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](http://www.umcs.maine.edu/~chaitin/sciamer3.pdf)” (PDF):

   ![GCincomp][1]

---

# 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](http://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.*

  [1]: https://i.sstatic.net/yMViB.png