On the Kolmogorov-Chaitin complexity for short sequences

This is a presentation about joint work between Hector Zenil and Jean-Paul Delahaye. Zenil presents Experimental Algorithmic Theory as Algorithmic Information Theory and NKS, put together in a mixer. Algorithmic Complexity Theory defines the algorithmic complexity k(s) as the length of the shortest program that produces s. But since finding this short program is in general an undecidable question, the only way to approach k(s) is to use compression algorithms. He shows how to use the Compress function in Mathematica to give an idea about the compressibility of various sequences. However, the idea of applying a compression algorithm breaks down for very short sequences. This is true not only for the Compress function, but also for any other compression algorithm. Zenil's approach is to construct a metric of algorithmic complexity for short sequences from scratch. He defines the algorithmic probability as the probability that an arbitrary program produces a sequence. The basic idea is to run a whole class of computational devices such as Turing Machines or Cellular Automata, and compute the distributions of the sequences they generate. Zenil presents a comparison of frequency distributions of sequences generated by 2-state 3-color Turing Machines and 2-color radius 1 Cellular Automata. He also compared these distributions to distributions found in data from the real world, and found that not only there is correlation across different systems, but also that the distributions are rather stable, and the difference between the distributions in abstract systems and real-world data can be attributed to noise. In his paper Zenil elaborates on the nature of the noise he has encountered. Zenil conjectures that the correlation distances between different systems decreases with a larger number of steps, and converge in the infinite limit case
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 65,657
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Is Evolution Algorithmic?Marcin Miłkowski - 2009 - Minds and Machines 19 (4):465-475.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
General Random Sequences and Learnable Sequences.C. P. Schnorr & P. Fuchs - 1977 - Journal of Symbolic Logic 42 (3):329-340.
Two Dogmas of Computationalism.Oron Shagrir - 1997 - Minds and Machines 7 (3):321-44.
Cellular Automata.Francesco Berto & Jacopo Tagliabue - 2012 - Stanford Encyclopedia of Philosophy.
A Theory of Probability.T. V. Reeves - 1988 - British Journal for the Philosophy of Science 39 (2):161-182.


Added to PP index

Total views
21 ( #521,736 of 2,462,330 )

Recent downloads (6 months)
1 ( #449,321 of 2,462,330 )

How can I increase my downloads?


My notes