# Is There a Complete Problem for the Class of Turing Decidable Problems?

Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes inbetween $\text{ELEM}$ and $\text{REC}$. They present complete problems for these classes under specifically crafted reductions.

Are there complete problems for $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ (aka $\textsf{REC}$) relative to weaker reductions? Turing reductions are inappropriate because they are capable of doing all the work. Should we expect such reductions to be contrived or not so (e.g. many-one reductions that are restricted to primitive recursion)?

[1] Sylvain Schmitz Complexity Hierarchies Beyond Elementary 2013 http://arxiv.org/abs/1312.5686

• This question seems a bit simple, but a professor and I blanked on it. I wouldn't be surprised if the answer is obvious. My apologies if this is the case. Even so, it will be nice to have the answer somewhere on the internet.
– mdxn
Sep 20 '14 at 19:55
• Every non-trivial recursive problem is complete under recursive many-one reductions. Are you looking for weaker reductions? Sep 21 '14 at 1:25
• @YuvalFilmus: Yes, I am.
– mdxn
Sep 21 '14 at 18:38
• @YuvalFilmus I'll provide a bit more info. Consider the case with $\textsf{P}$. When looking at P-completeness, we tend to consider weaker reductions such as logspace or first order reductions. If we defined P-completeness using polynomial many-one reductions, then we run into a similar situation that you bring up (an FO reduction is known to be strictly weaker). We can make the reduction perform nearly all the computation instead of identifying complete problems in a fruitful manner.
– mdxn
Sep 22 '14 at 20:58

Generally a class having a complete problem under a nice class of reductions implies that the class can be enumerated. $\mathsf{R}$ is not computably enumerable, therefore it does not have a complete problem with respect a nice class of reductions.
Assume that there is a complete problem $A$ for $\mathsf{R}$. Therefore for any problem in $\mathsf{R}$ can be obtained from a reduction (let's say polynomial time many-one reductions) combined with $A$. We can computably enumerate the reductions, therefore we can computably enumerate $\mathsf{R}$. But $\mathsf{R}$ is not computably enumerable (otherwise we could diagonalize).
• @Ariel, enumerate Turing machines with clocks of the form $n^k+k$. There are other more interesting (but harder to prove) ways to enumerate them, e.g. polynomial time computable functions are exactly queries which can be express in FO(LFP, BIT). Jan 13 '16 at 0:03