Hacker News new | ask | show | jobs
by GregBuchholz 3358 days ago
>Chaitin's constant -- <snip> -- which is so ornery a number that we cannot (even in THEORY) figure out a single digit of it (other than its being between 0 and 1).

You might be interested in:

https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf

"A Chaitin Omega number is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random(its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly noncomputable. The aim of this paper is to describe a procedure, that combines Java programming and mathematical proofs, to compute the exact values of the first 64 bits of a Chaitin Omega: 0000001000000100000110001000011010001111110010111011101000010000"

1 comments

Unfortunately, that is not a Chaitin Omega, since the notion of program length in that paper is flawed. In particular, it counts a 0 or a 1 provided as binary data in the program as adding 7 bits of length to the program. Later papers by Calude fix this problem, while reducing the number of computed bits to 43.