A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity and that, usually, generic lossless compression algorithms fall short at characterizing features other than statistical ones not different from entropy evaluations, here we explore...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2017/7208216 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832546580388904960 |
|---|---|
| author | Fernando Soler-Toscano Hector Zenil |
| author_facet | Fernando Soler-Toscano Hector Zenil |
| author_sort | Fernando Soler-Toscano |
| collection | DOAJ |
| description | Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity and that, usually, generic lossless compression algorithms fall short at characterizing features other than statistical ones not different from entropy evaluations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure m calculated from the output distribution of small Turing machines. We introduce and justify finite approximations mk that have been used in some applications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both m and mk and compare them to Levin’s Universal Distribution. We provide error estimations of mk with respect to m. Finally, we present an application to integer sequences from the On-Line Encyclopedia of Integer Sequences, which suggests that our AP-based measures may characterize nonstatistical patterns, and we report interesting correlations with textual, function, and program description lengths of the said sequences. |
| format | Article |
| id | doaj-art-16ba8bbfbd54427bacb462e886d77289 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2017-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-16ba8bbfbd54427bacb462e886d772892025-02-03T06:47:53ZengWileyComplexity1076-27871099-05262017-01-01201710.1155/2017/72082167208216A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer SequencesFernando Soler-Toscano0Hector Zenil1Grupo de Lógica, Lenguaje e Información, Universidad de Sevilla, Sevilla, SpainAlgorithmic Nature Group, LABORES, Paris, FranceGiven the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity and that, usually, generic lossless compression algorithms fall short at characterizing features other than statistical ones not different from entropy evaluations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure m calculated from the output distribution of small Turing machines. We introduce and justify finite approximations mk that have been used in some applications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both m and mk and compare them to Levin’s Universal Distribution. We provide error estimations of mk with respect to m. Finally, we present an application to integer sequences from the On-Line Encyclopedia of Integer Sequences, which suggests that our AP-based measures may characterize nonstatistical patterns, and we report interesting correlations with textual, function, and program description lengths of the said sequences.http://dx.doi.org/10.1155/2017/7208216 |
| spellingShingle | Fernando Soler-Toscano Hector Zenil A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences Complexity |
| title | A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences |
| title_full | A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences |
| title_fullStr | A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences |
| title_full_unstemmed | A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences |
| title_short | A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences |
| title_sort | computable measure of algorithmic probability by finite approximations with an application to integer sequences |
| url | http://dx.doi.org/10.1155/2017/7208216 |
| work_keys_str_mv | AT fernandosolertoscano acomputablemeasureofalgorithmicprobabilitybyfiniteapproximationswithanapplicationtointegersequences AT hectorzenil acomputablemeasureofalgorithmicprobabilitybyfiniteapproximationswithanapplicationtointegersequences AT fernandosolertoscano computablemeasureofalgorithmicprobabilitybyfiniteapproximationswithanapplicationtointegersequences AT hectorzenil computablemeasureofalgorithmicprobabilitybyfiniteapproximationswithanapplicationtointegersequences |