[FOM] RE sets/Naturalness//conjectures

[Harvey Friedman]

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 
>this use unhelpful.

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.

>If foundations is about anything, it is about making notions 
>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 
quadruples.

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