FOM: my reply to Harvey and Steve

[Steffen Lempp]

Dear Harvey and Steve,

Having returned from Siena, I looked over all the email that had piled up,
in particular from FOM.

I have three comments on what the two of you wrote:

1. the search for natural degrees: I am not sure that "mentioned in the
non-logic math literature" or, worse, "in the university curriculum", is an
adequate definition of natural, esp. since the latter seems to shrink
constantly, while the former is expanding at a breath-taking pace.
I propose instead as a preliminary working definition "natural" to mean
"definable in the degree structure using only the partial ordering".
Such a degree (other than 0, 0', etc.) would indeed be remarkable and show
that the degrees of the well-ordered sequence 0^alpha are not the only natural
degrees. Work on this, of course, has been going on for a while, in several
directions, by Slaman-Woodin on the bi-interpretability conjecture, by
Cooper's claim of nonrigidity, etc. There are several possible outcomes here
(depending on what degree structure we are talking about):
bi-interpretability (which would, of course, imply rigidity), the
degrees being a prime model of their theory (known for the Delta2 Turing
degrees, open for the others), or on the other extreme that no degree other
than the 0^alpha's is somehow definable (related to Martin's conjecture). In
summary, the search for natural degrees is going on, maybe with a slightly
different slant than the one Harvey envisions, but any progress here would be
a step in the right direction.
Two asides: a. The r.e. Turing degrees coincide, of course, e.g., with the
Turing degrees of word problems of finitely presented groups, or the Turing
degrees of solution sets of diophantine equations. This provides another angle
on the r.e. degrees being "natural".
b. Selivanov has some interesting work on fine hierarchies, where he shows
that in certain (so far somewhat limited) settings, the index sets
corresponding to definable properties can only attain 1-degrees within this
natural fine hierarchy. 

2. Harvey asked what I thought the major recent changes in
recursion/computability theory going on right now are. I see mainly two:
a. Within classical degree theory, there is a shift away from collecting
merely algebraic facts about the degrees (noncuppable, minimal cover, etc.,
etc.) to more global questions: decidability of (fragments of) the first-order
theory, global algebraic characterizations (lattice embeddings, extensions
of embeddings, etc.), rigidity, definability (cf. Cooper's definability of
the Turing jump, or the more recent work of Nies/Shore/Slaman) and the prime
model question. There have been some spectacular successes in the past ten
years, solving long-standing problems that had seemed beyond reach for
decades, all this building on the work on "algebraic facts" of the era before.
b. Increased and renewed interest in recursive model theory, esp. in the U.S.:
With the thaw of relations with the fSU, there has been an increasing
interchange of ideas, leading to solutions of problems that Russians had
worked on, at times using techniques developed mainly in the West, in
particular the advanced versions of the priority argument. This development
has only started recently, and it is too early to tell where exactly it is
headed, but I believe it is an important development (as we will hopefully see
next June at the AMS summer meeting in Boulder). (The growing connections
between reverse mathematics and recursion theory are another important
development, of course.)

3. recursive vs. computable: I agree with Soare that "computable" is the
better word, but I don't agree with him that it is all that important.
Of course, there was a PR aspect to this (as Shoenfield mentions also), no one
has ever denied this, which is why Soare was so vigorously attacked.
Also, the terms "computable" etc. have been around for a long time and are
well-established, so it is not the case that anyone is making up completely
new notation.
Since I don't consider this name debate all that important, let me instead
focus in on Steve's objection to the term "computability theory". First of
all, like almost all names of mathematical fields, it is NOT a precise notion,
but encompasses anything having to do with the concepts of computation,
computability, relative computability (and thus also, as Steve objects,
NONcomputability) as well as enumeration and definability. And, of course, it
intersects nontrivially with many other fields (incl. complexity theory),
which is exactly what we want it to!

Best,			Steffen

********************************************************************************

Office address: Prof. Steffen Lempp
		Department of Mathematics
		University of Wisconsin
		480 Lincoln Drive
		Madison, WI 53706-1388   USA
Office phone:   (608) 263-1975 or (608) 263-3054
Office fax:     (608) 263-8891
WWW home page:  http://www.math.wisc.edu/~lempp

********************************************************************************