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

Question

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$?

Answer 1

Chaitin number $\Omega$ is asymptotically computable, so we can compute the first several digits of it.

Please check the paper Computing a Glimpse of Randomness by Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu at 2002, they calculate the first 64 bits of $\Omega_U$ where U is a special register machine.

In summary, the first 64 exact bits of $\Omega_U$ are: 0000001000000100000110001000011010001111110010111011101000010000

The value is depending on the machine U

Also the thesis of Truth and Light: Physical Algorithmic Randomness by Michael A. Stay is very worth reading. In the thesis, the author gives all the background and several universal prefix-free machines which is suitable for the study.

Answer 2

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.