Can we know the first few digits of Chaitin's constant?

2.3k Views Asked by At

Chaitin's constant ($\Omega$) is a non-computable real number. Intuitively, it is the probability that a random program will halt.

In reality, the actual value of $\Omega$ depends on the encoding used for the programs and the statistical properties of the random generator used. So there are many "Chaitin's constants", what identifies them together is the common definition as halting probability.

Suppose we fix a program encoding and a procedure to generate random programs. It is impossible to write a finite algorithm that will output all the digits of $\Omega$ one-by-one. Is it possible to write a finite algorithm that will output a finite number of digits of $\Omega$?

1

There are 1 best solutions below

0
On

I assume you mean, "is it possible to write an algorithm that knowably prints $n$ digits correctly?" Of course, any finite string can be printed by an algorithm, so the key is that it prints the first $n$ digits, and we know it prints the first $n$ digits.

The answer is that, depending on the encoding, you can. In fact, there is no bound on such $n$'s (although there is a bound for any one given encoding). Also, there are encodings that can not be calculated to even one digit.

As for the unbounded nature of such $n$'s, consider encodings $E_1,E_2,...,$ such that $E_i$ lists $i$ knowably computable functions before listing any other functions. Some such encoding can be chosen to ensure that the algorithm which prints all 1's is correct to $n$ digits.

As for there being no knowable digits for some encoding, suppose that the first program in an encoding can not be known to halt (by the Church-Turing Thesis, there exist such encodings, although these encodings can not be recognized as such). It is true that knowing the first $n$ bits, one could calculate the halting problem for all programs of a size up to $n$. Then knowing the first bit would allow us to calculate the halting problem for the first function, which is impossible.

Maybe you are looking for an intelligent function which prints some correct digits for any given encoding. Any function that identifies halting functions could be used to form a function in such an effort, and it would sometimes not be provably correct to 1 digit, and there would be cases where it is provably correct to any given number of digits.