FOM: Natural examples: reply to Soare

[Joe Shipman]

I think Friedman and Simpson's call for "natural examples" of
intermediate r.e. degrees was misinterpreted by Soare; the query is for
a natural *specific* degree, not a natural *set* of degrees.  We already
knew about the existence of diophantine equations, finitely presented
groups, 4-manifolds, etc., instantiating any computably enumerable set;
but to construct a specific such equation, group, or manifold which
represents an intermediate degree is very complicated, so that the
Kolmogorov complexity of the resulting finite object is very large.

It is not an uncommon phenomenon to have a simply defined set but no
simply defined member of the set.  (For example, the set of
well-orderings of 2^omega is easily defined but it is possible no
individual member of this set is definable at all.)  What are the best
upper bounds known for the complexity of a degree between 0 and 0', in
some natural metric like Turing machine size?

(I recognize that I am changing the issue slightly here, because it
makes more sense to identify "natural" with "size of definition" rather
than "Kolmogorov complexity"; but if we are to make any technical
progress we must do this, as we otherwise have the relatively trivial
answer "the first Turing machine which enumerates a function of
intermediate degree", which can be turned into a formal definition that
is not too large.)

-- Joe Shipman