[FOM] ASL Annual Meeting
Stephen G Simpson
simpson at math.psu.edu
Mon Jul 14 11:45:50 EDT 2003
This is a follow-up to my FOM posting of Tue Jun 10 18:01:40 EDT 2003.
Off-line, Leonid Levin (via Alasdair Urquhart) has asked me for
clarifications and references to the literature, concerning the
results which I mentioned as being well known. The results,
reproduced from my earlier posting, are:
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.
By the way, there is some difficult work by Hanf and Peretyatkin which
implies that the theory T of Theorem 1 can be taken to be finitely
axiomatizable. See Peretyatkin's book on finitely axiomatizable
theories (English language edition 1997).
Clarifications: (I think this is overkill.)
1. The term "compute" refers to Turing computablity, sometimes with a
Turing oracle. Thus "X computes Y" means that Y is Turing
computable using X as a Turing oracle. Here X and Y may be taken
to be infinite sequences of 0's and 1's, or subsets of the natural
numbers. The notion of Turing oracle is explained, for example, in
the classic textbook, Theory of Recursive Functions and Effective
Computability, by Hartley Rogers, Jr., McGraw Hill Publishing
Company, 1967.
2. By a "theory" I mean a set of sentences in the first order
predicate calculus, closed under logical consequence, in a
vocabulary consisting of a finite set of predicates. A theory is
said to be decidable if it is recursive. A theory is said to be
recursively axiomatizable if it is the closure under logical
consequence of a recursive set of sentences. A theory is said to
be finitely axiomatizable if it is the closure under logical
consequence of a finite set of sentences. A theory is said to be
essentially undecidable if it has no decidable extension. The
"provables" of a theory are the sentences which belong to the
theory. The "refutables" of a theory are the sentences S such that
not-S belongs to the theory.
3. When I say that a random Turing oracle has a property, I mean that,
with probability 1, a random sequence of 0's and 1's (obtained by a
sequence of independent tosses of a fair coin) has the property in
question. This can be formulated rigorously in terms of the
probability space (2^N, mu), where 2^N is the space of total
functions from the set of natural numbers, N, into {0,1}, and mu is
the product measure, with mu({X:X(n) = i}) = 1/2, for all natural
numbers n, and i = 0 or 1.
References to the literature:
One paper from the 1970's that I am familiar with is:
@Article{js,
author = "Carl G. Jockusch{, }Jr. and Robert I. Soare",
title = "{$\Pi^0_1$} classes and degrees of theories",
journal = "Transactions of the American Mathematical Society",
year = 1972,
volume = 173,
pages = "35--56",
}
This paper includes Theorems 1 and 2 and their proofs.
Further remarks:
At Leonid Levin's suggestion, I have looked up his paper at
http://arxiv.org/abs/cs.CC/0203029/. It appears that he has proved
some refinements of Theorems 1 and 2, which he states in terms of
Kolmogorov's notion of "mutual information", with which I was not
previously familiar.
>From my point of view, an important service that Levin has performed
is to bring out an interesting formulation of the
foundational/philosophical significance of Theorems 1 and 2. He did
this in terms of the old question of whether the Godel/Tarski
undecidability results can be overcome by means of probabilitic
algorithms, i.e., algorithms using a random Turing oracle. The
answer, of course, is "no". See Levin's abstract for the recent ASL
Annual Meeting, on-line at https://www.aslonline.org/.
Stephen G. Simpson
Professor of Mathematics
Pennsylvania State University
More information about the FOM
mailing list