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 omega_K, based on all the programs that halt by stage K. 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 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 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 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 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.)

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.

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.

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 omega_K, based on all the programs that halt by stage K. 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 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 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 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 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.)

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

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.