FOM: natural examples

[S B Cooper]

_____________________________________________________________

In response to Harvey Friedman (FOM, Mon, 2 Aug 1999, 11:29):

Historical examples can be useful in an illustrative or pedagogical
context involving trust and open-minded exploration, or in the initial
stages of an attempt to understand something unfamiliar. Or to provide a
counterexample to some general assertion. But there can be little point in
exchanging, and analysing at length, such examples chosen, or rejected, in
accordance with an effort to substitute induction for real thought about
the phenomenon at hand (not that one would ever suspect contributors to
FOM of doing such a thing). 

The following has the limited aim of clarifying obvious misunderstandings,
and identifying (without trying to resolve) what seem to be the few areas
of substantive disagreement.

There does seem to be agreement that Harvey's point regarding 'canonical'
examples is valid. Quoting from my original message: 

> 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* [added emphasis] that is very significant.

But one would be missing the point of the 'However' starting the following
paragraph to analyse the extremely beautiful and significant results of
Feferman, Hanf, and Matiasevich (and of course one should also include the
names of Davis, Putnam and Julia Robinson in connection with this latter
work) just in terms of (pure) 'mathematically natural'. Although even in
that context there is room for discussion (if new techniques for
identifying incomputable sets and the failure to detect pattern in the
decimal expansion of pi were to lead to an incomputable set - say the set
of numbers N for which a sequence of exactly N 5s appears - would that
qualify as 'mathematically natural'?), one of the great achievements of
computability theory in the past (and one anticipates in the future) is
its contribution (both direct and conceptual) beyond the confines of pure
mathematics. And this is what was being referred to in mentioning Turing -
that in a world where an internationally respected logician can still
write 'I know of no mathematically natural example of an r.e. set of
natural numbers that is not recursive', a piece of pure mathematics
intended to prove the reverse of this statement theoretically anticipated,
quite unpredictably, the machine on ones desk facilitating the preparation
and despatch of such statements. There was no qualification 'mathematical'
to the use of the word 'natural' in the first two messages of this
correspondence (although Steve might retrospectively claim an implicit one
in his original message). And such an intention should have been clear
from reference to 'nascent incomputabilities' in nature. But even in
mathematics, it can be risky to assert just one meaning of a non-technical
term. ("Natural: of, existing in, or produced by nature", Collins
Dictionary of the English Language, 1984 edition -- plenty of room for
choice of 'natural' environment or processes of 'production'.) 

It is also risky (it turns out) to quote other people, even if it is not
to specifically support ones 'case', but to offer 'encouragement' to
mathematicians working on areas which they have not yet managed to
convince everyone of their 'general intellectual interest'. The quoted
words (in this case from Rota) may even be interpreted as ones own (Steve
Stevenson, FOM Thu, 29 Jul 1999). And it would be illogical to deny people
such encouragement on the grounds that Rota uses an illustrative example
(in relation to his claim that "Applications are found after the theory is
developed, not before") which does not provide a close description of what
one imagines a recursion theorist does. As for the von Neuman quote - and
there is insufficient time to check the context - it is hard to accept the
interpretation being put on the words of a man celebrated for his
unexpected discovery of the applicability of the theory of Hilbert spaces
to quantum theory some years after its development. But just one more
quote regarding the 'naturalness' of examples (this time from Gregory
Chaitin's "Algorithmic Information Theory", CUP, 1987, revised edn. 1992,
p.164): 

     "Perhaps biological structures are simple and easy to understand 
     only if one has an oracle for the halting problem."

But what is the issue of substance underlying this correspondence? One can
identify stereotypical proponents of contrasting positions. 

Proponent A believes we live in a 'computable' Universe - and not just on
his preferred mathematical territory. For him, there are precise,
effectively applicable criteria for the relevance of pure mathematical
research. Applications and theory have predictable avenues of connection. 
Language can be made to respond unambiguously to all our demands on it. He
recognises the technical interest of 'recursion theory' (as he insists on
calling it), but for him its great achievements predate the preoccupation
with incomputabilities (and the implicit limitation on his ultimate
ambitions in relation to reverse mathematics).

Proponent B, daily presented with what he chooses to recognise as nature's
uncertainties, takes a different view. Following Turing's 1939 attempt to
grapple with a real mathematical mystery, the relevance of the development
of the Turing model of computationally complex environments forces itself
upon him. He is interested in reverse mathematics, but proponent A's
enthusiasm for his nice results in reverse recursion theory is puzzlingly
muted. 

Both are amiable but serious people, and hope for a resolution of this
difference of world-view.

For proponent A, this will only be achieved by the progressive
establishment of some resuscitated form of Hilbert's programme. And, it
seems, by some concomitant reassertion of Enlightenment certainty in the
fields of science, humanities and mathematics itself (in relation to CH,
for instance, what might be viewed as an epistemological counterpart to
Penrose's 'cosmic censorship principle'). Local explanations of what
happens on the borders of quantum uncertainty. Or maybe a rigorously
finitist interpretation of the Universe, denuding it at the outset of
inconvenient physical consequences, such as incomputable reals, of its
algorithmic content and related higher order/systemic relations. He
anticipates the inevitable demise of postmodernism, poststructuralism, and
all manifestations of epistemological relativism. Turbulence to be
theoretically tamed by reference to polynomial bounds. Cosmogonical and
associated mysteries marginalised. Every avatar of incomputability exposed
as a sham. 

Also, for proponent A, the internal consistency of this outlook requires
no humility. Within such a world-view, one can assume (if one is clever
enough) certainty in relation to anything. 

This contrasts with the approach of proponent B, who, roughly speaking, is
enticed by the scenario sketched in my earlier message - that is, the
development of the theory of the incomputable to the point where what it
explains makes the acceptance of its basic assumptions unavoidable. 

Hopefully such stereotyped positions have limited relevance to those of
real people. Otherwise those who believe in such things recognise aspects
of a Kuhnian paradigm dispute. While those who do not may just end up
shouting louder. 

If one is to try and identify an area of discussion worth further
correspondence - and the underlying incommensurabilities of viewpoint make
this difficult - one would focus on some *positive* achievements of our
professional activities. At a point in time when both reverse mathematics
and computability theory seem to be enjoying a golden period (in the case
of the latter, unprecedented progress with the fundamental problems
identified by the early founders of the theory, and the discovery of
potentially remarkable applications to a wide range of problems outside of
mathematics) there is surely much more to be shared concerning things we
really *do* know something about. Even if it does include descriptions of
the significance of work on both sides of the divide thrown up by
Hilbert's programme. 

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