[FOM] Wolfram and intermediate degrees

[Harvey Friedman]

Reply to Baldwin 8:47PM 6/23/03.

>There is discussion of intermediate degrees on page 1130-1131 of 
>Wolfram's A new kind of science.  In particular, there is
>a sketch (naturally I mean literally) of a machine that is supposed 
>to be of intermediate degree.  I would be interested in
>comment; especially from recursion theorists.

I will also wait to hear from recursion theorists.

I would like to reiterate two research projects in connection with 
intermediate degrees that I formulated in my posting 1:34AM 5/24/03.

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

II. The priority arguments all involve the prior selection of a 
natural r.e. enumeration of the r.e. sets, or a natural partial 
recursive enumeration of the partial recursive functions. The nice 
robust thing is that there is only one appropriate notion of natural 
here. It is well known that all natural enumerations - from the 
recursion theoretic point of view - are equivalent or isomorphic, in 
very precise and satisfying senses.

However, it would seem that in every single priority argument 
whatsoever, if we change the actual choice of the natural r.e. 
enumeration, then we get a DIFFERENT degree. In the case of 
intermediate degrees between 0 and 0', a DIFFERENT intermediate 
degree.

However, I have never seen this investigated. It raises all sorts of 
questions. E.g., what can you say about the intermediate degrees that 
you do get in these priority constructions, as you vary the choice of 
natural enumerations? Do interesting classes of intermediate degrees, 
never noticed before, emerge from such considerations?

As I wrote in my earlier posting:

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

Harvey Friedman