[FOM] ASL Annual Meeting
Stephen G Simpson
simpson at math.psu.edu
Tue Jun 10 17:01:40 EDT 2003
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
More information about the FOM
mailing list