[FOM] ASL Annual Meeting
Harvey Friedman
friedman at math.ohio-state.edu
Thu Jun 12 03:18:56 EDT 2003
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.
More information about the FOM
mailing list