Concerning Computational Equivalence Ideas

[Harvey Friedman]

We can formulate extremely difficult conjectures in a good way using
the current standard presentation of Turing machines say in
https://en.wikipedia.org/wiki/Turing_machine#Formal_definition where
we use only two symbols and any number of states. Write set(TM) for
the set of input strings that lead to halting.

Let n be the least number of states sufficient for a TM to have
set(TM) non recursive.
Let m be the least number of states sufficient for a TM to have
set(TM) be complete r.e.
Let r be the least number of states sufficient for a TM to have
set(TM) be of degree 0'.
Let s be the least number of states sufficient for a TM to have
set(TM) be non recursive and not complete r.e.
Let t be the least number of states sufficient for a TM to have
set(TM) be of degree strictly between 0 and 0'.

What are some lower and upper bounds on n,m,r,s,t, and what are some
relationships between n,m,r,s,t? Wolfram seems to be in the direction
of n,m,r being very close, and much lower than s,t, and perhaps with
s,t being close.

Harvey Friedman