# (reference request) Chaitin's constant is incompressible

I've been looking for a full, detailed proof that Chaitin's constant is incompressible, i.e. there is a universal constant $c$ such that every program writing first $n$ digits of $\Omega$ has length at least $n-c$. I wasn't able to find such detailed proof, so I'm asking this question.

-

Although this is not the “detailed proof” you seek, you might still find Chaitin’s own reasoning interesting, as articulated in his Scientific American article “The Limits of Reason” (PDF):

# Why Is Omega Incompressible?

I wish to demonstrate that omega is incompressible— that one cannot use a program substantially shorter than $N$ bits long to compute the first $N$ bits of omega. The demonstration will involve a careful combination of facts about omega and the Turing halting problem that it is so intimately related to. Specifically, I will use the fact that the halting problem for programs up to length $N$ bits cannot be solved by a program that is itself shorter than $N$ bits (see www.sciam.com/ontheweb).

My strategy for demonstrating that omega is incompressible is to show that having the first $N$ bits of omega would tell me how to solve the Turing halting problem for programs up to length $N$ bits. It follows from that conclusion that no program shorter than $N$ bits can compute the first $N$ bits of omega. (If such a program existed, I could use it to compute the first $N$ bits of omega and then use those bits to solve Turing’s problem up to $N$ bits— a task that is impossible for such a short program.)

Now let us see how knowing $N$ bits of omega would enable me to solve the halting problem—to determine which programs halt—for all programs up to $N$ bits in size. Do this by performing a computation in stages. Use the integer $K$ to label which stage we are at: $K= 1, 2, 3,...$

At stage $K$, run every program up to $K$ bits in size for $K$ seconds. Then compute a halting probability, which we will call $\mathrm{omega}_K$, based on all the programs that halt by stage $K$.

$\mathrm{Omega}_K$ will be less than omega because it is based on only a subset of all the programs that halt eventually, whereas omega is based on all such programs.

As $K$ increases, the value of $\mathrm{omega}_K$ will get closer and closer to the actual value of omega. As it gets closer to omega’s actual value, more and more of $\mathrm{omega}_K$’s first bits will be correct—that is, the same as the corresponding bits of omega.

And as soon as the first $N$ bits are correct, you know that you have encountered every program up to $N$ bits in size that will ever halt. (If there were another such $N$-bit program, at some later-stage $K$ that program would halt, which would increase the value of $\mathrm{omega}_K$ to be greater than omega, which is impossible.)

So we can use the first $N$ bits of omega to solve the halting problem for all programs up to $N$ bits in size. Now suppose we could compute the first $N$ bits of omega with a program substantially shorter than $N$ bits long. We could then combine that program with the one for carrying out the $\mathrm{omega}_K$ algorithm, to produce a program shorter than $N$ bits that solves the Turing halting problem up to programs of length $N$ bits.

But, as stated up front, we know that no such program exists. Consequently, the first $N$ bits of omega must require a program that is almost $N$ bits long to compute them. That is good enough to call omega incompressible or irreducible. (A compression from $N$ bits to almost $N$ bits is not significant for large $N$.)

—G.C.

-

This is in Downey and Hirschfeldt: Algorithmic randomness and complexity, Theorem 6.1.3, which cites

Chaitin, G. Information-theoretical characterizations of recursive infinite strings, Theoretical Computer Science, vol. 2 (1976), 45-48.

-
I have two questions: what is $U_s$? I couldn't find the definition anywhere in paper. Second, why does $\Omega_s\uparrow n\neq\Omega\uparrow n$ lead to contradiction? –  Wojowu Aug 1 '14 at 17:26
@Wojowu maybe post that as a separate question, giving more specific page reference –  Bjørn Kjos-Hanssen Aug 1 '14 at 18:17

See Chaitin's very illuminating book http://arxiv.org/abs/math/0404335 (Meta Math! The Quest for Omega).

-

I wrote up the proof for myself about 4 years ago, here it is.

Definition. Fix a universal Turing machine with one program tape and one input tape. Assume that the possible programs are binary numbers none of which is a prefix of another. Call a program $p$ nice if the machine halts with program $p$ and input $p$. Let $C:=\sum_p 2^{-|p|}$, where the sum is over nice programs $p$, and $|p|$ stands for the length of $p$. It follows from Kraft's inequality that $0<C\leq 1$.

Theorem. In order to compute the first $n$ binary digits of $C$, one needs a program of length at least $n-O(1)$.

Proof. Assume that a program of length $k$ computes the first $n$ binary digits of $C$. The set of nice programs is recursively enumerable, hence with a program of length $k+O(1)$ we can find a finite subset $P$ of nice programs for which $\sum_{p\in P} 2^{-|p|}$ agrees with $C$ up to the first $n$ binary digits. It follows that $P$ contains all the nice programs of length at most $n$, hence with a program of length $k+O(1)$ we can decide about programs of length at most $n$ whether they are nice or not. We can modify this program with $O(1)$ bits in such a way that for input $p$ it halts when $p$ is a program of length at most $n$ that is not nice, and it does not halt otherwise. Call this modified program $s$, it has length $k+O(1)$. If the length of $s$ is at most $n$, then we get a contradiction by the definition of niceness and the feature of $s$, namely $s$ is nice if and only if $s$ is not nice. Hence the length of $s$ exceeds $n$, i.e. $k$ is at least $n-O(1)$.

-

The usual argument runs as follows (see for example the books by Li-Vitanyi or Calude): Fix inputs (strings) $x_n$ that produce outputs $0.\Omega_1\ldots \Omega_n$ when fed into a (fixed) universal Turing machine.

As in Chaitin's piece (see Joseph's answer), let's now run the following computation on input $x_n$: dovetail computations on general input $y$ until we've found all halting computations with input lengths $|y|\le n$; we know when we're done with this by our knowledge of the first $n$ bits of $\Omega$, which we compute from $x_n$. Let $z$ be the first string that is not output by any of these computations with input $y$. Then the Kolmogorov complexity satisfies $H(z)> n$ since we constructed $z$ so that no computation on input $y$ of length $\le n$ will output $z$. However, we just computed $z$ from input $x_n$, so $|x_n|\ge n-O(1)$ (the $O(1)$ is contributed by the invariance theorem).

-