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?



Normality of Chaitin's constant
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.


