Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines

Fernando Soler-Toscano; Hector Zenil; Jean-Paul Delahaye; Nicolas Gauvrit

Source-linked AI summary

Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines

Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye, Nicolas Gauvrit

arXiv:1211.1302v2Nov 6, 2012cs.ITcs.CCnlin.PS

TL;DR

The paper addresses how to approximate Kolmogorov complexity for finite and short strings, where conventional approaches face practical difficulties. It uses algorithmic-probability estimates derived from output frequencies of small Turing machines and applies the Coding Theorem. The resulting distributions support stable numerical approximations and show robustness across formalisms and sample sizes, within computational limits.

Problem
The paper addresses the practical evaluation of Kolmogorov complexity for finite and short strings, where lossless compression is difficult and existing theory is hard to use directly.
Method
The method estimates algorithmic probability from the output-frequency distributions of small deterministic Turing machines and converts those frequencies into complexity estimates using the Coding Theorem.
Results
The resulting distributions provide stable numerical approximations of Kolmogorov complexity for short strings, with evidence that estimates are robust across formalism and sample size.
Takeaways & Limitations
The approach provides an alternative to lossless compression for short-string complexity estimation and supports applications requiring numerical complexity values.
Takeaways & Limitations
Extending the method beyond 5-state machines is computationally constrained because the number of Turing machines grows exponentially with the number of states, and some length-12 estimates remain unstable.

Abstract

from arXiv · show

Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approximating the Kolmogorov-Chaitin complexity of short strings. The method is an alternative to the traditional lossless compression algorithms, which it may complement, the two being serviceable for different string lengths. We provide a thorough analysis for all $\sum_{n=1}^{11} 2^n$ binary strings of length $n<12$ and for most strings of length $12\leq n \leq16$ by running all $\sim 2.5 \times 10^{13}$ Turing machines with 5 states and 2 symbols ($8\times 22^9$ with reduction techniques) using the most standard formalism of Turing machines, used in for example the Busy Beaver problem. We address the question of stability and error estimation, the sensitivity of the continued application of the method for wider coverage and better accuracy, and provide statistical evidence suggesting robustness. As with compression algorithms, this work promises to deliver a range of applications, and to provide insight into the question of complexity calculation of finite (and short) strings.

Introduction

The paper develops a numerical approximation to Kolmogorov complexity from Turing-machine output frequencies, addressing practical limitations of existing approaches for finite and short strings. It extends earlier work with broader coverage, cross-source comparisons, and evidence about robustness.

The approach offers an alternative to lossless compression for estimating complexity, especially where finite-string evaluation has been difficult in practice.
The study approximates Kolmogorov complexity by applying algorithmic probability to output frequencies from 5-state, 2-symbol Turing machines.
Earlier work found an application in economic time-series analysis, but its wider use was limited by the length and number of available strings.
The present study analyzes longer strings and a number of strings increased by a factor of three orders of magnitude.
Comparisons across substantially different source sets and an informed non-halting cutoff provide evidence that the estimation and scaling are robust and less dependent on machine-sample size.

Preliminaries

The paper frames Kolmogorov complexity as an objective but uncomputable measure and motivates an algorithmic-probability alternative for short strings. Its method uses output frequencies from a standard small-Turing-machine formalism, with Busy Beaver reasoning helping manage noncomputability.

Kolmogorov complexity is the length of the shortest program producing a string on a universal Turing machine, but it is uncomputable.
Lossless compression supplies an upper bound on complexity, yet short strings are difficult to compress and expose gaps in practical complexity estimation.
For short strings, the invariance-theorem constant can substantially affect complexity values across programming languages or universal Turing machines.
Algorithmic probability assigns a universal-distribution frequency to strings and, through the Coding Theorem, connects higher production frequency with lower Kolmogorov complexity.
The chosen Rado formalism uses a binary alphabet, n states, an additional halt state, and a two-way unbounded tape, with outputs read from the traversed tape cells.
The method estimates algorithmic probability by running deterministic machines in the (n, 2) class and using Busy Beaver bounds to address non-halting computations.

Methodology

The Coding Theorem Method estimates string complexity from Turing-machine output frequencies, using reduced enumerations, runtime cutoffs, and symmetry-based completions to make large computations feasible.

Coding Theorem Method: The method approximates m(s) by running machines in a fixed enumeration, forming D(n,m) from output frequencies, and applying the Coding theorem to estimate K(s).D(n,m) assigns each produced string its count among halting machines; the paper calls the resulting approximation Km.
Computational scale: The five-state, two-symbol space contains 26 559 922 791 424 machines, making D(5) computationally demanding despite the method’s scalability motivation.The number of machines grows exponentially with the number of states, so producing D(5) requires considerable computational resources.
Runtime cutoff: A 500-step runtime cutoff was selected for five-state machines by using 4.6 times the known four-state Busy Beaver runtime and rounding to 500 steps.The cutoff was used to build the output frequency distribution for D(5), with theoretical justification provided later in the paper.
Reduction techniques: Reduced enumeration exploits transition-table symmetries, excludes predictable machines, and detects some non-halting machines before the full runtime is consumed.The reduction leaves 4/11 of the machines in the original enumeration while preserving outputs through reversals, complements, and added non-halting counts.
Distribution completion: The computation runs each machine with both 0 and 1 as blank symbols, then completes the resulting distributions using symmetry-based string transformations.The two blank-symbol runs avoid asymmetry from selecting only one initial tape symbol.
Non-halting detection: Period-two cycles are detected by checking whether the tape, machine state, and position recur after two steps, indicating infinite repetition.This filter identifies a class of non-halting machines without running them for the entire cutoff.

Results

The resulting D(5) distribution covers many short binary strings and supports complexity estimates, while runtime experiments indicate that the 500-step cutoff omits very few relevant halting machines.

Runtime reliability: 50 of 1.23×10^10 tested machines halted after 500 steps and before 5000, while 1 496 491 379 machines had not halted by 5000 steps.The experiment was used to assess how many machines were excluded by the D(5) cutoff.
Frequency and complexity: Table 1 lists the 147 most frequent D(5) strings, while Table 2 orders all 128 seven-bit strings by frequency and corresponding complexity.Table 2 contains 31 frequency groups representing different complexities among the 2^7 strings.
Runtime reliability: P(k > 500) ≈ e^-500λ was estimated from an exponential runtime model fitted with α = 1.12 and λ = 0.793.The nonlinear regression had residual sum-of-squares 3.392×10^-3 and was used to estimate the fraction missed by the cutoff.
Coverage: 99 608 different binary strings were produced, including every string shorter than 12 bits and nearly all 12-bit strings.Only two 12-bit strings were not produced; D(5) strings range from 1 to 49 bits, excluding lengths 42 and 46.
Length distribution: The cumulative length distribution from D(5) differs from D(4) and the theoretical 2^-n law because length 2 is more likely than length 1.The paper notes that the D(5) law does not decrease monotonically with string length.

Global simplicity

D(5) assigns lower probabilities to longer strings and recognizes repetition, symmetry, and complementation as patterns associated with simplicity. Its runtime distribution is modeled against observed machine halting times to assess the completeness of the construction.

Global simplicity: Most halting 5-state machines are covered by the t = 500 cutoff used to produce D(5), based on a sample run to t = 5000.Figure 2 compares runtime distributions from D(2) through D(5).
Global simplicity: Repetition, symmetrization, and 0-complementation produce different probabilities even for equal-length strings derived from s = 1011.For ss, symmetrized s̄s, and 0-complementation, the probabilities are 4.645999 × 10^-7, 5.335785 × 10^-7, and 3.649934 × 10^-7.
Global simplicity: Symmetry, complementation, and repetition are recognized by D(5), whose transformed-pattern means lie in the upper tail of the distribution for 2^n-length strings.This separation becomes more pronounced for longer strings.
Global simplicity: The first 50 probability-ranked climbers show subjectively simple patterns, consistent with longer strings sometimes appearing above shorter strings in the ranking.Climbers are strings whose length exceeds that of the next string in decreasing-probability order.
Global simplicity: Figure 3 compares observed and theoretical P(S = k|S ≤5000) across k using a logarithmic x-axis and two y-axis scales.The plot is designed to show the empirical and theoretical runtime distributions precisely.

Binomial behavior

The output distribution of random Turing machines differs from the binomial behavior of uniformly random binary strings because simpler, often unbalanced, patterns occur more frequently.

Binomial behavior: Uniformly random binary strings have a binomial distribution for the number of 0s.
Binomial behavior: D(5) yields a larger standard deviation than truly random sequences of length n.The broader distribution reflects the greater frequency of simple, often unbalanced patterns such as 0000000.
Binomial behavior: Random Turing-machine outputs are more scattered because simple patterns are often unbalanced.

Bayesian application

D(5) supports a Bayesian estimate of whether a sequence is random by combining a random-process model with its machine-output probability. The resulting estimates identify both highly nonrandom long strings and a set of short strings with high posterior randomness.

Bayesian application: D(5) uses a Bayesian model that treats a sequence as arising either from a random process or from a 5-state Turing machine.The model assigns equal prior probabilities to the random and machine-generation events.
Bayesian application: 16 strings have P(R|s) < 10^-16, and their lengths range from 47 to 49.The paper gives a long repetitive string as an example of this least-random group.
Bayesian application: 192 strings achieve P(R|s) > 1 − 1.7 × 10^-4, all with lengths 12 or 13.The concentration at these lengths may be specific to D(5).

Agreement in probability

D(5) and D(4) produce highly consistent measures of simplicity across strings of lengths 3 through 8, while their largest discrepancies occur among the shortest strings.

Agreement in probability: r^2 = 99.23% measures the relationship between D(4) and D(5) for all strings of lengths 3 through 8.The coefficient is interpreted as D(4) explaining 99.23% of the variation in D(5).
Agreement in probability: The only strings with absolute studentized residuals above 20 are 0 and 1, while all 4-long strings fall between 2 and 5.All 3-long strings have residuals between 5 and 20.

Agreement in rank

D(5) largely agrees with D(4) in ranking strings, while distinguishing more fine-grained groups and recognizing symmetry, complementation, and repetition as patterns of simplicity.

Symmetrization, 0-complementation, and repetition receive D(5) values in the upper tail of the distribution for strings of doubled length.This remains true even when comparing against the minimum mean among the three transformations.
D(5) distinguishes five groups among strings tied by D(4), reflecting finer-grained ranking.The groups consist of strings related by reversal and complementation.
The shortest strings with |R4 − R5| ≥ 5 have length 6, including examples with inverted ranks.One example is 000100, with R5 = 85 and R4 = 77.
D(5) and D(4) are similar measures of simplicity, although differences arise because D(5) is more fine-grained.The authors describe the discrepancies as rare enough for D(5) to remain a good approximation of the underlying simplicity measure.

Kolmogorov complexity approximation

The paper converts output frequencies of small Turing machines into numerical complexity estimates, preserving fine distinctions among short strings that compression may collapse. These estimates can exceed string length for short strings but become smaller for some sufficiently structured longer strings.

The Coding theorem converts string frequencies from D(n) into numerical estimates of Kolmogorov complexity for the chosen Turing-machine formalism.
The calculated complexity values are real numbers rather than integer program lengths, preserving finer classification at the cost of literal program-size interpretation.
The strings 00, 01, 10, and 11 receive the same calculated complexity from D(2) through D(5).The authors note that very short strings may not provide enough evidence for the intuitive distinction between apparent simplicity and randomness.
This frequency-based method can distinguish short strings that lossless compression algorithms often assign the same complexity approximation.The paper describes subtracting a constant as one way to lower absolute values while preserving relative order.
212 of 99,608 D(5) strings have program-size values smaller than their string lengths.The first such example has length 41 and approximate complexity 33.11.
The least frequent D(5) strings are not necessarily visually random because highly random strings may have frequencies too low to be produced.For length 12, the least frequent subset remains potentially unstable because it was generated by relatively few machines.

Robustness of KD(n)

The paper evaluates how stable KD(n) is across machine counts and computational formalisms. Rankings remain broadly consistent, though the least frequent strings are the most unstable and cross-distribution differences can reach several bits.

D(n + 1) preserves the ordering of D(n) except for few, minor discrepancies concentrated among the least frequent strings.These strings are most unstable because they are generated by relatively few machines.
The agreement between successive distributions remains high across the available comparisons, suggesting rapid rank convergence for small machine sets.The authors caution that divergence at a larger n cannot be ruled out completely.
Different computational models produce reasonable and correlated complexity-ranking distributions, including cellular automata and Post tag systems.
The robustness analysis estimates invariance-theorem constants by measuring maximum complexity differences between successive distributions.Smaller c values indicate more stable evaluations under this procedure.
The reported c values for |KD(4)(s) − KD(5)(s)| range from 5.022 to 2.797 across quartiles.
The maximum observed difference between KD(4) and KD(5) is 5 bits among the 1,832 strings occurring in both distributions.D(4) contributes fewer than 2% of the 99,608 strings produced in D(5).

Concluding remarks

The paper presents a stable algorithmic-probability method for estimating Kolmogorov complexity of short strings, while identifying computational limits and evidence of robustness across formalisms and sample sizes.

The method uses output frequency distributions from standard Busy Beaver Turing machines to produce stable numerical approximations of Kolmogorov complexity for short strings.It also estimates invariance-theorem error terms.
Improving D(5) substantially through D(n) for n > 5 is unlikely with current technology because the number of Turing machines grows exponentially with n.An order-of-magnitude increase in computational power would yield only a linear improvement on D(5).
The computationally expensive experiment need only run once for a set of short strings, making the method complementary to lossless compression.An online calculator releases the resulting data for public use.
Prior applications used the data for graph-complexity approximation and for classifying images and dynamical-systems diagrams alongside compression-based approximations.
The approach is presented as evidence that practical estimation can make short-string algorithmic complexity less dependent on formalism and support applications beyond deep theory.
Agreement with one-dimensional cellular automata and Post’s tag systems supports robustness across computational formalisms and sample sizes.