Report
Algorithmic Dimensions via Learning Functions
| العنوان: | Algorithmic Dimensions via Learning Functions |
|---|---|
| المؤلفون: | Lutz, Jack H., Migunov, Andrei N. |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - 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\"of random) sequences. Our proof uses Lutz's and Mayordomo's respective characterizations of algorithmic dimension in terms of gales and Kolmogorov complexity. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2407.01747 |
| رقم الانضمام: | edsarx.2407.01747 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |