FOM: Natural examples

[S B Cooper]

A few remarks arising from recent FOM correspondence:

1) "Is there a single automorphism which moves all intermediate degrees?"
(Shipman, 11 Oct) 

It does not seem to be known if a non-trivial Turing automorphism can
leave some intermediate c.e. degree fixed - although Slaman announced (in
his paper "Degree structures" taken from his ICM talk) that he and Woodin
could prove that not all c.e. degrees can be so unmoved.

To rephrase the question regarding the existence of an automorphism
linking the Friedberg-Muchnik degrees, one can ask if any of the known
notions of genericity for c.e. degrees leads to a class of pairwise Turing
relatable degrees. (Not known of course.)

2) A general remark: Intuition suggests that there may be a certain
fortuitousness about those non-canonical environments giving rise to
incomputable objects. In that case, the lack of Turing definable
intermediate degrees just reinforces the impression of a strong
relationship between Turing definability and naturalness of information
content. It gives an indication of how the underlying information content
arises, not necessarily of its material absence.

3) The question raised by Simpson, concerning non-relativisable local
degree theoretic phenomena, is a very interesting one. For instance, Shore
(1981) showed that the degrees between 0 and 0' were not elementarily
equivalent to those between 0' and 0", using degree theoretic codings. But
one has no intuitive grasp of the differences between these two local
structures, having no natural examples of structural differences, and
(Simpson rightly observes) little understanding of what must be a quite
basic phenomenon.

4) A general observation concerning degree theoretic codings: One can draw
an (admittedly crude) parallel between Hilbert's program for mathematics
(as a subject of study) and the bi-interpretability conjecture for the
Turing universe, insofar as it provides a model for the computationally
complex scientific environment in which we live. Initially envisaged as a
tool in proving a positive result, codings provided the first technical
results limiting the scope of Hilbert's program, and it was some years
before examples of natural sentences unprovable in various key theories
were obtained. Similarly, coding techniques devised to prove Turing
rigidity have provided a whole range of global facts concerning the Turing
universe, while a number of these still await their more informative
natural counterparts. In this context, one may view as a historical
accident the premature discovery of a natural way of defining the Turing
jump (an approximation to a view originating with Harrington), and the
current lack of a proof of Turing nonrigidity via an appropriate coding
argument. 

5) Finally, the difficulty in verifying new results in certain areas (not
just computability theory): The problem seems to be that in order to
comprehend very complex mathematical structures, one must build higher
level conceptual frameworks in an effort to control the diversity of
components involved. Initially personal, these frameworks can be
consolidated into minor paradigms, basic to the development of a subject.
The problem is that these conceptual structures are not normally the focus
of critical attention, except when contingencies seem to indicate the need
for modifications. The larger the role of such paradigms, the less
distinguishable the practice of mathematics becomes from that of science
(anathema as this may be in certain quarters), with its sudden switches of
emphasis, and provisional factual basis. It is inevitable, then, that any
area worth pursuing in depth will eventually progress at a slower pace,
and with less certainty, than in its earlier development. Such a situation
is not new to computability theory, and the more recent history of the
subject is certainly no discredit, any more than the more visibly tortuous
progress of the number theorists towards a final proof of Fermat's last
theorem was. 

More than twenty years ago, referees were presented with a paper proving a
the existence of a relatively nonsplittable c.e. degree, which was, at the
time, unreadable, and apparently unrelated to the basic questions raised
by the founders of the subject. It was around ten years from the discovery
of that result to the achievement of an understanding of it, and (through
the creative involvement of a small number of individuals as much
interested in mathematical truth as in just their own results) the
development of the necessary framework for further progress. This
included, eventually, a natural definition of the Turing jump, and of the
relation of 'computably enumerable in' -- the original version of which,
incidentally, is more informatively described (cf Simpson 15 Oct) as
'incomplete'.  (There is a simple insert to the existing definition which
leaves the structure of the proof intact, and only requires amendment to
certain details of the verification. But the full module does need six
requirements to fully test it - an indication of how the amended
definition extends the existing paradigm, within which a number of other
experienced researchers in the field were able to 'verify' the original
definition.)

____________________________________________________________________________
  S Barry Cooper            Tel: UK: (0113) 233 5165,  Int: +44 113 233 5165  
  School of Mathematics     Fax: UK: (0113) 233 5145,  Int: +44 113 233 5145
  University of Leeds       Email: s.b.cooper at leeds.ac.uk  
  Leeds LS2 9JT             Home tel: (0113) 278 2586, Int: +44 113 278 2586
  U.K.                      WWW: http://www.amsta.leeds.ac.uk/~pmt6sbc
____________________________________________________________________________