Recognizing and Using Chaitin's Constant

Solution 1:

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.