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?

  • 1
    $\begingroup$ As recently asserted in a comment by Douglas Zare, here: mathoverflow.net/questions/18375/… $\endgroup$ – Todd Trimble May 28 '13 at 15:29
  • 3
    $\begingroup$ Why is this community wiki? $\endgroup$ – François G. Dorais May 28 '13 at 15:36
  • $\begingroup$ @Francois: I made it a community wiki because the request for a "guiding intuition" is a vague one, and when I've posted such questions in the past, people have complained "This should be a community wiki." But if I'm misunderstanding what community wiki status is for, please enlighten me! $\endgroup$ – James Propp May 28 '13 at 15:55
  • 1
    $\begingroup$ @Todd Trimble: The thread was bumped recently, but my comment was from over 3 years ago. $\endgroup$ – Douglas Zare May 28 '13 at 16:06
  • 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$ – François G. Dorais Jun 2 '13 at 12:29

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.

  • $\begingroup$ Just what I needed to know! Thanks, Doug. $\endgroup$ – James Propp Jun 2 '13 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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