FOM: natural examples

[S B Cooper]

Just a short remark in regard to part 2 of Steve's summary of Harvey's
comments (circulated in his Wed 28 July FOM message):

One very often sees something along the lines "The only natural examples
[of r.e. sets and degrees] are the original ones, i.e. the halting problem
and the complete r.e. degree", and a qualification (even if providing
nothing new to most of us) is appropriate. 

There are of course a number of different definitions of 'natural' in this
context, depending on different notions of 'natural' information content
or of degree theoretic context. It is true that all the known canonical
c.e. sets (e.g. those associated with standard first-order axiomatic
theories, the halting problem, etc) turn out to be computable or of
complete c.e. degree, and that for a pure mathematician that is very
significant. It may also turn out that 0 and 0' are the only Turing
definable c.e. degrees.

However, there are mathematical criteria according to which *all* c.e.
sets and Turing degrees potentially contain 'natural' information content
which may be encountered in specific contexts - just to mention two 
well-known examples:

1) (Feferman, Hanf) All c.e. degrees contain (finitely) axiomatisable
theories, and 

2) (Matiasevich) All c.e. sets are diophantine.

In recognising such mathematically immediate levers to incomputable
information content, one may then (and this leads on to a purely personal
response along the lines of h-i of Steve's/Harvey's part 1 - Defending
Specialised Subjects) allow the probability of the existence of material
counterparts. And then one would have to expect consequences. There are a
number of results (many already mentioned) pointing in this direction, but
the persisting speculative nature of the discussion that makes one ask how
such 'real world' incomputabilities are to be recognised. 

If one looks to the history of mathematics and the way it gives often
unexpected explanations of physical phenomena, it is the development of
theory which opens the perceptual doors. (For instance, the acceptance of
gravitational 'action at a distance' implicit in Newtonian dynamics forced
itself on people mainly by the explanatory power of the theory in relation
to the observed motion of the moon and planets.) In the case of
computability theory, if the apparent permeation of the material and
epistemological universe by nascent incomputabilities is confirmed, then
the Turing model for computationally complex environments has immediate
relevance. And that relevance may only become widely recognised through
the development of the theory of that model to the point where it is
capable of explaining something people actually care about. Of course,
there is no guarantee that every arcane body of theory, even if built on
fundamental concepts, will eventually explain anything. But those of us
who are led by intellectual curiosity (and that is 'the *real* reason',
maybe incapable of the kind of reduction Steve is looking for) into (what
may appear to be) more abstruse research topics, can look to one of
Gian-Carlo Rota's characteristic quotes (taken from an interview with MIT
Tech Talk) for encouragement:

________________________________________________________________________
Applications are found after the theory is developed, not before. A math
problem gets solved, then by accident some engineer gets hold of it and
says, 'Hey, isn't this similar to...? Let's try it.' For instance, the
laws of aerodynamics are basic math. They were not discovered by an
engineer studying the flight of birds, but by dreamers -- real
mathematicians -- who just thought about the basic laws of nature. If you
tried to do it by studying birds' flight, you'd never get it. You don't
examine data first.  You first have an idea, then you get the data to
prove your idea. 
____________________________________________________________________

Of course, Turing's 1936 paper and the development of the stored-memory
computer is a famous example of how ostensibly esoteric 'pure' research
can lead to important applications. In fact, it is hard to think of a
publication in any other area of mathematical logic that has had so
celebrated an influence outside of pure mathematics. 

Steve may propose perfectly valid criteria of relevance for assessing the
long-term value of a particular field of research. Unfortunately (as
computability theory tells us) those criteria may not be effectively
implementable - and while one may on occasion be forced to attempt such
implementation, in so doing one must be aware that more damage than
benefit may result. And one such damaging effect can be demoralisation
among people producing some very nice mathematics - not necessarily a good
basis for a 'productive' change of direction, just for diminished research
activity. 

-- Barry

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