FOM: Natural examples

[Joe Shipman]

This is an attempt to sharpen some questions that were discussed last
month.

Question 1: Is there a "natural" definition of a c.e. degree d different
from 0 and 0' ?

Henceforth abbreviate "c.e. degree d different from 0 and 0' " by
"intermediate degree".

Precise version 1.1: Is there an intermediate degree definable in the
structure of c.e. degrees under Turing reducibility?

Answer:  No, Barry Cooper reports, because there are automorphisms
moving any degree.  (Question to Cooper: is there a single automorphism
which moves all intermediate degrees?)

Precise version 1.2: Is there an intermediate degree definable in the
structure of degrees under Turing reducibility with the jump operator?

Answer: No, Cooper reports, because the jump operator itself is
definable, so the answer to 1.1 implies this.

Precise version 1.3: Is there a naturally defined SET of intermediate
degrees?

Answer: Yes, for example the "High" degrees satisfying d'=0'', or the
"Low" degrees satisfying d'=0'.  I don't know any others. (I called
question 1.3 "precise" because it has a positive answer; a negative
answer would require sharpening of the definition of "natural".)
Whatever the definition of "natural", there cannot be a naturally
defined FINITE set of intermediate degrees unless there is a naturally
defined SINGLETON intermediate degree, because one could join the finite
collection together in an natural way to obtain a single intermediate
degree.

Precise version 1.4: What is the most "natural" intermediate degree
known, where "natural" is defined in terms of Kolmogorov complexity?

Answer:  I believe this would be one of the original two incomparable
degrees constructed in the Friedberg-Muchnik proof, which is tricky but
fairly short.  But I don't know the following:
1) Did Friedberg's and Muchnik's independently discovered proofs differ
in any significant way (did they calculate the same pair of degrees, for
example)?
2) Has the version in Shoenfield's 1967 text "Mathematical Logic" been
improved upon in terms of length?
3) Just how short are the resulting programs in terms of number of
Turing Machine quintuples or number of lines of LISP code or some other
intelligible measure?
4) [For Barry Cooper]: are the two degrees specified in the
Friedberg-Muchnik proof equivalent to each other under some automorphism
of the c.e. degrees?


Question 2:  Is there a "natural" definition of a c.e. SET whose degree
d is different from 0 and 0' ?

It is important to distinguish this from the previous question.  There
may be a natural degree with no natural examples of sets with that
degree; but if there is a "natural" set with intermediate degree, then
this degree itself is "natural".  However, if the definition of the set
depends on a particular basis for computation (universal TM) in such a
way that different such bases give rise to different degrees, then the
word "natural" applied to the degree need not connote rigidity in the
model-theoretic sense.

Precise version 2.1: Has any specific c.e. set that was defined in
"ordinary mathematics" (this can be made precise using the standard
Mathematics Subject Classifications, but I won't bother) been of
intermediate degree?

Answer: No. (key word "specific")

Precise version 2.2: Has any collection of c.e. sets that was defined in
"ordinary mathematics" (this can be made precise using the standard
Mathematics subject Classifications, but I won't bother) included sets
of intermediate degree?

Answer: Yes; see Higman (word problems for groups) or Davis, Putnam,
Robinson, Matiyasevich (diophantine equations).

Precise version 2.3: Has any collection of c.e. sets that was defined in
"ordinary mathematics" (this can be made precise using the standard
Mathematics subject Classifications, but I won't bother) included SOME
but NOT ALL sets of intermediate degree?

Answer: I think not, but if an ordinary mathematical structure reflects
the c.e. degrees with sufficient faithfulness, then the analogues of the
"high" and "low" degrees may become "natural".  For example, if the jump
operator had some reasonable interpretation that stayed within the
"ordinary mathematics", this would be the case; this is not true for
finitely presented groups or diophantine equations, but I don't know
whether this is true for other examples (like the work of Nabutovsky and
Weinberger that Soare has recommended).


-- Joe Shipman