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?
Best Answer
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.