[FOM] ASL Annual Meeting

Stephen G Simpson simpson at math.psu.edu
Wed Jul 16 21:29:58 EDT 2003


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



More information about the FOM mailing list