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): <blockquote><h1>Why Is Omega Incompressible?</h1><p> I wish to demonstrate that omega is incompressible—that one cannot use a program substantially shorter than <i>N</i> bits long to compute the first <i>N</i> 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 <i>N</i> bits cannot be solved by a program that is itself shorter than <i>N</i> bits (see <a href="http://www.sciam.com/ontheweb">www.sciam.com/ontheweb</a>)</p><p> My strategy for demonstrating that omega is incompressible is to show that having the first <i>N</i> bits of omega would tell me how to solve the Turing halting problem for programs up to length <i>N</i> bits. It follows from that conclusion that no program shorter than <i>N</i> bits can compute the first <i>N</i> bits of omega. (If such a program existed, I could use it to compute the first <i>N</i> bits of omega and then use those bits to solve Turing’s problem up to <i>N</i> bits—a task that is impossible for such a short program.)</p><p> Now let us see how knowing <i>N</i> bits of omega would enable me to solve the halting problem—to determine which programs halt—for all programs up to <i>N</i> bits in size. Do this by performing a computation in stages. Use the integer <i>K</i> to label which stage we are at: <i>K</i> = 1, 2, 3, …</p><p> At stage <i>K</i>, run every program up to <i>K</i> bits in size for <i>K</i> seconds. Then compute a halting probability, which we will call omega<sub><i>K</i></sub>, based on all the programs that halt by stage <i>K</i>. Omega<sub><i>K</i></sub> 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.</p><p> As <i>K</i> increases, the value of omega<sub><i>K</i></sub> will get closer and closer to the actual value of omega. As it gets closer to omega’s actual value, more and more of omega<sub><i>K</i></sub>’s first bits will be correct—that is, the same as the corresponding bits of omega.</p><p> And as soon as the first <i>N</i> bits are correct, you know that you have encountered every program up to <i>N</i> bits in size that will ever halt. (If there were another such <i>N</i>-bit program, at some later-stage <i>K</i> that program would halt, which would increase the value of omega<sub><i>K</i></sub> to be greater than omega, which is impossible.)</p><p> So we can use the first <i>N</i> bits of omega to solve the halting problem for all programs up to <i>N</i> bits in size. Now suppose we could compute the first <i>N</i> bits of omega with a program substantially shorter than <i>N</i> bits long. We could then combine that program with the one for carrying out the omega<sub><i>K</i></sub> algorithm, to produce a program shorter than <i>N</i> bits that solves the Turing halting problem up to programs of length <i>N</i> bits.</p><p> But, as stated up front, we know that no such program exists. Consequently, the first <i>N</i> bits of omega must require a program that is almost <i>N</i> bits long to compute them. That is good enough to call omega incompressible or irreducible. (A compression from <i>N</i> bits to almost <i>N</i> bits is not significant for large <i>N</i>.)</p></blockquote>