Make your own free website on

"Chaitin's mystical, magical number "

"Let x be a finite length binary string and let U be a universal computer. Let l(x) denote the length of the string x. Let U(p) denote the output of the computer U when presented with the program p." (p. 147)

"In this section [7.8], we introduce Chaitin's mystical, magical number , which has some extremely interesting properties.


Note that = Pr(U(p) halts), the probability that the given universal computer halts when the input to the computer is a binary string drawn according to a Bernoulli(1/2) process [coin-flipping].

Properties of :

  1. is non-computable. There is no effective (finite, mechanical) way to check whether arbitrary programs halt (the halting problem), so there is no effective way to compute . ...
  2. is a "Philosopher's Stone". Knowing to an accuracy of n bits will enable us to decide the truth of any provable or finitely refutable mathematical theorem that can be written in less than n bits. ...
  3. ...