8
$\begingroup$

According to this source, Chaitin's constant $\Omega$ is normal.

Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Indeed, each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits.

Source (Wikipedia)

Furthermore, the definition of normal is that each digit occurs with equal probability $1/b$. And that each duets of digits occur with $1/b^2$ probability and every triplets occurs with probability $1/b^3$ and so on.

Chaitin's omega is calculated via

$\Omega = \sum_{p \in halts} 2^{-|p|}$

Writing $\Omega$ in binary, we obtain a list of 0 and 1. For example,

2^-1=0.1 +
2^-2=0.01 +
2^-3=0.001 +
~skip 2^-4 as it does not halt
2^-5=0.00001 +
...
=\Omega
=0.11101...

Clearly, we can see that the position of each bits corresponds to the halting state of the program of length corresponding to the bit.

Here is what I am struggling with

If $\Omega$ is indeed normal, then it means that exactly 50% of programs halt and exactly 50% do not. This seems very counter intuitive.

For example, suppose I generate java programs by randomly concatenating single characters. The majority of them, I would guess more than 99.99% would not even compile. Would this not imply that at least 99.99% of them will not halt? How do we justify that exactly half will halt and exactly half will not, by virtue of $\Omega$ being normal.

Or is wikipedia incorrect about $\Omega$ being normal?

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! If you put your LaTeX between dollars instead of backticks, we'll be able to read the output, rather than the source. $\endgroup$ – David Richerby Dec 20 '16 at 20:23
  • 1
    $\begingroup$ And for the fractions \frac{1}{b^2} gives $\frac{1}{b^2}$ instead of $1/b^2$. $\endgroup$ – Evil Dec 20 '16 at 20:39
  • $\begingroup$ I believe that Chaitin's Omega is defined for prefix-free Turing Machine encodings, not for arbitrary encodings. If so, I think our normal intuitions around what constitutes a "random" TM might not be so reliable. $\endgroup$ – mhum Dec 21 '16 at 0:52
  • 1
    $\begingroup$ @mhum You can re-encode any program to a prefix-free encoding by adding a 1 in between every bit of the original program, then terminating it with a 0. Then the Turing machine reads every second bit until it finds the terminating 0. This leaves the java code intact but makes it prefix free. Hence the problem remains. $\endgroup$ – Alexandre H. Tremblay Dec 21 '16 at 2:37
8
$\begingroup$

In contrast to your example, Chaitin's constant is not defined as follows:

$$ \Omega = \sum_{n\colon \text{$n$th program halts}} 2^{-n}. $$

Instead, there is a set $\Pi \subseteq \{0,1\}^*$ of allowed programs which is prefix-free (no string is a prefix of another string). Each of the programs in $\Pi$ is legal (this negates your Java example). If the programs are encoding in unary then it is indeed the case that the $n$th program has length $n$, and then your definition of $\Omega$ works. But for other encodings, the definition of $\Omega$ is

$$ \Omega = \sum_{ p \in \Pi\colon p \text{ halts} } 2^{-|p|}, $$ where $|p|$ is the length of the binary string $p$. Kraft's inequality shows that $\sum_{p \in \Pi} 2^{-|p|} \leq 1$.

Chaitin's constant is algorithmically random: the (prefix) Kolmogorov complexity of the first $n$ bits is $n - O(1)$. To show this, note first that $\Omega_n$, the first $n$ bits of $\Omega$, suffice to determine whether a program of length $n$ (under the encoding $\Pi$) halts or not. Indeed, as a fraction, $\Omega_n \leq \Omega < \Omega_n + 2^{-n}$. Run all programs in parallel, and whenever $p$ stops, add $2^{-|p|}$ to some counter $C$ (initialized at zero). Eventually $C \geq \Omega_n$ (since $C \to \Omega$ from below). At this point, if the input program of length $n$ didn't halt, then you know that it doesn't halt, since otherwise $\Omega \geq C + 2^{-n} \geq \Omega_n + 2^{-n}$.

Given this, suppose that for some $K>0$ and infinitely many $n$, you could compute $\Omega_n$ using $n - K$ bits. For each such $n$, you can find a string whose Kolmogorov complexity is larger than $n$, by considering the output of all halting programs of length at most $n$. For large enough $K$, the result is a program of length at most $n$ for computing the a string whose Kolmogorov complexity is more than $n$. This contradiction proves that for some $K$, the Kolmogorov complexity of $\Omega_n$ is at least $n-K$.

Algorithmic randomness of $\Omega$ implies, in particular, that the frequency of 0s and 1s in its binary expansion tends to 1/2. Indeed, suppose that for some (rational) $\epsilon > 0$ there exist infinitely many $n$ such that the fraction of 1s in $\Omega_n$ is at most $1/2-\epsilon$. Since there are only at most $2^{h(1/2-\epsilon)n}$ strings with at most $1/2-\epsilon$ many 1s, we can compress $\Omega_n$ to size $h(1/2-\epsilon)n + 2\log n + C_\epsilon$ (the constant $C_\epsilon$ depends on $\epsilon$ since the program needs to know $\epsilon$). However, this is $n - \omega(1)$, contradicting the algorithmic randomness of $\Omega$.

$\endgroup$
  • $\begingroup$ Thank you for the very complete answer. I am struggling with the very first paragraph and I apologize for it not getting through my skull. If we only take those java programs that do compile, then encode them to unary, does it then mean that exactly half of them will halt? $\endgroup$ – Alexandre H. Tremblay Dec 21 '16 at 12:26
  • $\begingroup$ @AlexandreH.Tremblay Yes, that's the implication. For more, I recommend a textbook on Kolmogorov complexity, such as Li and Vitanyi. $\endgroup$ – Yuval Filmus Dec 21 '16 at 12:29
  • $\begingroup$ Could you make the Turing machine such that it includes a java compiler? Picture this. First, list all possible randomly generated strings of characters from shortest to longest. Second, encode these strings in unary. Third, feed the unary strings to the Turing machine as input. The Turing machine checks if the input compiles in Java. If it does, it executes it and half will halt and half will not. If it does not compile, then it loops forever (while(true){};). Would this not skew the halting/non-halting ratio? I have read Li and Vitanyi last week, but I will need to read it again ;). $\endgroup$ – Alexandre H. Tremblay Dec 21 '16 at 13:27
  • $\begingroup$ I suspect that unary encoding in the way you suggest wouldn't be admissible. For example, in unary encoding (even the simple one) you won't be able to compose programs with constant overhead. I'd check Li and Vitanyi for a list of properties that an admissible universal computer has to satisfy. This would be part of the definition of Kolmogorov complexity. $\endgroup$ – Yuval Filmus Dec 21 '16 at 13:35
  • $\begingroup$ Hello, can you recommend the section of Li and Vitanyi where this information is present. I read the book a second time and could not find it. $\endgroup$ – Alexandre H. Tremblay Jan 16 '17 at 0:05
0
$\begingroup$

Your mistake is on the following line:

If $\Omega$ is indeed normal, then it means that exactly 50% of programs halt and exactly 50% do not.

Nope. That's not what "normal" means. Or, to say it another way: Define $d_0(n)$ to be the number of bits that are a 0, in the first $n$ bits of the base-2 expansion of $\Omega$. Saying that $\Omega$ is normal implies that

$$\lim_{n \to \infty} {d_0(n) \over n} = 1/2.$$

In other words, "normal" is an asymptotic notion. It means that as you look far enough into the bits of $\Omega$, on average about half of them will be 0's. (Similarly, about half with be 1's.)

However, this says nothing about the first few bits of $\Omega$. For instance, there is no implication that the binary expansion $\Omega$ starts out as 0.01... or at anything else -- and there is no implication that $\Omega$ is close to 1/2. $\Omega$ might be close to 0, or close to 1, or anywhere in between; that doesn't contradict being normal, and being normal doesn't imply anything about how large $\Omega$ is.

$\endgroup$
  • $\begingroup$ Note that $\Omega$ is the probability that a random Turing machine halts under a very strange distribution. The OP is interested in the uniform distribution (in some limiting sense). So nobody is implying that $\Omega$ is close to 1/2. $\endgroup$ – Yuval Filmus Dec 21 '16 at 9:05

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.