On the Kolmogorov-Chaitin Complexity for short sequences
October 23, 2018 8:33 World Scientific Review Volume - 9in x 6in LongAbstractDelahaye2
Chapter 1
On the Kolmogorov-Chaitin Complexity for short
sequences
Jean-Paul Delahaye∗ and Hector Zenil†
Laboratoire d’Informatique Fondamentale de Lille
Centre National de la Recherche Scientifique (CNRS)
Université des Sciences et Technologies de Lille
Among the several new ideas and contributions made by Gregory
Chaitin to mathematics is his strong belief that mathematicians should
transcend the millenary theorem-proof paradigm in favor of a quasi-
empirical method based on current and unprecedented access to compu-
tational resources.3 In accordance with that dictum, we present in this pa-
per an experimental approach for defining and measuring the Kolmogorov-
Chaitin complexity, a problem which is known to be quite challenging for
short sequences — shorter for example than typical compiler lengths.
The Kolmogorov-Chaitin complexity (or algorithmic complexity) of a
string s is defined as the length of its shortest description p on a universal
Turing machine U , formally K(s) = min{l(p) : U(p) = s}. The major
drawback of K, as measure, is its uncomputability. So in practical applica-
tions it must always be approximated by compression algorithms. A string
is uncompressible if its shorter description is the original string itself. If a
string is uncompressible it is said that the string is random since no pat-
terns were found. Among the 2n different strings of length n, it is easy to
deduce by a combinatoric argument that one of them will be completely
random simply because there will be no enough shorter strings so most of
them will have a maximal K-C complexity. Therefore many of them will
remain equal or very close to their original size after the compression. Most
of them will be therefore random. An important property of K is that it is
nearly independent of the choice of U . However, when the strings are short
in length, the dependence of K on a particular universal Turing machine U
∗delahaye@lifl.fr
†hector.zenil-chavez@malix.univ-paris1.fr
http://arxiv.org/abs/0704.1043v5
October 23, 2018 8:33 World Scientific Review Volume - 9in x 6in LongAbstractDelahaye2
2 Jean-Paul Delahaye and Hector Zenil
is higher producing arbitrary results. In this paper we will suggest an em-
pirical approach to overcome this difficulty and to obtain a stable definition
of the K-C complexity for short sequences.
Using Turing’s model of universal computation, Ray Solomonoff9,10
and Leonid Levin7 developed a theory about a universal prior distribu-
tion deeply related to the K-C complexity. This work was later known un-
der several titles: universal distribution, algorithmic probability, universal
inference, among others.5,6 This algorithmic probability is the probabil-
ity m(s) that a universal Turing machine U produces the string s when
provided with an arbitrary input tape. m(s) can be used as a universal
sequence predictor that outperforms (in a certain sense) all other predic-
tors.5 It is easy to see that this distribution is strongly related to the K-C
complexity and that once m(s) is determined so is K(s) since the formula
m(s) can be written in terms of K as follows m(s) ≈ 1/2K(s). The distri-
bution of m(s) predicts that non-random looking strings will appear much
more often as the result of a uniform random process, which in our ex-
periment is equivalent to running all possible Turing machines and cellular
automata of certain small classes according to an acceptable enumeration.
By these means, we claim that it might be possible to overcome the problem
of defining and measuring the K-C complexity of short sequences. Our pro-
posal consists of measuring the K-C complexity by reconstructing it from
scratch basically approximating the algorithmic probability of strings to ap-
proximate the K-C complexity. Particular simple strings are produced with
higher probability (i.e. more often produced by the process we will describe
below) than particular complex strings, so they have lower complexity.
Our experiment proceeded as follows: We took the Turing machine
(TM) and cellular automata enumerations defined by Stephen Wolfram.11
We let run (a) all 2−state 2−symbol Turing machines, and (b) a statistical
sample of the 3−state 2−symbol ones, both henceforth denoted as TM(2, 2)
and TM(3, 2).
Then we examine the frequency distribution of these machines’ outputs
performing experiments modifying several parameters: the number of steps,
the length of strings, pseudo-random vs. regular inputs, and the sampling
sizes.
For (a) it turns out that there are 4096 different Turing machines accord-
ing to the formula (2sk)sk derived from the traditional 5−tuplet description
of a Turing machine: d(s{1,2}, k{1,2}) → (s{1,2}, k{1,2}, {1,−1}) where s{1,2}
are the two possible states, k{1,2} are the two possible symbols and the last
entry {1,-1} denotes the movement of the head either to the right or to the
October 23, 2018 8:33 World Scientific Review Volume - 9in x 6in LongAbstractDelahaye2
On the Kolmogorov-Chaitin Complexity for short sequences 3
left. From the same formula it follows that for (b) there are 2985984 so
we proceeded by statistical methods taking representative samples of size
5000, 10000, 20000 and 100000 Turing machines uniformly distributed over
TM(3, 2). We then let them run 30, 100 and 500 steps each and we pro-
ceeded to feed each one with (1) a (pseudo) random (one per TM) input
and (2) with a regular input.
We proceeded in the same fashion for all one dimensional binary cellular
automata (CA), those (1) which their rule depends only on the left and right
neighbors and those considering two left and one right neighbor, henceforth
denoted by CA(t, c)‡ where t and c are the neighbor cells in question, to
the left and to the right respectively. These CA were fed with a single 1
surrounded by 0s. There are 256 one dimensional nearest-neighbor cellular
automata or CA(1, 1), also called Elementary Cellular Automata11) and
65536 CA(2, 1).
To determine the output of the Turing machines we look at the string
consisting of all parts of the tape reached by the head. We then partition
the output in substrings of length k. For instance, if k=3 and the Turing
machine head reached positions 1, 2, 3, 4 and 5 and the tape contains the
symbols {0,0,0,1,1} then we increment the counter of the substrings 000,
001, 011 by one each one. Similar for CA using the ”light cone” of all
positions reachable from the initial 1 in the time run. Then we perform
the above for (1) each different TM and (2) each different CA, giving two
distributions over strings of a given length k.
We then looked at the frequency distribution of the outputs of both
classes TM and CA§, (including ECA) performing experiments modifying
several parameters: the number of steps, the length of strings, (pseudo)
random vs. regular inputs, and the sampling sizes.
An important result is that the frequency distribution was very stable
under the several variations described above allowing to define a natural
distribution m(s) particularly for the top it. We claim that the bottom
of the distribution, and therefore all of it, will tend to stabilize by taking
bigger samples. By analyzing the following diagram it can be deduced that
the output frequency distribution of each of the independent systems of
‡A better notation is the 3− tuplet CA(t, c, j) with j indicating the number of symbols,
but because we are only considering 2 − symbol cellular automata we can take it for
granted and avoid that complication.
§Both enumeration schemes are implemented in Mathematica calling the functions
CelullarAutomaton and TuringMachine, the latter implemented in Mathematica version
October 23, 2018 8:33 World Scientific Review Volume - 9in x 6in LongAbstractDelahaye2
4 Jean-Paul Delahaye and Hector Zenil
computation (TM and CA) follow an output frequency distribution. We
conjecture that these systems of computation and others of equivalent com-
putational power converge toward a single distribution when bigger samples
are taken by allowing a greater number of steps and/or bigger classes con-
taining more and increasingly sophisticated computational devices. Such
distributions should then match the value of m(s) and therefore K(s) by
means of the convergence of what we call their experimental counterparts
me(s) and Ke(s). If our method succeeds as we claim it could be possible
to give a stable definition of the K-C complexity for short sequences inde-
pendent of any constant.
Fig. 1.1. The above diagram shows the convergence of the frequency distributions of
the outputs of TM and ECA for k = 4. Matching strings are linked by a line. As one
can observe, in spite of certain crossings, TM and ECA are strongly correlated and both
successfully group equivalent output strings. By taking the six groups — marked with
brackets — the distribution frequencies only differ by one.
By instance, the strings 0101 and 1010 were grouped in second place,
therefore they are the second most complex group after the group com-
posed by the strings of a sequence of zeros or ones but before all the other
October 23, 2018 8:33 World Scientific Review Volume - 9in x 6in LongAbstractDelahaye2
On the Kolmogorov-Chaitin Complexity for short sequences 5
2n strings. And that is what one would expect since it has a very low
K-C complexity as prefix of a highly compressible string 0101 . . .. In fa-
vor of our claims about the nature of these distributions as following m(s)
and then approaching K(s), notice that all strings were correctly grouped
with their equivalent category of complexity under the three possible oper-
ations/symmetries preserving their K-C complexity, namely reversion (sy),
complementation (co) and composition of the two (syco). This also sup-
ports our claim that our procedure is working correctly since it groups all
strings by their complexity class. The fact that the method groups all
the strings by their complexity category allowed us to apply a well-known
lemma used in group theory to enumerate actual different cases, which let
us present a single representative string for each complexity category. So
instead of presenting a distribution with 1024 strings of length 10 it allows
us to compress it to 272 strings.
We have also found that the frequency distribution from several real-
world data sources also approximates the same distribution, suggesting
that they probably come from the same kind of computation, supporting
contemporary claims about nature as performing computations.8,11 The
paper available online contains more detailed results for strings of length
k = 4, 5, 6, 10 as well as two metrics for measuring the convergence of
TM(2, 2) and ECA(1, 1) and the real-world data frequency distributions
extracted from several sources¶. A paper with mathematical formulations
and further precise conjectures is currently in preparation.
References
1. G.J. Chaitin, Algorithmic Information Theory, Cambridge University Press,
1987.
2. G.J. Chaitin, Information, Randomness and Incompleteness, World Scien-
tific, 1987.
3. G.J. Chaitin, Meta-Math! The Quest for Omega, Pantheon Books NY, 2005.
4. C.S. Calude, Information and Randomness: An Algorithmic Perspective
(Texts in Theoretical Computer Science. An EATCS Series), Springer; 2nd.
edition, 2002.
5. Kirchherr, W., M. Li, and P. Vitányi. The miraculous universal distribution.
Math. Intelligencer 19(4), 7-15, 1997.
6. M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and Its
Applications, Springer, 1997.
¶It can be reached at arXiv: http://arxiv.org/abs/0704.1043.
A website with the complete results of the whole experiment is available at
http://www.mathrix.org/experimentalAIT/
http://arxiv.org/abs/0704.1043
October 23, 2018 8:33 World Scientific Review Volume - 9in x 6in LongAbstractDelahaye2
6 Jean-Paul Delahaye and Hector Zenil
7. A.K.Zvonkin, L. A. Levin. ”The Complexity of finite objects and the Algo-
rithmic Concepts of Information and Randomness.”, UMN = Russian Math.
Surveys, 25(6):83-124, 1970.
8. S. Lloyd, Programming the Universe, Knopf, 2006.
9. R. Solomonoff, The Discovery of Algorithmic Probability, Journal of Com-
puter and System Sciences, Vol. 55, No. 1, pp. 73-88, August 1997.
10. R. Solomonoff, A Preliminary Report on a General Theory of Inductive In-
ference, (Revision of Report V-131), Contract AF 49(639)-376, Report ZTB-
138, Zator Co., Cambridge, Mass., Nov, 1960
11. S. Wolfram, A New Kind of Science, Wolfram Media, 2002.
	*-14pt
	1. On the Kolmogorov-Chaitin Complexity for short sequences
	Jean-Paul Delahaye and Hector Zenil
