[Math] Can we know the first few digits of Chaitin’s constant

chaitin-constantcomputability

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

Best Answer

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.