[FOM] ASL Annual Meeting

[Stephen G Simpson]

This is another follow-up to my FOM posting of Tue Jun 10 18:01:40 EDT
2003.

I said:

   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. ]

But this does not do justice to Levin, because the related result
stated in his abstract (also proved in the 1972 paper which I cited)
is not quite the same as Theorem 1.  For that result, 1 - epsilon is
indeed correct and best possible.

Stephen G. Simpson
Professor of Mathematics
Pennsylvania State University