FOM: Natural examples

[Stephen Fenner]

On Mon, 11 Oct 1999, Joe Shipman wrote:

> 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:
...
> 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.

I don't have a reference, but I strongly suspect that the 
degrees of the Friedberg-Muchnik sets are very sensitive to the choice of
the G"odel numbering (equivalently, universal TM) of computable partial
functions.  There are so many different, "natural" models of computation
(besides TMs) that one really cannot favor one over all others.  The
choice of computational model is a source of much additional Kolmogorov
complexity in the F-M construction.

BTW, the solution of Post's problem presented first in Soare's book is the
construction of a noncomputable low c.e. set, and is simpler than the F-M
construction.

Steve