Kolmogorov Complexity of 3×3 and 4×4 Squares

Which of "11111111111111111111", "15747363020045852837", or "81162315385411264758" can be described in the most compact way? Each can be described as it is presented, using 20 characters. The first two could be described by and . The Kolmogorov complexity measures the length of the shortest program required to reproduce a pattern.
This Demonstration provides Kolmogorov complexity approximations to 3×3 and 4×4 square arrays. The approximations come from applying the Levin–Chaitin algorithmic coding theorem that relates the frequency of the appearance of a pattern and its Kolmogorov complexity. The coding theorem method [3, 4] consists, for this Demonstration, in the calculation of the output frequency distribution of Turing machines with five states and two symbols operating on a two-dimensional grid (instead of the traditional one-dimensional tape).
According to the coding theorem, the Kolmogorov complexity of a pattern is , where is the frequency of occurrence of ; this non-integer Kolmogorov complexity is denoted by [1]. You can either select a pattern using the bar or click directly on the squares of the grid for a desired configuration. The Demonstration will then display the Kolmogorov complexity value for the chosen grid.
The Compress function in Mathematica is another, more traditional way to approximate Kolmogorov complexity, and is shown for comparison, but unlike the coding theorem, lossless compression techniques do not deal well with small patterns.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

These squares are the basis of the block decomposition method [1, 2] for two-dimensional patterns used to classify the complexity of black and white bitmaps by decomposition into small squares. The block decomposition method is an extension of the coding theorem method [3, 4].
References
[1] H. Zenil, F. Soler-Toscano, J-P. Delahaye, and N. Gauvrit, "Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility," Dec. 30, 2012. arxiv.org/abs/1212.6745.
[2] H. Zenil, F. Soler-Toscano, J-P. Delahaye, and N. Gauvrit, Evaluating Kolmogorov Complexity: An Alternative to Compression Algorithms, Heidelberg: Springer-Verlag, forthcoming.
[3] F. Soler-Toscano, H. Zenil, J-P. Delahaye, and N. Gauvrit, "Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines," Nov. 6, 2012. arxiv.org/abs/1211.1302.
[4] The Algorithmic Nature Group. "The Online Algorithmic Complexity Calculator." (Feb 14, 2013) www.complexitycalculator.com.

RELATED LINKS

    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.