Algorithmic Dimensions via Learning Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910509902594048 |
|---|---|
| author | Lutz, Jack H. Migunov, Andrei N. |
| author_facet | Lutz, Jack H. Migunov, Andrei N. |
| contents | We characterize the algorithmic dimensions (i.e., the lower and upper asymptotic densities of information) of infinite binary sequences in terms of the inability of learning functions having an algorithmic constraint to detect patterns in them. Our pattern detection criterion is a quantitative extension of the criterion that Zaffora Blando used to characterize the algorithmically random (i.e., Martin-Löf random) sequences. Our proof uses Lutz's and Mayordomo's respective characterizations of algorithmic dimension in terms of gales and Kolmogorov complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01747 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithmic Dimensions via Learning Functions Lutz, Jack H. Migunov, Andrei N. Information Theory We characterize the algorithmic dimensions (i.e., the lower and upper asymptotic densities of information) of infinite binary sequences in terms of the inability of learning functions having an algorithmic constraint to detect patterns in them. Our pattern detection criterion is a quantitative extension of the criterion that Zaffora Blando used to characterize the algorithmically random (i.e., Martin-Löf random) sequences. Our proof uses Lutz's and Mayordomo's respective characterizations of algorithmic dimension in terms of gales and Kolmogorov complexity. |
| title | Algorithmic Dimensions via Learning Functions |
| topic | Information Theory |
| url | https://arxiv.org/abs/2407.01747 |