# [FOM] RE sets/Naturalness//conjectures

Harvey Friedman friedman at math.ohio-state.edu
Sat May 24 01:34:13 EDT 2003

```This posting, which proposes some precise questions and research
topics, was suggested by the posting of Davis 5:24PM 5/23/03.

We begin by a conceptually oriented reply to Davis, and then followup
with some strictly mathematical questions.

>
>
>He [Simpson] also notes that in addition to the Medvedev degrees
>forming the top and bottom of this lattice, there are intermediate
>degrees that can be identified as precisely the degree of the set of
>infinite sequences of 0s an 1's that are random in the sense of
>Martin-Löf. This is a really neat and surprising [result]...

Davis has obviously made a completely correct value judgment that
distinguishes the Medvedev degrees from what is known about the
Turing degrees of r.e. sets. Given Davis' value judgment, we can ask
if a similarly "really neat and surprising" result exists for Turing
degrees of r.e. sets. If Davis makes this value judgment here, he can
surely make the value judgment there, and his answer has to be NO up
to the moment. The interesting question is: can this change over
time? What could be behind it not changing over time?

>(to me), bringing together two fundamental notions. Simpson
>contrasts this situation with the much-studied r.e. degrees, where
>despite the plenitude of intermediate degrees, none has turned up
>which can similarly be identified as the degree of an important
>problem occurring in a different context.
>
>Simpson uses the word "natural" in making this contrast, and I find

Unhelpful for certain people, but a natural word, and unavoidable in spirit.

However, even much better than merely talking about "natural" and
"unnatural" would be at least some mathematical program aiming to try
to ferret out the difference.

I should point out that there were several postings by recursion
theorists on the FOM, including Jockusch, freely using "natural" in
this context and/or related recursion theoretic contexts.

>precise. I would love to see a precise definition of what it means
>for something in mathematics to be "natural", and while we all do
>use the word, short of such a definition, the use is bound to be at
>least partly subjective.

It is far too difficult for us to work out proposals of precise
definitions of what it means for something in mathematics to be
"natural". This is out of the question right now with our present
understanding. However, important general moves can be made in this
direction. One problem is that this leads to excruciatingly difficult
problems technically. But see what I am talking about below.

Nevertheless, it seems extremely inadvisable to try to avoid such
judgments in the choice of research problems and programs. Every good
professional does make judgments of this sort. And there is no doubt
that the importance of our (i.e., everybody's) work both in the short
and long range, and the influence of our work both in the short and
long range, is deeply affected by how sound these judgments of
"naturalness" are - as well as more subtle notions related to
"naturalness".

So I am very much against the idea of "protecting" students and
colleagues from such judgments, although there is a conservative
limit as to what is appropriate to put into print in a formal Journal
of mathematics.

In fact, "protecting" students and colleagues from such judgments
amounts to an insidious form of "political correctness" which
undermines the purpose of intellectual life.

Of course, it is also vital when bringing up such matters, especially
with students, that one should go out of one's way in pointing out
that there are plenty of people with opposite viewpoints.

And then, it is natural(!) - in fact compelling - to want to go on to
at least try to relate such judgments to supporting mathematical
conjectures. This, I think, is where Martin Davis is at.

>Someone deeply immersed in the demanding craft of priority
>constructions, may find sets of intermediate Turing degree
>constructed by those means perfectly "natural".

But even here, there are serious questions of robustness that in such
detailed contexts, are difficult to avoid. I.e., do we get the same
intermediate Turing degrees or sets of intermediate Turing degrees if
we change coding and various ways of proceeding?

Actually, I think that it would be valuable for the FOM if the
distinguished recursion theorists on the list could take a little
time out to consider some interesting and completely precise
questions concerning this - i.e., how much matters are affected by
the exact way of going about priority constructions.

In fact, one may have interesting theorems to the effect that any
(significant) minor change in the setup for a priority argument
always leads to a different degree. Or at least partial results that
give necessary or sufficient conditions for there to be no change in
the degree.

In many cases, the parameter to vary is obvious - it might be an
actual standard (in the precise standard sense) partial recursive
enumeration of the partial recursive functions of one variable. (Here
the notion of "standard" is a precise and very important technical
one that is very interesting and totally standard in the subject, and
has nothing to do with "natural" in the sense under discussion).

Such an investigation could conceivably be profitable throughout the
entire range of priority arguments. (If this turns out to be a good
new idea, you heard it first on the FOM email list. Help with the
membership drive!!)

>  And a debate on this matter is sure to become about words not concepts.

Davis - I'm trying...

>But one can be quite precise in stating that no one has produced an
>intermediate r.e. degree about which it can be said that it is the
>degree of a decision problem that had been previously been studied
>and named.
>

Yes, this is a nice way of making the point.

Before getting into some math, here is a general conceptual issue
that is suggested by this, which is of an historical, pragmatic,
naturalistic, character. E.g., it fits into the framework of Maddy's
current approach to ph.o.m.

***Find examples in mathematics generally where a particular family
of mathematical objects is intensively studied, where there are no
"natural" examples other than the trivial ones. One can use Davis'
naturalistic criterion "had been previously studied and named".***

I.e., a good project in naturalism is to investigate the role of
"natural examples" in mathematics.

###############################

I now wish to move to some precise conjectures.

For some time now, I have been very interested in "simplicity". The
crudest approximation to simplicity is

tiny.

Yes, I hear from the some readers that this is too crude for them,
that this is beneath them. But even the first 500 obvious questions
in f.o.m. in terms of "tiny" are more than enough in technical depth
to occupy 1 billion people for 1 billion years.

Now let's relate this to "naturalness" in recursion theory.

1. It has been a well known occupation of some to try to find the
"tiniest" Turing machine whose behavior is nonrecursive, in terms of
the accepted inputs. A pretty much generally accepted standard has
emerged for talking about how "tiny" these TM's are. I think one
measures the number of states and symbols used in the set of

The subscribers could help by listing some websites that I recall are
devoted to the state of the art on this question. I.e., for what tiny
pairs (n,m) is it the case that you get nonrecursive behavior in the
set of accepted strings with TM's with n states and m symbols.

The numbers are very very small, if I recall, and the accepting
strings of the TM's written down are COMPLETE RE SETS.

CONJECTURE: There is no tiny TM whose acceptance set is an r.e. set
of intermediate degree. There is no TM with at most 10 symbols and 10
states whose acceptance set is an r.e. set of intermediate degree.

Of course, negative results are going to be excruciatingly hard in
this direction. But

CHALLENGE. Write down the smallest sized TM you can whose acceptance
set is an r.e. set of intermediate degree.

2. A lot of classical logic has been devoted to the determination of
whether certain theories in predicate calculus with equality are
decidable or not, in the sense that the theorems in its language form
a recursive set or not. In every case not jimmied up to be a
counterexample, it has been either recursive or complete r.e. (or
unknown).

Let's look at single sentences in one binary relation symbol without
equality. Note that there are only finitely many such sentences with
a given number of quantifiers, up to logical equivalence.

What is the least number of quantifiers needed for a sentence in one
binary relation symbol to have a nonrecursive set of consequences in
the same language?

Answer: 1. (forall x)(R(x,x)). 1 is least since no sentence can have
0 quantifiers. Of course, the empty theory has undecidability.

What is the least number of quantifiers needed for a sentence in one
binary relation symbol to have a recursive set of consequences in the
same language?

Answer: 2. (forall x,y)(R(x,y)). It can be seen that 1 is not enough.

What is the least number of quantifiers needed for a sentence in one
binary relation symbol to have a set of consequences in the same
language, of intermediate degree?

CONJECTURE: At least 8.

CHALLENGE: Write down the sentence with the smallest number of
quantifiers in one binary relation symbol you can, whose set of
consequences in the same language is of intermediate degree.

Is it fair to restrict to one binary relation symbol only in this
problem? Yes, because the trivial degrees 0 and 0' can handle this
restriction.

Harvey Friedman

```