FOM:Natural Examples
William Calhoun
wcalhoun at planetx.bloomu.edu
Wed Aug 18 11:03:31 EDT 1999
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
More information about the FOM
mailing list