# [FOM] Wolfram and intermediate degrees

Harvey Friedman friedman at math.ohio-state.edu
Tue Jun 24 01:13:47 EDT 2003

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

```