"Chaitin's mystical, magical number "
- The following material is quoted from Elements of Information Theory
by Thomas M. Cover and Joy A. Thomas, John Wiley, 1991, primarily pages
164-166.
- There is a lot of other good stuff in this book. If I ever decide to try
to understand statistical mechanics and thermodynamics, I
will start with "the asymptotic equipartition property".
"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.
Definition:
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 :
- 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 . ...
- 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. ...
- ...