FOM: natural examples/support system/divides

[Harvey Friedman]

Reply to Cooper 8:02AM 8/5/99:

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

It is useful to have this on the record. An earlier posting of someone
would appear to have contested the point.

>...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'?),

The set of integers N for which a sequence of exactly N 5s appears in the
decimal expansion of pi being nonrecursive would indeed make a big splash
in the mathematics community, and with many other people. Yes, it would be
mathematically natural - certainly on a comparative basis. And yes, one
could want it to be even more natural.

But there would still be a big important difference between recursion
theory and various classification topics in mathematics. In the latter
case, one has a variety of known natural examples - known before an
intensive classification effort is under way. That is something I don't see
in r.e. sets/degrees.

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

Are you referring to the actual results or various methods?

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

I think you are headed towards a discussion of various kinds of determinism
and nondeterminism formulated in recursion theoretic terms. But let me say
right off the bat that there is a problem that I see with anything like
this, and that is the unwarranted use of infinities in the discussion.

In particular, there is the tantalizing possibility that there is a deep
new theory of finite recursion theory, where the Kolmogorov complexity
approach is just one small matter. Once you start talking about actual
practical things in real life, it seems that you want to move to finite
treatments of the whole subject. Perhaps you know of creative work in this
direction?

This could be a typical example of a possible conceptual reorientation of a
field suggested by considerations outside its normal scope.

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

I do not regard the fact that no one seems to be able to produce a
mathematically natural example of an intermediate degree as implying that
intensive study of the r.e. sets/degrees is questionable. Rather, I
mentioned it as a symptom - something that should cause concern - something
that should cause people to search out reasons for the huge investment
relative to other pursuits. I think it admirable that people like you are
willing to take the issue seriously and try to come up with imaginative
reasons.

I urge readers to again look at my posting of 8/5/99 4:44PM where I am more
precise about my position on recursion theory. My position is much more
subtle than can be captured in easy soundbites (of course, I know Cooper is
fully sensitive to subtleties).

I have little doubt that if you come up with new and sound imaginative
reasons for the intense investigation of r.e. sets/degrees, then this will
form the basis for related investigations. And you probably would not have
even thought of the related investigations had you not come up with the new
imaginative reasons.

**However, my fear is the following. That there is no decent support system
left for new imaginative investigations - even if they are sound. They will
not be considered on a par with time tested investigations steeped in 40
years of technical history. Job opportunities and grant support will not be
available for such things, at least in the US logic and US math community.
I don't know as much about Europe.**

NOTE: Cooper follows with a rather long and intriguing discourse mentioning
proponents A and B without name. They have the appearance of, say, Friedman
and Cooper, but I cannot really tell. It would be valuable to have this
stuff spelled out more directly.

I now come to his final paragraph:

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

Good idea. Do you think I have been sufficiently clear about "positive"
achievements of my professional activities and, in my words, their general
intellectual interest? Or in the context of this discussion, do you need me
to be more explicit?

On the other hand, you haven't made very many postings on the FOM and I
don't think people can judge by what you have written yet on the FOM what
your [and your close associates] "positive" achievements are, and their
general intellectual interest. I think the readers would be very pleased to
see this discussed in clear terms on the FOM, rather than, e.g., be sent to
look at other websites.

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

I don't think that this readership is familiar with the "fundamental
problems identified by the early founders of the theory" that are being
solved. Could you please elaborate on these? Also, what do you think are
some of the "potentially remarkable applications - applications of what? -
to a wide range of problems outisde of mathematics"? I personally am not
sure of what you are referring to in either case, and would like to hear.

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

I am intrigued with this phrase "both sides of the divide thrown up by
Hilbert's programme" and would love for you to elaborate on what this
divide is.