FOM: motivations

Harvey Friedman friedman at
Fri Aug 13 15:49:04 EDT 1999

Comment on Shoenfield 8:33PM 8/12/99:

>     The lack of many applications outside of RE degree thery and the
>lack of natural examples of RE degrees are, of course, disappointing
>to the priority theorists; but I don't think they imply (as Simpson
>and Friedman seem to think) that they show that priority theory is
>not worth studying.   Natural examples and applications are only two
>of the many reasons for examining a theory.

I have heard of recursion theory, recursive function theory, computability
theory, and definability theory. But what is "priority theory"?

I can't speak for Simpson, but I certainly do not believe that the features
you cite in and of themselves imply that the theory is not worth studying.
In fact, I have never even said that the theory is not worth studying. I
articulated a more subtle view in 4:44PM 8/5/99. It makes it all the more
interesting to find other kinds of reasons for the huge research effort.

NOTE: This kind of critical analysis can also be appropriately done for
virtually all parts of mathematical logic. There is no effort to single out
recursion theory.

Comment on Jockusch 5:31PM 8/12/99:

Recursion theorists on the FOM have proposed three "natural" examples of
possible nonrecursive sets of natural numbers:

1. (Jockusch) Positive differences between prime numbers.
2. (Cooper) The set of all N such that there is a block of exactly N 5's in
the decimal expansion of pi.
3. (Jockusch) The set of numbers that iterate to 1 under the piecewise
linear map: if n is even then n/2 else 3n+1.

[The credits just signify who mentioned them on the FOM, and not their

These are all incomparably more mathematically natural than any known
examples, to my knowledge. In my opinion, they still differ from one
another somewhat in their relative mathematical naturalness, which is
really premature to worry about. I have listed them in order of my opinion
of their mathematical naturalness. However, I conjecture that they are all
recursive sets.

The situation with regard to natural intermediate r.e. degrees is quite
different. Here I have never seen a proposal of a natural intermediate r.e.
degree. Does anybody have such a proposal?

More information about the FOM mailing list