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.
Thanks in advance!
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):
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.
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).
