FOM: Exchange with Davie on complexity of intermediate degrees

[Joe Shipman]

G Davie wrote:

> Dear Professor Shipman
>
> I have been thinking about the following remark of yours:
> "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."
>
> Can we not see the Friedberg-Muchnik proof as a construction of two
> programs enumerating two sets, at least one of which is of
intermediate
> degree?  If so then since the (fairly short) proof of FM is really a
> construction of the two (fairly succinctly describable) programs, both

> have low Kolmogorov-complexity and hence there IS a Turing machine
> with low Kolmogorov complexity enumerating a set of intermediate
> degree.
>
> I may very well be missing something. I have thought a lot about
> Kolmogorov complexity but much less about degrees!
>
> Sincerely
> George Davie
> University of South-Africa
> South-Africa

Dear Professor Davie,

Yes, I was thinking of the original Friedberg-Muchnik proof as the best
current example of an intermediate degree; but even though this proof is

short (2 pages in Shoenfield's text), when you unpack it and translate
it
into a real Turing machine program it is fairly formidable.  This is
actually an excellent exercise, because the resulting T.M. program will
still be feasible in size -- I would guess it can be done with a few
hundred quadruples.

The other technically precise way to identify a "natural" intermediate
degree is to find one that is invariant under all automorphisms of the
r.e.
degrees.  Barry Cooper is the expert on automorphisms of the degrees,
perhaps he can tell us if one exists.

-- Joe Shipman