[FOM] ASL Annual Meeting

[Stephen G Simpson]

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