Natural example of a strictly recursively enumerable set below the halting problem

Question

My question is about sets that are recursively enumerable, not recursive and strictly weaker than the halting problem. I know that such sets do exist (in fact, infinitely many) - this is an answer to the famous Post's problem.

But is there any natural set of this type? E.g., some set that was defined not only to be an example of something between $0$ and $0'$? All the proofs of undecidability I have seen so far (except for examples that have no much sense outside the computability theory) consist of encoding some (at least) Turing complete model.

Answer 1

There is no known example of such a set, and I believe it is widely believed that there are no such examples at all (although of course it's difficult to formalize this).

We can prove that there is no "canonical" exampe of an intermediate c.e. set. Specifically, it is known (proved by Lachlan) that there is no $e$ such that

• For every $X$, $X<_T W_e^X<_T X'$ (that is, $W_e^-$ is a recipe for cooking up an intermediate c.e. set),

and

• For every $X\equiv_TY$, we have $W_e^X\equiv_TW_e^Y$ uniformly (that is, the $W_e^-$ is actually finding an intermediate Turing degree - in some sense, $W_e^-$ is "invariant" in the appropriate sense: the amount of information in $W_e^X$ depends only on the amount of information in $X$; the "uniformly" at the end says that there is an algorithm providing a computation of $W_e^X$ from $W_e^Y$ when given an algorithm for computing $X$ from $Y$).

Along similar lines, it is conjectured (Martin's conjecture) that every "reasonable" function from Turing degrees to Turing degrees is "almost always" an iterate of the jump operator $X\mapsto X'$. (The precise statement(s) of Martin's conjecture are a bit technical, so I'll omit them unless you're specifically interested - let me know in a comment if you are.) And Martin's conjecture is known to hold for certain classes of functions.

All of this points towards a negative answer to your question. However, there is still hope: a natural c.e. set whose definition fundamentally doesn't relativize could still exist. For example, consider Hilbert's 10th problem for $\mathbb{Q}$. Based on current knowledge, it is possible that the set of polynomials with rational coefficients which have rational solutions could be of intermediate degree. Of course, it's also possible that it is computable or complete, too. There are other examples, also coming from algebra, which could conceivably generate such a natural intermediate set in a "non-relativizing" way, so as to avoid the Martin/Sacks obstacles. However, that said, I think the general view is still one of pessimism.

---

Things get better if we shift to classes of degrees ("mass problems"), in which case there are many natural examples. In some sense, mass problems are more natural than Turing degrees anyways: they represent the complexity of problems with more than one solution, and most problems in mathematics ("find an ideal in this ring," "find a subspace of this vector space," "find a descending path through this illfounded linear order", ...) are of this type. This is a point of view heavily exploited in reverse mathematics. However, Turing degrees are still in some sense "more fundamental" (at least, I would argue that) and so the shift to mass problems is not entirely satisfying (at least, to me).