Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness

Jean-Paul Delahaye; Hector Zenil

Source-linked AI summary

Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness

Jean-Paul Delahaye, Hector Zenil

arXiv:1101.4795v5Jan 25, 2011cs.ITcs.CCmath.IT

TL;DR

Estimating algorithmic complexity for short strings is difficult because compression estimates can vary considerably with the compressor and its parameters. This paper estimates complexity from the outputs of small Turing machines; its frequency tables show occurrence related to string length and lower-table strings appearing more random-looking.

Problem
Compression-based estimates for short strings differ considerably with compressor choice and parameters, even though short strings are common in practical settings.
Source: §1 · p. 3
Method
The paper counts strings produced by halting (n,2) Turing machines to form an empirical universal distribution D, then estimates complexity using the coding theorem.
Source: §4.1 · p. 10
Results
The frequency tables show occurrence correlating with string length, with counts appearing to decrease exponentially, while strings nearer the bottom look more random.
Source: §5.1 · pp. 12, 15
Takeaways & Limitations
The coding-theorem estimates preserve strings’ relative complexity order despite a shared additive constant and a print-related surplus in short-string values.
Source: §6 · p. 26
Calculating D(n) rapidly becomes impractical for even slightly larger state counts, while thorough analysis is limited by the halting problem’s undecidability.
Source: §3 · p. 9

Abstract

from arXiv · show

We describe an alternative method (to compression) that combines several theoretical and experimental results to numerically approximate the algorithmic (Kolmogorov-Chaitin) complexity of all $\sum_{n=1}^82^n$ bit strings up to 8 bits long, and for some between 9 and 16 bits long. This is done by an exhaustive execution of all deterministic 2-symbol Turing machines with up to 4 states for which the halting times are known thanks to the Busy Beaver problem, that is 11019960576 machines. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the (Levin-Zvonkin-Chaitin) coding theorem.

1. Overview

Compression is a common way to upper-bound string complexity, but short strings resist reliable compression because program overhead and compressor choices can dominate. This paper proposes an alternative numerical method: execute 2-symbol Turing machines up to 4 states, use output frequencies to estimate algorithmic probability, and infer complexity via the coding theorem.

Motivation

Compression gives an upper bound on C(s), but for short strings program overhead and compressor choices or parameters can dominate, making estimates vary considerably.Although compressors’ asymptotic behavior eventually converges to C(s), short strings remain challenging to estimate.Source: §1 · pp. 2–3

Method

Using Busy Beaver results, the study runs machines with known halting runtimes from the shortest (fewest states) upward, recording how many produce each string.This execution strategy is framed as a way to find the shortest program within a standard Turing-machine formalism.Source: §1 · p. 3

Contribution

The proposed procedure numerically calculates the complexity of short strings as an alternative to indirect compression-based methods, combining halting probability, Busy Beaver, algorithmic probability, Levin’s semi-measure, and the coding theorem [11, 12].Source: §1 · p. 3

Method

The method exhaustively runs 2-symbol Turing machines up to 4 states, counts their halting outputs to estimate string algorithmic probability, then applies the coding theorem to evaluate complexity.The resulting output frequencies provide an empirical distribution from which the algorithmic probability of a string is calculated.Source: §1 · p. 3

2. Preliminaries

The preliminaries define halting probability, prefix-free algorithmic complexity, and algorithmic probability, and explain why these quantities are generally noncomputable. They introduce Busy Beaver functions, whose values are known for small two-symbol Turing machines.

2.1. The Halting problem and Chaitin’s

Chaitin’s Ω[3] is a universal prefix-free machine’s halting probability for a random program, and its value depends on the chosen machine.No more than finitely many digits of an Ω number can be computed; the passage notes examples for which no digit can be computed.Source: §2.1 · p. 4
Knowing the first n bits of Ω lets one determine whether programs of length at most n halt; most programs stop quickly or never halt.The paper connects these theoretical arguments with empirical values of halting times and output-string length frequencies.Source: §2.1 · pp. 4–5

2.2. Algorithmic (prefix-free) complexity

C_U(s) is the bit-length of the shortest prefix-free program for universal machine U that produces s and halts.The invariance theorem bounds the difference between complexities under two universal machines by an additive constant independent of s.Source: §2.2 · p. 5
C(s) cannot be computed by a program that takes s as input and outputs its complexity.The passage attributes this noncomputability to a reduction to the halting problem.Source: §2.2 · p. 5

2.3. Algorithmic probability

Levin’s semi-measure m(s) is the probability that a random program on a universal prefix-free machine outputs s.Unlike Ω, algorithmic probability depends on the output and halting time of halting machines; its distribution assigns the shortest programs greater weight than longer ones.Source: §2.3 · p. 6
m(s), like C(s) and Ω, is noncomputable because of the halting problem.The section also states that algorithmic probability is connected to algorithmic complexity.Source: §2.3 · p. 6

2.4. The Busy Beaver problem: Solving the halting problem for small Turing machines

P(n) is the maximum number of 1s and S(n) the maximum runtime among halting n-state, 2-symbol Turing machines; both functions are noncomputable, but values are known for n ≤ 4.The paper follows the Turing-machine model introduced by Rado.Source: §2.4 · pp. 6–7

3. The empirical distribution D

The section defines D(n) as the relative frequency of each output among halting n-state, two-symbol Turing machines. It reports example frequencies and establishes that D(n) is noncomputable, although exact values can be obtained for small n using Busy Beaver bounds.

The machines use a binary alphabet, n states plus a halt state, and are run with both 0 and 1 as blank symbols to avoid asymmetry.Source: §3 · pp. 7–8
D(n) assigns each string the fraction of halting n-state, two-symbol machines that produce it; outputs are the contiguous tape cells traversed by the head at halting.Source: §3 · p. 8
D(1) has 24 halting machines, with 0 and 1 each at 0.5; D(2) has 6,088, with 0 and 1 each at 0.328, and tables report D(1)–D(3) and top-ranked D(4).Source: §3 · p. 8
D(n) is noncomputable: if it were computable, its halting-machine count and output frequencies would let one decide whether any n-state machine halts, solving the halting problem.Source: §3 · pp. 8–9
Exact D(n) values are calculable for n < 5 using Busy Beaver bounds; for n = 4, S(4) = 107, so machines running longer than 107 steps are stopped.Source: §3 · p. 9
For larger n, sampling can approximate D(n) asymptotically, and D(n) is approachable from above; despite being well-defined, its calculation rapidly becomes impractical as the state count grows.Source: §3 · p. 9

4. Methodology

The methodology estimates string complexity by running bounded two-symbol Turing machines, using Busy Beaver halting times to address the halting problem. It counts output frequencies to form an empirical distribution and applies the coding theorem to estimate complexity, with a shared additive constant affecting absolute values but not relative order.

4. Methodology

The computation processed about 1.3775 × 10^9 machines per day and took about nine days to run all (4, 2) machines up to Busy Beaver step bounds.The halting-time bounds addressed the halting problem; computing time and programming effort remained constraints.Source: §4 · pp. 9–10

4.1. Numerical calculation of D

The study derives D(n) by counting halting machines’ n-bit outputs, treats D as an empirical universal distribution, and estimates C(s) through the coding theorem.The coding theorem introduces a common additive constant, so absolute values depend on that choice while relative order should not.Source: §4.1 · p. 10
The calculation reports 72, 20,000, 15,059,072, and 22,039,921,152 two-way-tape machines started on tapes filled with 0s and 1s for D(2), D(3), and D(4).The number of machines grows exponentially with the number of states; D(5) would require 53,119,845,582,848 machines, while P(5) and S(5) were unknown.Source: §4.1 · p. 11
To preserve output frequencies, the study avoided some symmetry reductions but ran one-direction rules on a 0-filled tape and recovered skipped outputs by reversion and complementation.Unlike a Busy Beaver search focused on maximum values, constructing a probability distribution requires every output to be considered equally.Source: §4.1 · p. 11

5. Results

The results show how output frequencies from small Turing machines classify strings by probability and yield algorithmic-complexity estimates, while also revealing patterns in halting and runtimes. For (4, 2), the distribution covers every string up to 8 bits, and longer runtimes are rare.

5.1. Algorithmic probability tables

D(2) and D(3) preserve earlier string rankings while increasingly sorting outputs into length blocks, with simple strings prominent and fewer strings represented at larger lengths.D(2) produced 22 of the 30 strings shorter than 5 bits; D(3) produced 128 of 254 strings shorter than 8 bits, and its most frequent strings included 0^k and reversed 1^k for n ≤ 8.Source: §5.1 · pp. 12–13
D(4) produced 1,824 strings, including strings of every length up to 8 bits, and its longest outputs were 16 bits long.The 16-bit strings had about 5.4447×10^-10 probability each, lower than the Busy Beaver strings’ total probability of 4.02×10^-9.Source: §5.1 · p. 15
D(4) largely preserves D(3)’s frequency ranking, but string length no longer determines position and 399 strings rise above their length groups.The rankings differ in 17 of D(3)’s 128 strings, with a Spearman rank correlation coefficient of 0.98; groups appearing sooner than expected have greater algorithmic probability and lower complexity than shorter strings.Source: §5.1 · pp. 15, 17

5.2. Derivation and calculation of the string’s algorithmic complexity

The greatest algorithmic complexity calculated from D(4) using the coding theorem was 29 bits.The paper notes that the resulting frequency-based measure is related to, but not necessarily identical to, Kolmogorov-Chaitin complexity.Source: §5.2 · pp. 19, 22

5.2.1. Same length string complexity

The same-length classification compares the structure of strings of equal length drawn from D(4).The section describes this comparison as using the calculated complexity classification.Source: §5.2.1 · p. 22

5.3. Runtimes investigation

Long runtimes are rare, and the empirical runtime distribution approaches the a priori computable distribution predicted in.Strings produced before 8 steps account for 49% of outputs from halting (4, 2) machines, and no n-bit string is produced before t = n.Source: §5.3 · p. 24

6. Discussion

The discussion frames short-string complexity as an objective machine-based ranking, while explaining how print-program overhead and encoded halting delimiters affect interpretation. It also considers how rankings vary across machine spaces and what the computed values reveal.

6. Discussion

For very short strings, apparent simplicity does not establish relative randomness; larger alternating strings may admit short descriptions, and computing D(5) could change some ranks.The authors argue that strings such as 010 and 001 can only be compared objectively by running machines under their formalism.Source: §6 · p. 26
The method provides a hierarchy of strings by relative algorithmic complexity, while a constant print-program surplus can be subtracted without changing their order.Subtracting 1 brings the shortest strings’ values to their lengths, though larger strings may still have values above their lengths.Source: §6 · p. 26
The machine encodes string length through its halting configuration, unlike cellular-automaton approaches that require an arbitrary stopping time.The authors interpret the extra information as delimiting the output length.Source: §6 · pp. 26–27
Non-integer complexity values from the coding theorem provide finer information about the positions of ranked strings, despite program sizes being integer-valued.The authors leave open whether the actual string frequencies converge across larger machine spaces.Source: §6 · pp. 27–28
For 1 < n < 5, D(n) preserves most of D(n − 1)’s string order, with very strong ranking correlation across machine spaces.The first rank difference between D(3) and D(4) occurs at place 20; the authors suggest smaller spaces may miss some strings.Source: §6 · p. 27

7. Concluding remarks

The paper provides numerical complexity tables for short strings and examines small Turing machines’ halting runtimes and output-frequency distributions. Its algorithmic-probability approach yields an empirical distribution independent of an additive constant, while robustness across computational formalisms remains under investigation.

7. Concluding remarks

The study provides numerical complexity tables for short strings and characterizes small Turing machines’ halting runtimes and output-frequency distributions.The calculation of D(n) yields an empirical, natural distribution independent of an additive constant; the algorithmic-probability approach reduces that constant’s impact and is bottom-up rather than top-down.Source: §7 · p. 28
Robustness across computational formalisms remains an open question, although prior results find reasonable classifications intuitive and statistically correlated across formalisms.The paper identifies alternative tape directions, n-dimensional cellular automata, and Post tag systems as examples for investigation.Source: §7 · p. 28