The beacon with no story

Imagine a sealed beacon that emits either darkness or light once per second. After sixty-four seconds it has produced a binary record. One record alternates perfectly: 010101… Another has no visible regularity. Both records have the same length, both could have arisen from the same physical switch, and each particular outcome had the same probability under a fair coin model. Yet a scientist would treat them differently. The alternating record invites a short law. The irregular record appears to demand a list.

That difference is Chaitin’s starting problem. Classical probability describes an ensemble and a generating distribution. It can say that each sixty-four-bit result has probability 2⁻⁶⁴. It does not, by that statement alone, distinguish the alternating string from a visually irregular one. Shannon’s entropy measures average uncertainty under a distribution. Chaitin asks a different question about an individual finite object: how much machinery is required to produce this exact string?

The intuitive answer is easy to say and difficult to discipline. A string has a pattern when a shorter specification generates it. “Print 01 thirty-two times” is economical. Quoting all sixty-four bits is merely the data wearing quotation marks. The danger lies in the word shorter. Shorter in which language? On which machine? Are two instructions really two units if one hides a complex operation? Can the shortest programme be found? The 1966 paper spends most of its technical effort making those questions precise.

Three quantities that must remain separate

String length counts output bits. State complexity counts the least machine states needed to print the string in a specified family. Programme-description length counts bits needed to encode the table. The paper connects them without identifying them. An N-state, M-symbol table has many entries, and each transition may name one of N states. For fixed M and large N, encoding the meaningful table requires approximately N(M+1)log₂N bits after redundancies are controlled.

This distinction blocks a common historical error. Modern expositions write K(x) for the bit length of a shortest programme on a universal machine. Chaitin’s 1966 paper mainly analyses L_M(S), the smallest number of states in an M-symbol Turing machine that calculates S, followed by L(S) for bounded-transfer machines. Bit-program theory is developed in the 1969 sequel. Self-delimiting programmes and the mature information identities arrive later.

The output convention is part of the definition, not a clerical detail. A machine must halt with the finite sequence recoverable in the prescribed position and format. Without such a convention, one could hide information in where the head stops, in unused tape territory, or in the choice of a decoding rule supplied after the computation. Chaitin’s tables are therefore judged as complete generators. The programme includes the choices needed to leave the requested finite binary object, while fixed conventions are charged uniformly to every competitor.

There is also a useful asymmetry between pattern and cause. The beacon may have been driven by a deterministic counter, a fair coin, a biased physical process or a human typing digits. The complexity measure sees only the finished record and the stipulated machines. It asks whether an economical executable account exists, not which account actually caused the observations. That makes the measure suitable for mathematics, where the object can be held fixed, but it prevents a leap from incompressibility to claims about physical indeterminism. A causally random device can emit a simple run of zeros, and a deterministic calculation can emit a string with no shorter description in the chosen system.

Counting states, not slogans

A machine in the first part has a one-way infinite tape, N internal states and M tape symbols. Its programme is an N-by-M table. Each cell names a next state and an elementary action: move left, move right, write a symbol, or halt through a designated convention. The output is the finite binary block left on the tape when the machine stops in the required position.

Naively, every table repeats arbitrary state names. Relabelling states leaves behaviour unchanged, unreachable rows never participate, and some transition conventions can be simplified. Chaitin therefore canonicalises the table. Beginning from the initial state, he scans entries and assigns the next unused number when a new state is first reached. Programme size is tied to computation rather than an author’s naming habits.

After normalisation, the number of genuinely different N-state programmes is still enormous, yet it can be bounded. Taking a base-two logarithm converts programme counts into bits required to select one table. The leading cost is about N(M+1)log₂N bits. N counts rows, M+1 reflects effective table choices, and log N is the price of naming a state among N possibilities.

Define L_M(S) as the least N for which some N-state, M-symbol machine prints S. Define L_M(C_n) as the maximum L_M(S) among all 2ⁿ strings of length n. C_n contains the hardest strings at that length. This maximum is the comparison scale. A string is highly complex when its least machine approaches the largest least machine required by an equal-length peer.

The asymptotic formula comes from a squeeze. Too few small machines exist to cover all 2ⁿ strings, which gives the lower bound. Chaitin also builds tables whose transition choices carry blocks of any requested output, which gives the upper bound. Roughly, N rows offer N(M+1)log N bits of capacity. Solving for N produces n divided by (M+1)log n. One side is a counting obstruction; the other is an explicit construction.

The logarithm is the signature of unrestricted addressing. If a table has N rows, a next-state field can select among roughly N destinations. That one selection can therefore carry about log₂N bits. There are a number of effective selections proportional to N(M+1), so the whole normalised table can distinguish about 2^{N(M+1)log N} behaviours before lower-order factors are considered. Requiring enough candidates to cover 2ⁿ possible outputs forces N(M+1)log N to approach n. This is why the maximum state count grows more slowly than linearly even though every output has n bits.

The construction half is indispensable. Counting alone proves that some outputs resist small tables, but it does not rule out the possibility that the hardest outputs require wildly more than the counting threshold. Chaitin encodes pieces of the desired sequence into transition choices and supplies fixed table machinery to emit them in order. The construction shows that every n-bit sequence is within the advertised scale. Lower and upper bounds then meet in their leading term. The result is not a numerical estimate for one familiar string; it is a calibration of the worst least-table size over an entire length class.

Canonical numbering also explains why raw source-code length would answer a different question. A verbose table may contain comments, duplicated unreachable rows or extravagant identifiers. Deleting those features can shrink the text without changing the computation. Chaitin instead counts a normal form whose combinatorial degrees of freedom can be analysed. The normal form is still a design choice, but it converts a vague appeal to a short description into a finite catalogue that can be bounded above and below.

When the programme table acquires geography

The ordinary machine permits a transition from any row to any other row. A single table entry may jump from state 2 to state 20,000. That freedom hides a large address inside one transition. State count alone then understates what the programme can encode. It also makes two programmes awkward to join: the state names and long jumps of one component can collide with those of the other.

Chaitin’s second machine family places a fixed upper bound on transfer distance. A transition may move control only to a nearby row. To reach a remote part of the table, the machine passes through intermediate rows and uses the tape to keep track of progress. The programme now has spatial structure. Long-distance authority must be paid for through an explicit route.

The restriction does not destroy universality. Chaitin gives two simulation ideas. A universal bounded-transfer programme can read an encoded ordinary programme from the tape and imitate it. Alternatively, rows can be interwoven in a braid: one type simulates an operation, another returns control towards the beginning, and a third walks towards the intended state while decrementing a tape counter. Local jumps plus memory recover distant control.

The price is a different complexity rate. For bounded-transfer machines, the maximum L(C_n) is asymptotic to a positive constant a times n. The constant depends on the fixed machine convention and transfer bound. The linear form matters more than its numerical value. Each additional stretch of output requires a proportionate amount of programme geography.

The proof uses subadditivity. Take a hardest m-bit string and a hardest n-bit string. A bounded-transfer programme can place the two component programmes next to one another, adjust the second component’s local references, run the first, then the second, and concatenate their outputs. Because transfers are local, the adjustment does not require an address whose size grows with the whole table.

A subadditive sequence cannot sustain arbitrary oscillations in cost per output bit. Divide by n. For any fixed block length d, long outputs can be tiled by d-bit blocks plus a remainder. The average cost of the long output is therefore no greater than the average cost of the d-bit block, apart from a vanishing remainder. Taking the greatest lower bound across block sizes yields a limiting rate. Counting separately keeps that rate above zero.

The stitching argument must track a maximum, not a convenient pair. Choose any string z of length m+n and split it into an m-bit prefix x and an n-bit suffix y. By definition, x has a programme no larger than the hardest m-bit programme, and y has one no larger than the hardest n-bit programme. Join those two programmes. The resulting upper bound applies to every z, so it applies in particular to the hardest member of length m+n. This order of quantifiers is what turns an engineering construction into the inequality for L(C_m+n).

Local transfers make the join uniform. If state references are relative and bounded, shifting an entire component down the table does not enlarge the names written in each row. A small connector can hand control from the first component to the second. With unrestricted absolute destinations, relocation can alter references throughout a component, and the apparent one-state operation may conceal a destination selected from the whole table. Chaitin’s restriction exposes that hidden address cost by forcing remote control to travel through intermediate structure.

The constant a should consequently be read as an exchange rate set by the formal machine. It records how many bounded-transfer states are needed per output bit in the worst case after long-run overheads settle. Chaitin proves that the rate exists and is positive; he does not offer a machine-independent physical constant. Change the permitted local actions or transfer radius and a may change. The theorem’s robust content is the linear regime and the compositional mechanism producing it.

Maximum complexity becomes a definition of randomness

Chaitin now returns to the beacon. A scientist regards a short generative rule as a discovered pattern. A programme that merely stores the entire record offers no compression and therefore no explanation in this narrow formal sense. The shorter the programme compared with the data, the more arbitrary detail has been removed. The comparison is descriptive rather than semantic: a concise false theory and a concise true theory can have similar lengths, so empirical adequacy still matters.

For each length n, the paper calls strings random or patternless when their complexity is approximately the maximum L(C_n) available at that length. “Approximately” is essential because exact maxima fluctuate and machine conventions impose finite overheads. A deficit m below the ceiling records how many units of compressibility have been found.

Counting then supplies a census. If the number of programmes m units below maximum is at most a 2^−m fraction of the n-bit output space, only that fraction can be markedly compressible. Nearly all strings sit close to the ceiling. This is the finite incompressibility principle in the state-count setting.

High complexity also constrains simple statistical deviations. A severely biased n-bit string belongs to the much smaller class of strings with that composition. It can be named by specifying the positions of its rare symbols plus a decoding routine. Its description therefore falls below the general ceiling for sufficiently large n. Similar arguments connect missing blocks or other effectively recognisable regularities to savings.

The 1966 paper cautiously states that statistical properties begin with forms of the law of large numbers and defers fuller development. Its definition of an infinite random sequence, requiring all initial segments to be random in the finite sense, is historically important but not the final word. Martin-Löf’s parallel 1966 work uses effective null tests. Chaitin’s 1969 sequel develops statistical considerations. Later equivalence results require refined complexity notions and bounded deficits, not a casual identification of every long irregular prefix with randomness.

The majority claim has a precise but limited force. Fix a deficit d below the maximum scale and catalogue every programme short enough to qualify. Each halting programme contributes at most one output. If the catalogue contains at most a 2^−d fraction of the number of n-bit strings, then at least a 1−2^−d fraction escape that deficit. Programme collisions and failures to halt only strengthen the conclusion. The proof establishes that incompressibility is typical under uniform counting over strings, although it offers no effective list of the typical members.

This last qualification matters whenever a sample is presented as evidence. A counting theorem says that a uniformly chosen n-bit string is likely to lie outside a small description catalogue. It does not license the reverse inference that a particular unexplained record was uniformly chosen. Nor does it make visual irregularity a certificate. A short number-theoretic generator can produce digits that defeat a human glance, while a chance process can produce a conspicuous pattern. The description test and the sampling model answer different questions and must be argued separately.

Statistical defects become relevant only when they themselves define small, effectively decodable classes. If a record has exactly four ones, a description can name the four positions and invoke a fixed placement routine. If a long block never occurs, one may enumerate strings satisfying that restriction and name the target by its index. These are compression arguments, not declarations that every familiar statistical test is automatically built into the 1966 machine measure. The decoder, class boundary and encoding cost must all be counted.

The shortest-description trap

A definition can be mathematically exact without being computable. To upper-bound L(S), find a programme that prints S. Every discovered programme is a witness that the minimum is no larger. To prove a matching lower bound, eliminate every smaller programme. Some halt with another output; some halt with S; some run for a century; some never halt. No universal clock tells us when the remaining candidates are safe to dismiss.

Chaitin’s paper makes the contradiction sharper. Suppose exact complexity were computable. Given n, an algorithm could examine all n-bit strings, calculate each complexity and select a member of C_n, the maximally complex set. But the selection algorithm plus a compact encoding of n would itself be a short programme for that selected string. For sufficiently large n, the constructed description would be far smaller than the maximum it was supposed to attain.

The architecture resembles Berry’s paradox: “the least number not nameable in fewer than eleven words” appears to name what it declares unnameable. Here, programmes, machine conventions and asymptotic inequalities replace linguistic ambiguity. The contradiction does not say complexity is meaningless. It says its exact values outrun total effective calculation.

To see why the selector is short, separate its fixed and variable parts. The alleged complexity procedure, the loop that enumerates n-bit strings and the instruction to choose the first maximum are fixed code. Only n varies. Under any reasonable encoding, naming n costs on the order of log n bits, or a similarly modest number of states in the paper’s construction. Yet the selected output belongs to the hardest class and has complexity on the scale already established for n-bit strings. For large n, the fixed selector plus the compact parameter is too small. Exactness causes the contradiction.

A one-sided approximation survives. Dovetail the executions of all programmes: give each candidate one step, then another, and record any output when it halts. Whenever a shorter programme for S appears, lower the current upper bound. This process may improve forever and can verify a claimed construction, but it cannot announce that no unseen improvement will arrive. The obstacle is not an inadequate search strategy. It is the absence of a computable stopping condition that works for every target and every smaller candidate.

For empirical work, this produces a hierarchy of claims. A compressor, grammar or model can demonstrate a description of stated length. A lower bound may follow within a deliberately finite language, as in the executable census below. Exact Chaitin complexity requires ruling out an open-ended computational universe and is generally unavailable. Reporting these three levels separately prevents an experiment with a practical codec from being mistaken for a solution to the shortest-programme problem.

A finite description census

The demonstration below does not calculate Chaitin’s L. It searches a deliberately finite description family: literal strings, constant strings, alternating strings, repeated blocks up to length four, and simple bitwise complements. Because the catalogue is finite and every candidate terminates, the smallest discovered description is computable. The exercise exposes the counting mechanism while keeping its limitation visible.

How to inspect it. Enter a binary string and run the census. The programme reports the best toy rule, its encoded cost, literal cost and the proportion of equal-length strings compressible under the same toy catalogue. A positive saving permits only the claim that this catalogue found structure. No saving means the catalogue failed, not that the string is algorithmically random. The artefact omits non-halting programmes, universal simulation and state-table encodings, so it cannot establish L(S), K(S), physical randomness or predictive security.

The catalogue makes its accounting inspectable. A literal rule pays for every bit. A constant or alternating rule pays for a rule tag, its starting symbol and the requested length. A repeated-block rule pays for the block as well as its repetition count. Complementing a recognised rule adds another operation. These prices are pedagogical rather than canonical, but they stop the display from awarding a free, infinitely expressive command to whichever pattern happens to be noticed.

Try three contrasts. The string 000000000000 should select a constant rule. The string 010101010101 should favour alternation or a repeated two-bit block. An irregular twelve-bit input may remain literal. Then alter one bit in the alternating record. Its cheapest toy explanation can jump sharply even though the Hamming distance is one. That discontinuity is a property of the catalogue: descriptions are organised by executable rules, not by visual distance alone. A richer language might encode “alternate except at position seven” cheaply.

The reported compressible proportion replays the pigeonhole argument inside a closed world. The script enumerates every string of the selected length, finds the cheapest rule in the same catalogue and counts how many beat literal quotation. Unlike Chaitin’s general setting, every candidate is known to terminate and the finite search is exhaustive. The result is therefore exact for this toy language. Its very tractability marks the boundary: the general theory becomes noncomputable when arbitrary programmes and their unbounded runtimes enter the contest.

The built-in tests check one constant case, one alternating case and one literal comparison before reporting success. They verify that the demonstration’s advertised mechanisms execute; they do not validate the historical theorem. That separation is deliberate. The mathematics rests on the cited machine analysis and proofs, while the browser artefact offers a finite analogy whose assumptions can be inspected and changed.

What the 1966 paper earns, and what later theory repairs

The paper earns a powerful shift of viewpoint. Information can be asked of an individual finite object, not only of an ensemble. Pattern can be priced by the least generative machinery. Counting proves that near-maximal objects dominate. Explicit constructions calibrate the maximum. Local control restrictions reveal why composability depends on programme architecture. Noncomputability appears inside the measure rather than as an external inconvenience.

Several boundaries matter. First, state count is model-dependent at finite sizes. Changing the alphabet, transition convention or transfer bound changes values. The paper controls this by fixing a family and studying leading asymptotics. Kolmogorov’s optimal-machine theorem and later universal-machine formalisms provide a different sort of stability, usually up to an additive constant.

Second, simplicity is not speed. A tiny machine may run for an astronomical duration. Chaitin explicitly distinguishes the number of arbitrary programme choices from ease of prediction. Cook’s 1971 paper, next after this cluster, turns towards resource-bounded difficulty. Description complexity and computational complexity answer different questions.

Third, incompressibility is not semantic importance. A corrupted file may contain more algorithmic information than a carefully organised theorem, yet be less useful. A concise scientific law gains authority only when evidence supports it. Programme length formalises parsimony; it does not replace observation, likelihood, causal testing or meaning.

Fourth, the mature prefix-free theory should not be backdated. The 1966 article analyses ordinary and bounded-transfer state complexity. The 1969 sequel develops statistical properties and binary programmes. The 1975 paper introduces self-delimiting programmes, algorithmic probability and identities resembling Shannon theory. Chaitin later regarded that self-delimiting framework as the mature version.

Recovering the argument without memorising notation

Where this paper changes the path through the canon

Paper 0007 remains in Stage S0, module S0M1: first-principles computability, algorithms and information theory. Church and Turing established limits on effective procedure. Shannon separated information from meaning at the level of distributions. Solomonoff used programme descriptions to weight predictive theories. Kolmogorov defined information in individual objects. Chaitin’s 1966 contribution is to work through finite-string programme length with concrete Turing-machine architectures and to connect the hardest equal-length strings with patternlessness.

The closest prerequisites are Paper 0002 for Turing machines, Paper 0003 for bit counting and compression, Paper 0005 for description-based induction, and Paper 0006 for algorithmic information. The new capability is a proof discipline for individual objects: count descriptions, construct an upper bound, identify the machine assumptions, and price the undecidable remainder.

The next three papers are tightly chosen. Paper 0008, Cook (1971), separates description economy from the time required to establish a result and introduces polynomial reducibility. Paper 0009, Chaitin (1975), supplies the self-delimiting programme theory and information identities that the 1966 state measures do not yet possess. Paper 0010, Valiant (1984), asks what can be learned efficiently from examples, bringing resource bounds and probabilistic success into the picture.

The durable lesson

A pattern is not merely something a viewer happens to notice. Chaitin makes it a contest among executable explanations. The contest has a firm combinatorial backbone: short explanations are scarce, so most objects evade them. It also has an irreducible blind spot: the winning explanation cannot be found by a general total algorithm. Any practical claim of simplicity therefore carries three labels, whether stated or hidden: the description language, the search budget and the evidence that the proposed rule actually generates the object.