FOM: Natural examples

[Joe Shipman]

Stephen Fenner wrote:

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

This is one of the things it would be really useful to know.  Can anyone
clarify how sensitive the degrees of sets constructed in various priority
arguments are to the particular choice of a basis for computation?  Since the
standard bases for computation (TMs, general recursive functions, combinators,
etc.) are recursively isomorphic in a strong sense, I think it plausible that
the simpler priority arguments might not lead to different degrees for any of
these.  Can any recursion theorists can help us here?

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

I don't have this book -- can you sketch this proof for us?

-- Joe Shipman