Existe um problema completo para a classe de problemas decidíveis de Turing?

Linguagens como são sob muitas one-redução. É trivial ver que tem problemas completos. S. Schmitz [1] considera algumas classes entre e . Eles apresentam problemas completos para essas classes sob reduções especificamente criadas.$\text{HALT}_{TM}$$\textsf{RE-complete}$$\text{co-RE}$$\text{ELEM}$$\text{REC}$

Existem problemas completos para (aka ) em relação a reduções mais fracas? Reduções de Turing são inadequadas porque são capazes de fazer todo o trabalho. Deveríamos esperar que essas reduções fossem inventadas ou não ( por exemplo, muitas reduções restritas à recursão primitiva)?$\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$$\textsf{REC}$

[1] Hierarquias da complexidade de Sylvain Schmitz além do ensino fundamental 2013 http://arxiv.org/abs/1312.5686

Geralmente, uma classe com um problema completo em uma boa classe de reduções implica que a classe pode ser enumerada. não é computávelmente enumerável; portanto, ele não possui um problema completo com relação a uma boa classe de reduções.$\mathsf{R}$

Aqui está o argumento:

Suponha que há um problema completa para R . Portanto, para qualquer problema em R pode ser obtido a partir de uma redução (digamos tempo polinomial muitos-um reduções) combinado com um . Podemos enumerar as reduções computacionalmente; portanto, enumerar R computavelmente . Mas R não é computávelmente enumerável (caso contrário, poderíamos diagonalizar).$A$$\mathsf{R}$$\mathsf{R}$$A$$\mathsf{R}$$\mathsf{R}$

Na literatura, procure o conjunto de funções recursivas / computáveis ​​totais .