[FOM] ASL Annual Meeting

[Stephen G Simpson]

Alasdair Urquhart writes:
 > The most interesting plenary talk to me was by Leonid Levin,
 > who gave a fine exposition on "Forbidden information."
 > The general thrust of this talk was to reject the following 
 > reaction to Goedel's incompleteness theorem: "Goedel has shown
 > that formal methods don't work, so we'll have to use informal
 > (physical?) methods instead."  Greg Chaitin, for example, argues
 > somewhat along these lines.

Dear Alasdair,

I concur with the thrust of Levin's argument.  The widespread idea of
trying to use physical or probabilistic oracles to overcome the Godel
Incompleteness Theorem seems misguided.

Having said that, I am still wondering what precisely Levin has
proved.  Do his results boil down to the following two theorems?
These theorems are well known.

Theorem 1.  We can construct a recursively axiomatizable theory T such
that T is essentially undecidable, yet a random Turing oracle computes
a completion of T.

[ In other words, the probability that a random infinite sequence of
0's and 1's computes a completion of T is 1.  Levin's abstract says
that the probability is greater than .99, but 1 is also correct. ]

Theorem 2.  A random Turing oracle does not compute a completion of,
for example, Peano Arithmetic.

[ In other words, the probability that a random infinite sequence of
0's and 1's computes a completion of PA is 0. ]

By the way, the theory T mentioned in Theorem 1 has the interesting
property that the provables and refutables of T are recursively
separable, even though T is is recursively axiomatizable and
essentially undecidable.

Of course, Kolmogorov complexity and algorithmic randomness are a good
setting for quantitative refinements of Theorems 1 and 2.  Thus we can
say that every 1-random sequence computes a completion of T, and every
2-random sequence does not compute a completion of PA.  Perhaps this
is Levin's point.

-- Steve