Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As far as I understand, Chaitin's constant is the probability that a given universal Turing machine will halt on a random program. I understand that Chaitin's constant is not computable--if it were, we could compute it and use it to solve the halting problem. Because the constant is not computable, there is no procedure that could be used to generate arbitrary digits of precision.

However, knowing many digits of the constant would allow us to solve the halting problem for some programs up to a certain size, and therefore (if we knew enough digits of the constant) to settle important unsolved mathematical questions.

Please correct me if any of the above is wrong. I have a two questions:

1) If somehow we were given (for instance by an alien) many digits of the constant for a certain Turing machine (which we were told how to construct), how would we recognize the constant? Would we need to trust the alien completely, or is there some way (easier than soving the halting problem) to test or at least increase our certainty that the constant we were given was Chaitin's constant for a certain Turing machine.

2) Second, if we did trust the constant to be correct for a given Turing machine, and then we solved many important mathematical questions by using it, would the knowledge gained be of any use? We would only have satisfied our curiosity about the "final answer", with no knowledge of a proof technique. Is that correct? Or could one use the constant to find traditional "satisfying" proofs?

share|improve this question
The first question might be better suited for cstheory.SE. As for the second question: the technique suggested in the Wikipedia article would yield a ‘proof’ which would be at least controversial, if not universally rejected. I don't think it would be possible to extract a traditional proof out of the knowledge that the program fails to halt, unless we obtained the necessary bits of Chaitin's constant by non-oracular means. –  Zhen Lin Aug 11 '11 at 15:25
en.wikipedia.org/wiki/IP_(complexity) and en.wikipedia.org/wiki/PCP_theorem seem relevant to the first question, although I don't know if they solve it. The second question asks for an opinion, and my opinion is "no." –  Qiaochu Yuan Aug 11 '11 at 15:40
If there were any way to check whether arbitrarily many given digits belong to Chaitin's or not, we'd be brute forcing numbers to find more and more digits of $\Omega$ as we speak - impossible because it's not computable. And, since $\Omega$ only has one precise value in any given context, one needs a working definition of what it means for $\Omega$ to have a certain probability of being in some interval or having a digit somewhere. –  anon Aug 11 '11 at 15:58
Busy beaver function can also be used for such purposes. The "Applications" section of the wikipedia articla en.wikipedia.org/wiki/Busy_beaver contains an interesting discussion on it. –  Levon Haykazyan Aug 11 '11 at 17:00
Thank you all for your replies! –  JOwen Aug 11 '11 at 21:20
show 1 more comment

1 Answer

up vote 6 down vote accepted

1) There is no algorithm that can compute arbitrarily many digits of $\Omega$. If we were in some fashion capable of checking whether given strings of numbers composed the first $n$ of $\Omega$'s binary expansion, we could simply brute force our way through all numbers with denominators $2^k,$ $k=1,2,3,\dots$, which would provide us with more and more digits of $\Omega$ - a contradiction.

However, all is not lost. First off, the set of rational numbers less than $\Omega$ is computably enumerable, so there exists an algorithm that lists them off one by one. More directly, we can compute successively better lower bounds by simply calculating known halting programs and discovering more of them (we never know how close we are, though, or otherwise we could extract digits). If the aliens give us a number less than Chaitin's constant, then in theory we could confirm that. In practice, though, we might well not have enough time and resources to check their number if it's too close to the real value, so we wouldn't be sure (and of course, we would be guaranteed failure if their number is $>\Omega$).

Second, just because no algorithm computes infinitely many digits, doesn't mean we can't soundly prove the first $n$ digits for some fixed $n$ (and a fortuitous choice of Turing machine). Mathworld provides two examples of Chaitin's constant being computed for two TM's:

$$\Omega_U= 0.0000001000000100000110\cdots_2$$ $$\Omega_U=0.0001000000010000101001110111000011111010\cdots_2 $$

For more on these, you'll have to see Calude (2002) and Calude, Dinneen (2007). Using these, we can do a rudimentary check on the alien's number by confirming or disconfirming that it agrees with what we have. But of course, this is extremely limited - and highly dependent on choice of Turing machine.

Third, the digits of $\Omega$ are algorithmically random, i.e. the first $n$ digits (alone) can only be enumerated in at least $n-O(1)$ steps. Thus it might be possible to investigate the plausibility of candidate digits via approximations of Kolmogorov complexity or other statistical tests. However, this may require a very large number of candidate digits in order to obtain a useful indicator, possibly more than is feasible to realistically work with.

2) Whether the answer to a general mathematics problem is "of any use" is outside the scope of computability theory. To the extent that proving or disproving a conjecture is inherently useful, then calculating truth or falsity based on $\Omega$ would be useful. If an existence claim turned out false, we could stop searching computationally, or if a universality claim turned out false we could start searching computationally for a counterexample. Precisely what the implications of a conjecture are depend on the problem itself, e.g. the Riemann hypothesis affects the distribution of prime numbers and subsequent arithmetic bounds in number theory.

However, a simple computation of this sort won't lend any insight into why a problem turns out the way it does. Normally in mathematics, famous unsolved problems require whole new theories, perspectives, or directions to resolve, but we won't get that from a $\Omega$-based calculation because all of the "reasoning" is not found in the digits, nor the checking of the digits. Chaitin's constant encodes only the answers, not the why's behind them.

share|improve this answer
Great answer, thanks. –  JOwen Aug 12 '11 at 20:19
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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