10217

# 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.

### 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.

### PERMANENT CITATION

 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 » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.