FOM:Natural Examples

[William Calhoun]

I recently joined FOM (after hearing about it at the Boulder computability
meeting).  I have been following the recent discussion of natural examples
with interest, and I hope this discussion will continue in a productive
direction. 

It seems to me that the lack of specific natural examples of c.e. sets
with intermediate Turing degree is a special case of a broader phenomenon. 

It seems that our main tool for separating levels of hierarchies is by
variations on Cantor diagonalization, including "fancy" variations such as
priority arguments and forcing.  Simple diagonlization produces natural
examples (the halting set, the continuum), fancy diagonalization is
required to produce the "unnatural" intermediate sets.  (Such as the sets
of cardinality between Aleph_0 and c that can be constructed in models of
ZFC by forcing.)

Godel was interested in the analogy between Post's problem and the
Continuum Problem (according to an earlier posting by Martin Davis).  I
think there is another interesting analogy between Post's problem and the
complexity theory problem of finding a set intermediate between EXPTIME
and P.

A simple diagonalization separates EXPTIME from P, but (as far as I know) 
no set has yet been shown to be intermediate between them, despite a huge
collection of natural candidates (e.g. the NP-Complete sets).  And oracle
results suggest that NP cannot be separated from P by any known form of
diagonalization.

If we are to find natural examples of intermediate c.e. sets, we may need
to develop new methods to show that certain sets have intermediate degrees.  
(Carl Jockusch suggested some possible candidates in an earlier posting.) 

It appears that a new method, or at least a more subtle form of
diagonalization, will also be required to solve problems in set theory
("natural" axioms to decide CH) and complexity theory (P=?NP).
 
Disclaimer:  I'm not a set theorist or complexity theorist (and only a
part-time computability theorist) so please feel free to set me straight.

-Bill Calhoun
-Math, CS, and Stats 		wcalhoun at plantex.bloomu.edu	
-Bloomsburg University		Telephone: 570-389-4507  
-Bloomsburg, PA 17815		FAX: 570-389-3599
Position: Assistant Professor  Research Interest: Computability