The parcel with no seam

A receiver gets the bit stream 0110111. Two programmes were sent back to back, but the envelope has no seam. If 01 is a complete programme, should the remaining 10111 begin the second? If 011 is complete instead, the split moves. A blank after each programme would settle the issue, yet that blank is an extra symbol outside the binary channel. The sender has claimed seven bits while quietly borrowing punctuation.

Chaitin’s 1975 paper begins from this engineering-sized defect and turns it into a mathematical redesign. Earlier programme-size complexity measured an object by the shortest binary programme that produces it. That idea captures a durable intuition: a regular string can be generated by a short instruction, while a patternless string may need to be quoted almost verbatim. Yet the natural algebra of information asks for more than a ranking of strings. It asks whether descriptions can be combined, conditioned and assigned probability without hidden boundary costs.

Suppose a shortest programme for object A has length a and one for B has length b. It is tempting to concatenate them and announce that the pair has a description of a+b bits. The decoder, however, must know where the first ends. A language with an external endmarker makes that fact available for free. A binary stream with no endmarker does not. Encoding the first length costs additional bits, and repeating that manoeuvre across nested descriptions can make the error grow with the objects.

That is why the paper’s title says “formally identical to information theory”. Chaitin does not claim that an individual string is a random variable, or that its programme length equals Shannon entropy. He seeks a programme-size quantity whose equations have the same shape as entropy equations, within a constant independent of the particular strings. The constant may depend on the chosen universal machine. The decisive question is whether the error stays bounded as the objects grow.

A set of binary words is prefix-free when no member is the beginning of another member. The set {0, 10, 110, 111} qualifies. Once the decoder reads 0 it may stop, because no valid word begins 0 and continues. After reading 10 it may stop for the same reason. By contrast, {0, 01, 11} fails: 0 is a valid word and also begins 01. Prefix-freeness is stronger than merely having different words, and it makes termination visible without a separator.

Chaitin defines a computer as a partial computable function C(p,q), with programme p and free auxiliary data q, whose halting programmes form a prefix-free set for every fixed q. “Partial” matters because some bit strings may never yield an output. “For every fixed q” matters because auxiliary knowledge can change what a programme does. The semantic act of halting, not the typography of a source file, determines which bit strings enter the code.

The same calculation exposes a failed code. For {0, 01, 11}, the numerical sum is 1/2 + 1/4 + 1/4 = 1, yet the tree regions for 0 and 01 overlap because 01 lies below 0. Kraft’s inequality says valid prefix-free lengths have total mass at most one; satisfying the inequality for a list of lengths means some prefix code with those lengths exists. It does not rescue an arbitrary assignment of words whose branches collide.

A tree that spends probability

Write every finite binary string as a node in an infinite tree. Reading 0 takes the left branch and reading 1 the right. A word of length k roots a cylinder containing all infinite streams that begin with it. Under fair independent bits, that cylinder has measure 2^−k. If valid programmes are prefix-free, their cylinders do not overlap. The total measure of all halting programmes can therefore never exceed one.

This is the geometric heart of the paper. A syntactic boundary rule becomes a conservation law. Short programmes occupy large regions because many random streams share their prefix. Long programmes occupy small regions. Once a region is allocated to a halting word, none of its descendants may be allocated. Programme length is now a legitimate negative logarithm of measure rather than a tally attached to an externally punctuated file.

An equivalent picture cuts the unit interval. The first bit divides [0,1) into two halves, the second divides each half again, and so forth. Word 10 corresponds to [1/2,3/4); word 110 to [3/4,7/8). A prefix-free machine allocates disjoint dyadic intervals. This picture carries Chaitin’s Kraft construction: if a recursively enumerable list asks for codewords of lengths n₁, n₂, … and the requested masses sum to at most one, a computer can allocate compatible words.

Chaitin’s proof is constructive in a carefully limited sense. Requirements can arrive over time because halting computations can be enumerated. The allocator assigns the earliest available interval of the requested size. It never frees storage. The binary expansion of the remaining measure records which block sizes remain possible. This is not a practical memory manager; it is a way to turn lower bounds on probability into actual prefix programmes.

The allocation theorem has two directions worth separating. Necessity is immediate once codewords are drawn as disjoint intervals: their lengths cannot sum beyond the unit interval. Sufficiency is the deeper claim. If an enumerable request list obeys the mass budget, a greedy dyadic allocator can realise those requested lengths as an actual prefix-free domain. Thus a numerical inequality becomes a programme constructor. Later proofs may specify desired lengths first and rely on the theorem to supply codewords afterwards.

That reversal is easy to miss. Chaitin does not begin each proof by guessing the bits of a short programme. He shows that certain probability estimates generate a consistent list of length requests. Kraft allocation builds a machine meeting those requests, and universality transfers its descriptions to U for a fixed surcharge. The technique lets measure-theoretic bounds do programme-design work indirectly. It is one reason the 1975 theory yields sharper identities than a direct search through arbitrary binary descriptions.

The word “probability” needs discipline here. Chaitin imagines feeding a computer an infinite stream of fair random bits. The probability that it halts after consuming exactly programme p is 2^−|p|. Prefix-freeness ensures that different halting programmes describe disjoint events. Some streams may never trigger a halt, so the total output mass can be less than one. The result is a semimeasure, not necessarily a probability distribution that sums exactly to one.

The halting probability Ω is the total mass of the universal machine’s halting programmes. The 1975 paper defines it while building the programme-size calculus, but its full randomness and incompleteness roles belong to adjacent work. For this paper, Ω first confirms that self-delimiting programme weights converge. It should not be treated as a mystical constant detached from a particular universal machine.

The universal decoder

A complexity measure needs a reference computer. One language may describe repeated zeros with a primitive instruction; another may require a loop. If arbitrary language choice could change description length without limit, shortest programme size would measure notation rather than information. The invariance remedy is a universal computer U that simulates every prefix-free computer C with a fixed header whose length depends on C, not on the object being described.

Formally, whenever C(p,q) produces s, U has some programme p′ with the same auxiliary data q, the same output s, and |p′| ≤ |p| + sim(C). The simulation constant includes the interpreter or compiler for C. Once C is fixed, that tax does not grow with s. Large-scale comparisons therefore survive a change of universal language up to an additive constant.

Choose one such U as standard. Chaitin defines H(s) as the shortest U-programme length producing s with empty auxiliary data. If several shortest programmes exist, a lexical rule selects the canonical one s*. This canonical representative carries more than the object: its own length is visible once the entire self-delimiting programme has been read. That small detail later becomes essential to conditional information.

The constant prevents asymptotic chaos, not small-scale arbitrariness. A perversely designed universal machine can reserve a one-bit programme for a favoured string and use a huge interpreter for everything else. H of that string then differs sharply across machines. Serious uses either reason beyond fixed constants, fix a concrete machine, or study relations robust enough to tolerate them. “Machine-independent” always means invariant up to this additive convention, not numerically identical.

Chaitin’s universal construction uses LISP machinery and a watchdog that enforces self-delimitation. The implementation is historically revealing but not the theorem’s lasting burden. What matters is that prefix-free machines can be effectively enumerated and simulated with fixed overhead. Modern accounts often write K for this prefix complexity. This companion retains H where it follows the paper and uses “prefix complexity” to distinguish it from plain, blank-endmarker complexity.

From length to probability

The shortest programme gives one route to an output. Random input may reach the same output through many longer programmes as well. Chaitin defines algorithmic probability P(s) by adding 2^−|p| over every U-programme p that produces s. The shortest programme contributes at least 2^−H(s), so P(s) cannot be smaller than that term. The difficult direction asks whether a swarm of longer descriptions can make P(s) far larger.

Kraft allocation supplies the answer. Because lower bounds on P(s) can be enumerated from observed halts, one can request a fresh programme whose length is approximately −log₂P(s). The requested masses remain within one unit. Universality then says U can simulate this allocation with fixed overhead. Probability cannot accumulate around s without licensing a correspondingly short U-description.

This is the paper’s coding theorem. A one-bit decrease in description length corresponds to roughly doubling algorithmic probability. A ten-bit decrease corresponds to a factor near 1,024. The relationship is only within multiplicative constants on the probability side and additive constants on the complexity side. Still, it transforms proofs: length inequalities can be derived through measure and then translated back to programmes.

To see the two inequalities, start with the shortest programme p*. Its single contribution makes P(s) at least 2^−H(s), so −log P(s) cannot exceed H(s). For the other direction, enumerate increasingly strong lower bounds on P(s). Whenever the mass passes a dyadic threshold 2⁻ⁿ, request a codeword of roughly n bits for s. The total requested mass remains bounded because the output masses do. A universal machine simulates the resulting decoder, giving H(s) no more than −log P(s) plus fixed overhead.

The proof also explains why the sum includes every programme, not just a selected shortest one. The shortest contribution supplies only one inequality. The reverse direction needs accumulated mass to trigger a length request even when no individual observed programme is short enough. The coding theorem says that a large cloud of descriptions cannot conceal its information advantage. Universal allocation condenses the cloud into one comparably short description, up to the interpreter constant.

The theorem does not assume that a human chose s from a known ensemble. P is generated by a universal computing process, and H concerns one finite object. Shannon entropy instead averages surprise under a specified source distribution. The two theories share code-length geometry, but they answer different questions. Confusing them can turn an expectation over outcomes into a claim about the shortest effective description of one observed outcome.

Nor is P computable. Halting programmes can be discovered, so its lower estimates rise over time. No general procedure knows when all relevant programmes have appeared. The same obstruction prevents exact H from being calculated: finding a short programme proves an upper bound, but proving that no shorter programme will ever halt with the same output requires solving a halting-shaped negative question.

The chain rule needs the right gift

Classical information theory decomposes joint information into information in one variable plus conditional information in the other. Programme-size complexity wants the analogous statement H(s,t)=H(s)+H(t|s)+O(1). Prefix-free concatenation proves the easy inequality: attach a shortest self-delimiting programme for s to a shortest programme that computes t from the relevant auxiliary description, and a decoder can find the seam.

The reverse inequality is subtler. Giving the raw object s does not reveal how many bits its shortest description uses. A joint shortest programme may distribute information between “the s part” and “the rest” in a way that cannot be recovered with constant advice from s alone. Chaitin therefore defines conditional complexity H(t/s) using s*, a canonical shortest self-delimiting programme for s, as the free condition.

This gift contains s because running s* produces s. It also contains H(s) because self-delimitation reveals |s*|. That extra metainformation closes the chain rule within O(1). Modern notation often writes K(t | s, K(s)) or K(t | s*) to make the convention explicit. Writing only K(t|s) and claiming a constant-error identity silently drops the very repair the paper introduced.

The proof architecture alternates programme construction and probability. One direction concatenates two self-delimiting subroutines. The other allocates conditional programmes based on joint probability mass relative to the marginal for s. Universality converts the allocated code back to U with fixed overhead. This route is more than elegance: direct attempts to cut an unknown shortest joint programme at the correct point would smuggle in the boundary one is trying to prove.

For the upper bound, let s* be the canonical shortest description of s and let p be shortest for t with s* supplied. A prefix reader consumes exactly s*, then starts a second prefix reader on p. Their concatenation is itself self-delimiting and produces the ordered pair. This gives H(s,t) no more than H(s)+H(t/s), apart from the fixed pairing interpreter. The argument works because neither component needs a length field placed ahead of it.

The lower bound asks for a conditional description whose size is the joint cost minus H(s). Joint programmes producing pairs with first component s occupy total mass comparable to P(s). Rescale those programme weights by roughly 2^H(s); the coding theorem keeps the resulting conditional requests within the Kraft budget. The allocator then gives t a code of the desired difference length when s* is free. This is the point at which knowing H(s) through |s*| performs real work.

Conditional algorithmic probability follows the same starred convention. P(t/s) sums the masses of programmes producing t when given s*. The paper then obtains P(t/s) within a constant factor of P(s,t)/P(s). Taking negative logarithms yields the chain rule. This is the promised formal resemblance to conditional probability, but “within a constant factor” remains essential.

Shared algorithmic information

Two objects share algorithmic information when describing them together is cheaper than describing them separately. Chaitin defines the saving as H(s)+H(t)−H(s,t), within the paper’s bounded identities. The chain rule shows that this is also H(t)−H(t/s) up to a constant: how much a shortest description of s helps compute t. Symmetry of joint complexity then makes the saving nearly symmetric between s and t.

This is dependence without a sampling distribution. Two identical long strings share almost all their programme-size information. Two independent incompressible strings share little, even if both contain roughly half zeros. A string and its cryptographic-looking computable transformation may share substantial algorithmic information because a short reversible rule converts one to the other. Surface resemblance is neither necessary nor sufficient.

Consider a 10,000-bit bitmap and the same bitmap shifted one pixel right. Pixel-by-pixel comparison reports many changed positions, but a short transformation plus one boundary rule maps one object to the other. Their shared algorithmic information is therefore high relative to their individual complexities. Conversely, two files may share a long common header yet have independent bodies. Byte overlap exaggerates their deeper dependence.

The symmetry is not magic. H(s,t) and H(t,s) differ only by a fixed pairing routine. The starred chain rule writes the same joint description in two orders. Subtracting from the separate complexities yields approximately equal savings. The constant absorbs pairing conventions, universal simulation and the chosen canonical shortest programmes.

Later information-distance work turns this saving into a transformation cost: how much information is required to convert one object into another and back. Practical compression distances approximate related ideas, but they replace an incomputable universal machine with a real compressor. Their output depends on compressor design, window size, file format and scale. Chaitin’s theorem licenses the conceptual target, not every empirical proxy.

Prefix-code laboratory

The laboratory below checks a finite codebook. It tests whether every word is binary and whether any accepted word prefixes another. It then calculates Kraft mass and greedily decodes a message when the code is prefix-free. This exposes the paper’s boundary mechanism in a form that can fail visibly. It does not search universal programmes, decide halting or calculate exact H, P or Ω.

Run the default set. Its Kraft mass is one and the message decodes as 0 | 10 | 110 | 111. Replace the codebook with 0,01,11. The tool flags the 0/01 prefix collision and refuses greedy decoding, even though the length masses add to one. Replace it with 00,01,10. The code is prefix-free with mass three quarters, so one quarter of the infinite input space remains unallocated.

A positive result permits only a local conclusion: this finite set has recoverable boundaries and consumes the reported dyadic mass. A negative result locates either invalid symbols, a duplicate, a prefix collision or an undecodable suffix. The test assumes a finite explicit codebook and fair independent input bits. A real prefix-free universal computer has an infinite recursively enumerable halting domain, much of which cannot be known in advance.

What the identity does not buy

The paper earns a calculus, not an oracle. Exact H is upper semicomputable: enumerate programmes, run them by dovetailing, and keep the shortest discovered description for each output. The estimate may fall whenever a shorter programme halts. No computable stopping rule generally certifies that the current candidate is minimal. Algorithmic probability is approximable from below for the same reason, but its missing mass cannot be bounded effectively in general.

This limitation is not an implementation inconvenience awaiting faster hardware. A reliable exact solver would decide questions equivalent to halting. Paul Vitányi’s later analysis sharpens the practical warning: approximation schemes may be useful, but one usually cannot know their distance from K for arbitrary data. A compressor demonstrates a description and hence an upper bound. It does not demonstrate optimality.

The second boundary is machine dependence. The invariance theorem controls changes by additive constants, which is powerful for asymptotic statements and impossibility results. It does not supply a privileged universal machine. Concrete applications must disclose the description language or use a robustness argument across reasonable choices. Otherwise an unexplained constant can dominate the quantity being compared.

The third boundary concerns “formally identical”. Shannon entropy H(X) is an expectation determined by a probability distribution over outcomes. Chaitin’s H(s) is a shortest effective description length for one finite object under a fixed universal machine. Expected prefix complexity can relate to entropy under computable sources, but the objects, quantifiers and error terms differ. Algebraic resemblance does not erase that distinction.

The fourth boundary is time. A tiny programme may require astronomical runtime. Programme-size complexity values brevity alone. A short exhaustive search can describe an output that no feasible observer can obtain. Time-bounded complexity, logical depth and practical compression introduce other resource questions. They are successors, not results of the 1975 theorem.

The fifth boundary is interpretation. An incompressible finite string need not have been produced by a physical random process. A deterministic but hidden mechanism may generate outputs that resist the chosen description language at the observed scale. Conversely, a genuinely stochastic source can emit a simple run of zeros. Algorithmic incompressibility is a property of descriptions, not a complete causal diagnosis.

A sixth boundary concerns conditioning. Auxiliary data is free by definition, so moving information across the slash can change complexity drastically. H(t/s) is small when s* contains an effective route to t, yet that does not mean an actual observer possesses s*, can recognise it as shortest, or can compute the route efficiently. Conditional complexity is a counterfactual description budget under exact side information. Treating it as a measured cognitive or storage cost requires an additional bridge.

Chaitin also derives a sharper finite-string maximum than the naive “about n bits”. Under self-delimiting complexity, an n-bit string can require n+H(n)+O(1) bits because a self-contained description must convey the length scale as well as the payload. Most n-bit strings lie near the appropriate ceiling in a counting sense. This extra H(n) term is one price of honest boundaries and another reason to distinguish prefix complexity from plain complexity.

That result should not be paraphrased as “random strings are longer than themselves” without explanation. The raw string can be copied if its length arrives as free data. A standalone self-delimiting programme must also tell the decoder when the copied material ends. Conditioning on n removes much of that overhead. The apparent paradox disappears once the information boundary is stated.

The strongest rival reading is therefore not that the theory fails, but that its clean identities depend on deliberately chosen conventions: prefix-free machines, canonical shortest descriptions and bounded machine constants. Chaitin makes those choices explicit and proves what they buy. Later presentations sometimes hide the star or blur the Shannon distinction. Faithfulness requires keeping the conventions visible because they are the intellectual move, not technical debris.

Memory studio

Teach-back test. Without using the words “entropy”, “Kolmogorov” or “prefix”, explain why a shortest instruction needs a recoverable stopping point before its length can behave like probability. Then explain why knowing an object is not always the same as knowing the length of its shortest instruction.

Place in the canon

Paper 0009 sits in Stage S0, module S0M1, after the canon has established computability, communication, induction, programme-size complexity and computational difficulty. Church and Turing supply the unsolvability boundary. Shannon supplies prefix-code geometry and information measured in bits. Solomonoff supplies algorithmic probability as an inductive idea. Kolmogorov and Chaitin’s 1966 paper supply shortest-description complexity. The 1975 paper fuses these strands by changing the programme domain.

The earlier question it answers is precise: how can programme-size complexity support a stable calculus of joint, conditional and mutual information? Its new capability is not merely a new symbol H. It is the ability to concatenate descriptions without hidden separators, allocate their lengths as disjoint measure, and recover information-theoretic identities within fixed constants.

The strongest successor branch develops prefix complexity into algorithmic randomness, universal semimeasures, minimum description length, algorithmic statistics and information distance. The strongest corrective branch insists on the distinctions this paper can tempt readers to erase: individual-object complexity versus ensemble entropy, universal ideals versus computable compressors, and short descriptions versus feasible computations.

The paper’s professional relevance is narrow but real. Any claim that a compressor, model code or similarity metric measures “intrinsic information” should be checked against Chaitin’s boundary conditions. Which machine is fixed? Is the code self-delimiting? Is the reported number an upper bound, an expectation, or a universal ideal? Are runtime and data access free? Those questions prevent a theorem about descriptions from becoming an unsupported performance metric.

The original thesis of this companion is that self-delimitation is an accounting rule for computational knowledge. It decides which bits belong to a claim, which arrive free as context, and whether two claims reuse the same description. Chaitin’s formal identities work because the accounting boundary is built into the machine. Remove the boundary, and the apparent information savings may be borrowed punctuation.

What should now read differently? When an equation adds information quantities, inspect the seams. When a conditional term appears, ask exactly what the condition contains. When a universal measure is approximated, separate the discovered upper bound from the unreachable optimum. Chaitin’s 1975 achievement is to make these bookkeeping choices mathematical enough that their consequences can be proved.