[FOM] ASL Annual Meeting

[Harvey Friedman]

Comment on Simpson 5:01PM 6/10/03.

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

It would be nice if the notions Steve uses here were defined for the 
readership.

What does "computes" here mean? What does 1-random and 2-random mean? 
And perhaps some references for results.