From: columbus@strident.think.com (Michael Weiss)
Newsgroups: sci.physics,sci.math
Subject: Chaitin's Omega and QM (was: Bayes' theorem and QM)
Date: 14 Dec 92 14:21:45
Organization: Thinking Machines Corporation, Cambridge MA, USA
	<1992Dec14.003452.12884@galois.mit.edu>
	<SRCTRAN.92Dec13221623@world.std.com> <1gh518INN9eo@chnews.intel.com>
	<SRCTRAN.92Dec14122532@world.std.com>
NNTP-Posting-Host: strident.think.com
In-reply-to: srctran@world.std.com's message of Mon, 14 Dec 1992 17:25:32 GMT

The purpose of this post is to give a reference, and to state
Chaitin's result with more precision than "Chaitin showed that integers
lead to randomness".

First, for anyone who has a vague feeling that there must be some sort of
connection between Chaitin's work and the foundations of QM, a good book to
look at is the collection "Complexity, Entropy, and the Physics of
Information", ed. by Wojciech H. Zurek, volume 8 in the Proceedings of the
Sante Fe Institute (pub. Addison-Wesley).  A few essay titles will give the
flavor:

    Information, Physics, Quantum: The Search for Links,  John A. Wheeler
    
    Algorithmic Information Content, Church-Turing Thesis, Physical
    Entropy, and Maxwell's Demon, W.H. Zurek

    Parallel Quantum Computation, Norman Margolus

The essay by Wheeler is oracular, heady, and good fun, but leaves you with
a bit a hangover in the morning.  I've been dipping into the other, more
sober, essays, and my own personal reaction is "yup, there's gotta be a
connection, but damned if I know what it is!"

To retreat to precise mathematics: Solomonoff, Kolmorgoroff, and Chaitin
all gave definitions of the entropy or information content of a finite
bit-string, and Chaitin defined the notion of a random infinite bit-string
(the others may have too, I'm not familiar with the detailed history).
Chaitin defined a real number Omega between 0 and 1, which has several
interesting properties:

(1) In a certain precise mathematical sense which I won't explain, Omega is
    the probability that a randomly chosen Turing machine with random input
    will eventually halt.
(2) The binary expansion of Omega is Chaitin-random.
(3) The binary expansion of Omega is arithmetic, i.e., there is a formula
    in the language of Peano arithmetic with one free variable (call it
    G(x)) such that the n-th bit of Omega is 1 if and only if G(n) holds
    for the integers.
(4) G(x) in fact can be put in the form, "there exist infinitely many
    k-tuples (y_1,...,y_k) such that the exponential diophantine equation
    P(x,y_1,...,y_k) = 0 has a solution" (remember x is a free variable).
    Here k is some specific number, whose value I don't remember, and
    Chaitin has given P explicitly.  We're talking thousands of variables
    here.  From the standpoint of mathematical logic, however, the
    interesting thing about G(x) is that it is quite low in the arithmetic
    hierarchy: just pi_2, or AE, that is, we only need a single alternation
    of quantifiers to express it.
(5) The truth-value of G(n) (or equivalently, the value of the n-th bit of
    Omega) can be determined in Peano arithmetic for only a finite number
    of values of n.  The same holds if we replace "Peano arithmetic" with
    ZF, or indeed with any recursively axiomatized extension of Peano
    arithmetic. 

In some sense, then, Omega provides us with an infinite sequence of
arithmetical propositions (i.e., "the n-th bit of Omega is 1", for
n=1,2,3,...), and we will be unable to decide almost all of them so long as
we stick to Peano arithmetic (or ZF).  Chaitin concludes that perhaps
mathematicians should be readier to add new axioms to the accepted canon,
on what one might call an experimental basis.

Last time I posted on this topic, the notion of Chaitin-random came in for
some controversy.  Whether one is willing to accept the equation
"Chaitin-random = random" depends on philosophical issues.  I will not give
the precise definition of Chaitin-random, but I will try to indicate
roughly what it means.

There are actually several equivalent definitions of a Chaitin-random
infinite bit-string.  One can be approximately stated:

(i) An infinite bit-string is Chaitin random if it passes any sequence of
    statistical tests that can be posed by a single Turing machine.

Another equivalent definition uses the Chaitin entropy function.  This is
defined on finite bit-strings, and has almost exactly the same formal
properties as the entropy function we know and love from statistical
physics or coding theory.  Here is a loose paraphrase:

(ii) An infinite bit-string is Chaitin random if the entropy of its first n
    bits grows with n the way you would expect of a sequence of independent
    fair coin-tosses.

For precise definitions, theorems, and proofs, see Chaitin's books, or the
chapter in the Handbook of Computer Science on algorithmic information
complexity and the references there.  I also have some Latex notes I will
be glad to email to interested parties.