Gibt es ein vollständiges Problem für die Klasse der entscheidbaren Probleme?

Sprachen wie sind mit vielen Reduzierungen. Es ist trivial zu sehen, dass auch vollständige Probleme hat. S. Schmitz [1] betrachtet einige Klassen zwischen und . Sie stellen für diese Klassen vollständige Probleme unter speziell gestalteten Reduzierungen.$\text{HALT}_{TM}$$\textsf{RE-complete}$$\text{co-RE}$$\text{ELEM}$$\text{REC}$

Gibt es vollständige Probleme für (auch bekannt als ) im Vergleich zu schwächeren Reduktionen? Turing-Reduktionen sind ungeeignet, weil sie die ganze Arbeit erledigen können. Sollten wir damit rechnen, dass solche Reduktionen erfunden werden, oder nicht ( z. B. viele Reduktionen, die auf die primitive Rekursion beschränkt sind)?$\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$$\textsf{REC}$

[1] Sylvain Schmitz Komplexitätshierarchien jenseits der Grundstufe 2013 http://arxiv.org/abs/1312.5686

Im Allgemeinen impliziert eine Klasse mit einem vollständigen Problem unter einer netten Klasse von Reduktionen, dass die Klasse aufgezählt werden kann. ist nicht berechenbar aufzählbar, daher hat es kein vollständiges Problem bezüglich einer schönen Klasse von Reduktionen.$\mathsf{R}$

Hier ist das Argument:

Angenommen, es gibt ein vollständiges Problem ist für R . Daher kann für jedes Problem in R aus einer Reduktion (sagen wir Polynom-Zeit-Vielfachreduktionen) in Kombination mit A erhalten werden . Wir können die Reduktionen rechnerisch aufzählen, daher können wir R rechnerisch aufzählen . Aber R ist nicht berechenbar aufzählbar (sonst könnten wir diagonalisieren).$A$$\mathsf{R}$$\mathsf{R}$$A$$\mathsf{R}$$\mathsf{R}$

Suchen Sie in der Literatur nach der Menge der gesamten rekursiven / berechenbaren Funktionen .