9711

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.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+