FOM: natural examples

[Carl G. Jockusch]

First, let me apologize for leaving to my colleagues the "heavy
lifting" of discussing the significance and applicability of
computability theory and, more specifically, the priority method.
Whether I will jump into this at some future time remains open, but in
this message I would like to comment on the problem of finding a
natural example of a c.e., non-computable set of natural numbers.
Here I will conform to a very strict concept of "natural" which
requires very simple definitions which do not use any sort of coding.

I would like to propose a couple of candidates for a natural example
of a c.e. noncomputable set.  Each of these is obviously c.e., and I
hope that they will also be considered clearly natural in the strict
sense above.  The catch is that it is not known whether they are
computable or not.

The first candidate is the set D of all natural numbers which can be
expressed as the difference of two prime numbers.  (It follows from
the linear case of Schinzel's Hypothesis (a generalization of the twin
prime conjecture) that every even number is the difference of two
primes.  Thus Schinzel's hypothesis implies that D is computable.
However, Schinzel's hypothesis seems beyond the reach of current
number theory.  I have no argument that D "should" be noncomputable
though it is easily seen that there are computable sets R such that
the set of all differences of elements of R is non-computable.  For
further information and references, see "Difference sets and
computability theory", by R. Downey, Z. Furedi, C. Jockusch, and
L. Rubel, APAL 93 (1998), 63-72.)

The second candidate C is related to the (in)famous "3x+1"-problem.
Let f(n) be n/2 if n is even and 3n+1 if n is odd .  Let C be the set
of natural numbers n such that the sequence n, f(n), f(f(n)),
f(f(f(n))), ...  has 1 as a term .  It is conjectured by many that
every natural number is in C , and so of course C is computable.
However, this conjecture again seems intractable.  Again, there are
variants of f (which are linear on each residue class mod k for some
fixed k) which yield a noncomputable corresponding set C , and in fact
J. H. Conway has shown that every c.e. set may be obtained in this
fashion.  For further information and references, see "Unpredictable
iterations" by J. H. Conway, Proc. 1972 Number Theory Conference,
University of Colorado, 1972, 49-52 or the survey paper "The 3x + 1
problem and its generalizations" by J. C. Lagarias, American
Math. Monthly, January 1985, 3-22.)

Carl Jockusch