9
$\begingroup$

Can anyone provide an overview of the proof that Chaitin's constant is normal, or better yet, the guiding intuition?

Even if we replace the existential quantifiers in the assertion of non-normality by explicit functions of the universally quantified variables, I don't see how an oracle in possession of those functions could solve the halting problem, yielding the desired contradiction.

(In fact, I would've guessed that the normality of Chaitin's constant was in the class of undecidable things!)

Putting the question more starkly: if 90% of the bits were 0's, how would knowing this give you a way to solve the halting problem?

$\endgroup$
5
  • 1
    $\begingroup$ As recently asserted in a comment by Douglas Zare, here: mathoverflow.net/questions/18375/… $\endgroup$
    – Todd Trimble
    May 28, 2013 at 15:29
  • 1
    $\begingroup$ @Todd Trimble: The thread was bumped recently, but my comment was from over 3 years ago. $\endgroup$ May 28, 2013 at 16:06
  • $\begingroup$ @Douglas Zare: okay. Anyhoo... I hope I can look forward to your answer to James Propp's question. $\endgroup$
    – Todd Trimble
    May 28, 2013 at 21:46
  • $\begingroup$ It has been a while so I'm not sure if I can reconstruct the argument. The hard step is to show that Chaitin's $\Omega$ is algorithmically incompressible, that there is a finite upper bound on the number of bits which can be compressed from a prefix. Non-normal numbers can be compressed more than any fixed number of bits by a simple compression scheme. I think if you can compress prefixes of $\Omega$ any number of bits, then you can construct a program which halts iff it doesn't halt by using the saved space to write the program. $\endgroup$ May 29, 2013 at 2:56
  • 1
    $\begingroup$ @James: On MO, CW is often used for questions that have no definite answers. Usually questions with multiple answers where it makes sense to sort the answers by an appropriate preference scheme. I don't think this applies here. $\endgroup$ Jun 2, 2013 at 12:29

1 Answer 1

7
$\begingroup$

Consider a program $P_n$ which first unpacks $\Omega_n$, the first $n$ digits of $\Omega$, then runs all finite programs tallying $2^{-k}$ each time a program of length $k$ halts. $P_n$ continues until it gets within $2^{-n}$ of $\Omega_n$, and then halts. If you run all finite programs forever, then you see all contributions to $\Omega$, so you get arbitrarily close to $\Omega$, and $P_n$ must halt at some point. $P_n$ runs a copy of itself, but it doesn't observe itself halt. So, the contributions of programs which halt up to this point (at least $\Omega_n - 2^{-n} \ge \Omega - 2^{-n+1}$), plus $2^{-|P_n|}$ for $P_n$, must be less than $\Omega$. This means $|P_n|\ge n$.

Let $c_1(n)$ be the length of the part of $P_n$ which says to run all finite programs, tallying their contributions to $\Omega$, and halt if it gets within $2^{-n}$. $c_1(n)$ is $O(\log n)$. For any $n$, there can't be a way unpack $\Omega_n$ with fewer than $n-c_1(n)$ bits. If $\Omega$ were not normal, then for infinitely many $n$, $\Omega_n$ could be compressed saving at least $c_2 n + c_3$ bits. If $90\%$ of the digits of $\Omega$ were $0$s then it would take fewer than $n/2 + c_4$ bits to encode $\Omega_n$. So, if $\Omega$ is not normal, then some $P_n$ could have fewer than $n$ bits, a contradiction.

$\endgroup$
1
  • $\begingroup$ Just what I needed to know! Thanks, Doug. $\endgroup$ Jun 2, 2013 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.