A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
Joint Authors
Soler-Toscano, Fernando
Zenil, Hector
Source
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-12-21
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Soler-Toscano, Fernando& Zenil, Hector. 2017. A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences. Complexity،Vol. 2017, no. 2017, pp.1-10.
https://search.emarefa.net/detail/BIM-1143373
Modern Language Association (MLA)
Soler-Toscano, Fernando& Zenil, Hector. A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences. Complexity No. 2017 (2017), pp.1-10.
https://search.emarefa.net/detail/BIM-1143373
American Medical Association (AMA)
Soler-Toscano, Fernando& Zenil, Hector. A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences. Complexity. 2017. Vol. 2017, no. 2017, pp.1-10.
https://search.emarefa.net/detail/BIM-1143373
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1143373