In this post, I give a self-contained treatment, including a proof, of the coding theorem.^[1] Let $x$ be a finite binary string and $U$ a universal prefix-free Turing machine. The universal probability $P\left(x\right)$ of $x$ is defined as the probability that a program $p$ sampled uniformly at random computes $x$ when $p$ is run via $U$. The coding theorem says that $P\left(x\right)\approx 2^{-K\left(x\right)}$ up to a multiplicative constant, where $K\left(x\right)$ is the prefix-free Kolmogorov complexity of $x$.^[2] Thus, more complex binary strings $x$ become exponentially less likely and vice versa. This can be interpreted as a form of Occam's razor.

This statement has found some prior interest on Lesswrong. Alexander Gietelink Oldenziel called the argument behind one inequality the padding argument, after it was independently rediscovered by Matthias Dellago and Lucius Bushnaq.^[3] Nate Soares wrote a whole post about his rediscovery of some of these ideas, for the case that strings $x$ are themselves computable functions. A similar result was discussed by Joar Skalse in the context of the complexity of functions learned by neural networks. Note that my usage of the term padding is unrelated to a different type of padding argument.

The motivation of this post is to provide a didactical and elementary proof for readers, avoiding the typical machinery of "lower semicomputable discrete semimeasures", and to have a reference for future posts. In particular, Alexander and I are currently writing a post on the complexity of functions learned by neural networks, in which we would like to refer to this result. 

Audience: This post assumes basic knowledge of Turing machines, the Church-Turing thesis, and the Kolmogorov complexity for prefix-free Turing machines (often called prefix Turing machines; I find it clearer to append "free"). We will briefly recall some basic definitions as a reminder. 

Contributions: It is possible that all parts of the proofs can already be found identically in the literature, but I did not try to find them. OpenAI's o3 found the idea for the dovetailing procedure. The proof of the efficient algorithmic Kraft coding in the appendix is mine. The entire post is written by myself, except the last paragraph of the following section, which was first drafted by GPT-5. 

Acknowledgments: I thank Alexander Gietelink Oldenziel and Matthias Dellago for engaging discussions about the coding theorem and the padding argument. 

Formulating the Coding Theorem

Let $\{0,1\}$ be our alphabet. Denote by $\{0,1{\}}^{\ast }$ the set of binary strings of arbitrary finite length. A prefix-free Turing machine is a Turing machine that halts on a prefix-free set of programs $p\in \{0,1{\}}^{\ast }$. Let $U$ be a universal prefix-free Turing machine, meaning that for any prefix-free Turing machine $T$, there exists $i\in \{0,1{\}}^{\ast }$ such that for all $q\in \{0,1{\}}^{\ast }$ we have $T\left(q\right)=U\left(i^{\prime }q\right)$,^[4] where $i^{\prime }$ is a chosen prefix-free encoding of $i$.  

We construct $P\left(x\right)=P_U\left(x\right)$, the universal a priori probability of $x$, as follows: First, by abuse of notation, consider the uniform distribution $P$ on infinite binary sequences $s\in \{0,1{\}}^{\infty }$, which are sampled by sampling each bit in sequence with probability $1/2$. Now for a particular sampled sequence $s$, we observe whether it starts with a finite sequence $p$ on which $U$ halts, and if it does, then we write $U^{\prime }\left(s\right)=U\left(p\right)$, where $U^{\prime }$ is an adapted version of $U$ that operates on infinite sequences. There can only be one such $p$ since $U$ is prefix-free. Then, define the universal a priori probability of $x\in \{0,1{\}}^{\ast }$ to be

i.e., the probability that $U^{\prime }$ maps a randomly sampled sequence $s\in \{0,1{\}}^{\infty }$ to $x$, i.e., that $s$ starts with a program on which $U$ halts with output $x$. As an aside, note that this is only a semiprobability mass function since some infinite sequences $s$ do not contain any prefix on which $U$ halts, meaning that $U^{\prime }\left(s\right)$ is undefined. Thus, we have 

This total probability is also called the halting probability; it is the probability that a randomly selected program $p$ produces an output and halts. 

For a program $p\in \{0,1{\}}^{\ast }$, denote by $l\left(p\right)$ its length. Then the distribution $P$ also has an alternative and more common formulation:

Lemma 1 (Deadcode/padding argument). We have

Proof. We first claim

The inclusion from left to right is clear: Every infinite $s$ with $U^{\prime }\left(s\right)=x$ by definition starts with a finite program $p$ such that $U\left(p\right)=x$. The other direction is the padding or deadcode argument: If a program $p$ computes $x$ (i.e., $U\left(p\right)=x$), then every extension of $p$ to an infinite sequence $s$ will compute $x$ via $U^{\prime }$: The extensions/paddings are a dead code that is ignored by $U^{\prime }$.

Thus, we obtain

In the last step, we used that the likelihood of sampling an infinite sequence that starts with $p$ is exactly $2^{-l\left(p\right)}$ since each specific bit is sampled with probability $1/2$ under the uniform distribution. $\square$

Now, let $K\left(x\right)$ the Kolmogorov complexity of a binary string $x\in \{0,1{\}}^{\ast }$ computed via the universal prefix-free Turing machine $U$, i.e., the length of the shortest program that computes $x$:

We can now formulate the coding theorem:

Theorem 2 (Coding Theorem). There is a constant $C>0$ such that for all $x\in \{0,1{\}}^{\ast }$, we have

In other words, up to at most a multiplicative constant, $P\left(x\right)$ coincides with $2^{-K\left(x\right)}$. 

Proof (first inequality). Choose a shortest program $p\in \{0,1{\}}^{\ast }$ with $U\left(p\right)=x$. Then we have $l\left(p\right)=K\left(x\right)$ and we obtain $2^{-K\left(x\right)}=2^{-l\left(p\right)}\le P\left(x\right)$ by Lemma 1. $\square$

The rest of the post will be about proving the second inequality, which is much harder than the first. It roughly states that if $x$ is likely under the universal probability, then its Kolmogorov complexity is small, i.e., $x$ can be compressed. To prove this claim, we first reformulate it slightly. Up to a relabeling of $C$, and by taking the binary logarithm, the inequality is equivalent to

The rough outline is as follows: Our proof of this inequality constructs, for each string $x$, a short prefix-free program whose length is close to $-\log P\left(x\right)$, using an online version of Kraft’s inequality: We simulate all programs in parallel (dovetailing) and maintain running lower bounds $Q\left(x\right)$ of $P\left(x\right)$. Whenever $Q\left(x\right)$ first crosses a threshold $2^{-r}$, we assign $x$ a fresh codeword of length $r+1$ via an algorithmic Kraft coding procedure that guarantees prefix-freeness without knowing future codelengths. That this is accomplished by an online algorithm ensures that the decoding procedure is computable by a fixed prefix-free Turing machine, adding only a constant $C$ to the code lengths. Since $r$ is eventually within a distance of $1$ of $-\log P\left(x\right)$, the resulting shortest program length found by the procedure is at most $-\log P\left(x\right)+C+2$, establishing the desired bound with constant $C+2$. 

Algorithmic Kraft Coding

We need an algorithmic version of the Kraft inequality as a tool. If you are not interested in the details, feel free to only read the statement of Theorem 4 and then move on to the next section. 

For a binary string $x\in \{0,1{\}}^{\ast }$, we denote by $0.x$ the corresponding real number in base $2$, with $0\le 0.x<1$. Furthermore, $D\left(x\right):=[0.x,0.x+2^{-l\left(x\right)})$ denotes the corresponding half-open dyadic interval. We say that $y$ is a prefix of $x$ if $x$ starts with the bits of $y$.

Lemma 3. Let $x,y\in \{0,1{\}}^{\ast }$ be binary strings. Then $D\left(x\right)\subseteq D\left(y\right)$ if and only if $y$ is a prefix of $x$.

Proof. Assume $y$ is a prefix of $x$. Then 

All inequalities except the last are trivial. The last inequality follows since adding $2^{-l\left(x\right)}$ to $0.x$ increments only the last bit of $0.x$, which cannot get larger than incrementing an earlier bit — which is what happens by forming $0.y+2^{-l\left(y\right)}$, given that $y$ is a prefix of $x$. Overall, this shows $D\left(x\right)\subseteq D\left(y\right)$.

For the other direction, assume we have $D\left(x\right)\subseteq D\left(y\right)$, i.e., the inequalities in the first equation in the proof all hold. If $0.y=0.x$, then the third inequality shows $2^{-l\left(x\right)}\le 2^{-l\left(y\right)}$, which shows $l\left(y\right)\le l\left(x\right)$, and $0.y=0.x$ implies $x=y{0}^{l\left(x\right)-l\left(y\right)}$. Thus, $y$ is a prefix of $x$ and we are done. Thus, we can assume $0.y<0.x$. For any natural numbers $k$, define $x\left(k\right)$ and $y\left(k\right)$ as the $k$'th bit in the binary expansions of $0.x$ and $0.y$, respectively. Let $k$ be the earliest index where $x\left(k\right)>y\left(k\right)$ (which exists since $0.x>0.y$). We are done if we can show $k\ge l\left(y\right)+1$. And indeed, if this were not the case, then $0.x\ge 0.y+2^{-l\left(y\right)}$, a contradiction to the assumed inequalities. Thus, $k\ge l\left(y\right)+1$, i.e., $y$ is a prefix of $x$. $\square$

Theorem 4 (Algorithmic Kraft Coding). Let $l_1,l_2,\cdots \in \{1,2,\dots \}$ be a sequence of natural numbers. Assume they satisfy Kraft's inequality:

Then there exist codewords $C\left(k\right)\in \{0,1{\}}^{\ast }$ with the two properties that:

1. $C$ forms a prefix-free code, i.e., no $C\left(k\right)$ is the prefix of any $C\left(l\right)$.
2. The codelengths are given by $l\left(C\right(k\left)\right)=l_k$.

Furthermore, there is an algorithm which successively maps the lengths $l_k$ to a codeword $C\left(k\right)$ without looking at future codelengths and without revising earlier codewords along the way. 

Proof.  Here, we present a simple proof that only achieves slightly less efficient codelengths $l\left(C\right(k\left)\right)=l\left(k\right)+1$. In the appendix we present a more complicated algorithm that achieves precisely the stated result.

The algorithm proceeds as follows: Upon receiving the sequence $(l_1,\dots ,l_k)$, form the numbers $s_k={\sum }_{i=1}^{k-1}{2}^{-l_i}$, and analogously $s_{k+1}$. Consider the interval $I_k=[s_k,s_{k+1})$.
To construct the codeword $C\left(k\right)$, go through all binary codewords $x$ of length $l\left(k\right)+1$, lexicographically, until you find the very first one for which $0.x\ge s_k$. This is $C\left(k\right)$.

Now we prove the first property (the second one holds by construction, though with lengths $l\left(C\right(k\left)\right)=l_k+1$). Due to the minimality of $C\left(k\right)$, we have $0.C\left(k\right)<s_k+2^{-(l_k+1)}$. Consequently, we have 

Consequently, the dyadic interval satisfies $D\left(C\right(k\left)\right)\subseteq I_k$. Since all $I_k$ are pairwise disjoint, all $D\left(C\right(k\left)\right)$ are pairwise disjoint, too. By Lemma 3, no $C\left(k\right)$ is a prefix of any other. That proves property 1. Finally, notice that $C\left(k\right)$ was chosen algorithmically without knowledge of future codelengths and without revising any earlier codewords, finishing the proof. $\square$

Remark: The statement of the theorem is stronger than its typical formulation since I require there to be an algorithm that selects one codeword at a time. This is what makes my proof of the efficient codewords in the appendix so complicated. Other proofs I found in the literature assume that the codelengths can be ordered in a non-decreasing way, which isn't possible when receiving one codelength at a time. 

The reverse of this theorem is also true, i.e., the codelengths of any prefix-free code satisfy Kraft's inequality, see the Wikipedia page. 

A Proof of the Coding Theorem

We now prove the second inequality of Theorem 2. Recall that we want to prove

We now explain how to code binary strings $x$ algorithmically to a code of length roughly $-\log P\left(x\right)$ to achieve this. Crucially, we can't compute $-\log P\left(x\right)$ precisely and can only approximate it, leading to a moving target for the codelengths for $x$, and so we have to code $x\in \{0,1{\}}^{\ast }$ in several ways since we can never be sure if we have found the correct codelength already.

We proceed as follows: For all $x\in \{0,1{\}}^{\ast }$, initialize $Q\left(x\right):=0$ as an approximation to $P\left(x\right)$. Initialize an empty sequence $\left(\right)$ of codelengths. We approximate $P\left(x\right)$ from below. We do this by dovetailing: Run all inputs $p$ in parallel through the universal Turing machine $U$, one algorithmic step at a time. Assume our list of codelengths already contains $(l_1,\dots ,l_{k-1})$ at some algorithmic step. Whenever any program halts and computes $U\left(p\right)=x$ for any binary string $x$, update the estimate $Q\left(x\right)$:

When this happens, check whether $Q\left(x\right)$ just crossed a threshold $2^{-r}$ for any natural number $r$ for the first time. If it did, then for the smallest such $r$ (if it crosses several at once), append $l_k:=r+1$ to a sequence $(l_1,\dots ,l_{k-1})$ of codelengths to obtain $(l_1,\dots ,l_k)$, and assign to $x$ a codeword of length $l_k$ via the algorithm from Theorem 4.

For this to be well-defined, we need to check that all the codelengths $l_1,l_2,\dots$ together satisfy Kraft's inequality. Notice that each $l_i$ is of the form $r+1$ for an $r$ with$2^{-r}\le Q\left(x\right)\le P\left(x\right)$ for some binary string $x$, and that no $r$ appears twice for a given $x$ since we only update the list if a threshold is crossed for the first time. For a given $x$, let $r_x$ be the minimal $r$ that eventually appears in the algorithm and satisfies $2^{-r}\le Q\left(x\right)$. Thus, we have

Thus, algorithmic Kraft coding can indeed be applied.

Now, if you have a codeword $p$ that arose from this procedure, you can decode $p$ to $x$ algorithmically as follows: Just run the same procedure again and observe which binary string $x$ will be coded as $p$. Then, halt and output $x$. Since this procedure halts only on outputs of the above encoding, and these outputs form a prefix-free set by Theorem 4, the decoding procedure described here halts on a prefix-free set, and so it is given by a prefix-free Turing machine (where we make use of the Church-Turing thesis). Let $T$ be this Turing machine. Thus, there exists a Turing machine index $i\in \{0,1{\}}^{\ast }$ such that $U\left(i^{\prime }q\right)=T\left(q\right)$ for all $q\in \{0,1{\}}^{\ast }$. Consequently, we have $U\left(i^{\prime }p\right)=T\left(p\right)=x$, and thus

where $C=l\left(i^{\prime }\right)$ is a constant independent of $x$ and $p$.

Now, note that for a given $x$, in the encoding procedure, we eventually reach the minimal $r_x$, which then satisfies $2^{-r_x}\le P\left(x\right)\le 2^{-(r_x-1)}$ since otherwise $Q\left(x\right)$ would eventually cross the threshold $2^{-(r_x-1)}$, contradicting the minimality of $r_x$. Thus, there exists some minimal code $p$ such that 

Combining with the previous equation, we obtain

finishing the proof of Theorem 2. $\square$

Appendix: Proof of Efficient Algorithmic Kraft Coding

Here, we present a more complicated algorithm that achieves the efficient codelengths $l\left(C\right(k\left)\right)=l_k$ for Theorem 4. Start with the set $R_0=\{0,10,110,1110,\dots \}\subseteq \{0,1{\}}^{\ast }$ of codewords.^[5] Intuitively, we think of them as a "resource" from which we choose the codewords of length $l_k$. Whenever this resource does not have a codeword of the correct size available, we fractally "break up" the longest available shorter string into longer strings in a prefix-free way, assign one of them, and add the new remaining "pieces" back into the resource in a way that does not create any "waste".

We now explain the details of how to do this. Initialize the set of "found codewords" $F_0$ as the empty set $F_0=\varnothing$. Note that $R_k$ and $F_k$ have the following properties for $k=0$:

1. $R_k$ is prefix-free.
2. $F_k=\left\{C\right(1),\dots ,C(k\left)\right\}\subseteq R_k$, and the codelengths are given by $l\left(C\right(i\left)\right)=l_i$ for $i=1,\dots ,k$.
3. No codelength is represented more than once in $R_k\setminus F_k$.
4. ${\sum }_{r\in R_k}{2}^{-l\left(r\right)}=1$.

In the course of this proof, we will progressively replace elements of $R_k$ with extensions and build up the desired codewords $F_k$ algorithmically while preserving all four properties. The fact that $R_k$ is prefix-free by property $1$ and that $F_k\subseteq R_k$ by property $2$ then shows that also $F_k$ is prefix-free, which then implies that the code $C$ is prefix-free, establishing the result. 

Let $k=1$. As $C\left(1\right)$, choose the unique $r\in R_0$ with $l\left(r\right)=l_1$. This exists since $R_0$ contains one codeword for each codelength. Set $R_1:=R_0$ and $F_0:=\left\{C\right(1\left)\right\}$.
Note that all four properties still hold for $k=1$.

Now, assume by induction that $R_{k-1}$ and $F_{k-1}=\left\{C\right(1),\dots ,C(k-1\left)\right\}$ are already constructed and that all four properties hold. If there is an $r\in R_{k-1}\setminus F_{k-1}$ with $l\left(r\right)=l_k$, then simply choose $C\left(k\right)=r$, $F_k=F_{k-1}\cup \left\{C\right(k\left)\right\}$ and $R_k=R_{k-1}$. The choice of $r$ is unique by property $3$. Then trivially, all four properties are preserved.

Finally, consider the case that there is no $r\in R_{k-1}\setminus F_{k-1}$ with $l\left(r\right)=l_k$. Define $r\in R_{k-1}\setminus F_{k-1}$ as the longest element with $l\left(r\right)<l_k$. It is unique by property $3$. It exists since otherwise $R_{k-1}\setminus F_{k-1}$ does not represent any of the codelengths $1,2,\dots ,l_k$, which by induction and properties $2$, $4$, and $3$ (in that order) would imply

This would result in

in contradiction to the assumed Kraft's inequality. Thus, $r\in R_{k-1}\setminus F_{k-1}$ with $l\left(r\right)<l_k$ (and maximally long with these properties) exists.

Now, set $n:=l_k-l\left(r\right)>0$. Define

Define $C\left(k\right):=r{1}^n$ and $F_k:=F_{k-1}\cup \left\{C\right(k\left)\right\}$.

We now show that all four properties remain true with these constructions. The newly added elements in $R_k$ are clearly not prefixes of each other. Since they are all extensions of $r\in R_{k-1}$ and $R_{k-1}$ was prefix-free, the prefix-free property then follows for all of $R_k$, proving property $1$. For property $2$, note that $F_{k-1}\subseteq R_{k-1}$, and since $r\notin F_{k-1}$ by definition, we have $F_{k-1}\subseteq R_k$, too. $C\left(k\right)\in R_k$ by construction, and so $F_k\subseteq R_k$. We have $l\left(C\right(k\left)\right)=l\left(r\right)+l\left(1^n\right)=l\left(r\right)+n=l_k$, proving property $2$.

For property $3$, note that

Thus, codelength $l\left(r\right)$ is removed from and codelengths $l\left(r\right)+1,\dots ,l\left(r\right)+n=l_k$ are added to $R_{k-1}\setminus F_{k-1}$. By construction of $r$ (i.e., its maximality), none of the newly added codelengths were present in $R_{k-1}\setminus F_{k-1}$, and so no codelength is represented more than once in $R_k\setminus F_k$, proving property $3$.

Property $4$ follows from Equation $(\ast )$ and the induction assumption for $k-1$:

As we explained before, this concludes the proof. $\square$

1. ^{^}

   See Theorem 4.3.3 in Li and Vitányi's "An Introduction to Kolmogorov Complexity and Its Applications". This was first proved by L.A. Levin in 1974.

2. ^{^}

   Importantly, this result is only correct up to a logarithmic error for plain, or descriptional, Kolmogorov complexity. Thus, the assumption that we work with prefix-free Turing machines is crucial. Thanks to Daniel Filan for pointing that out. 

3. ^{^}

   The term "padding" is also used in this context in the book "An Introduction to Universal Artificial Intelligence" by Hutter, Quarel, and Catt.

4. ^{^}

   In particular, $T$ halts on $q$ whenever $U$ halts on $i^{\prime }q$.

5. ^{^}

   My guess is one could also start with the resource $R_0=\left\{ϵ\right\}$ consisting of only the empty binary string, which would possibly be somewhat cleaner than the choice I made.