Reduzierungen bei unentscheidbaren Problemen

Es tut mir leid, wenn diese Frage eine triviale Antwort hat, die mir fehlt. Immer wenn ich ein Problem untersuche, das sich als unentscheidbar erwiesen hat, stelle ich fest, dass der Beweis auf einer Reduktion auf ein anderes Problem beruht, das sich als unentscheidbar erwiesen hat. Ich verstehe, dass es eine Art Ordnung über den Schwierigkeitsgrad eines Problems schafft. Aber meine Frage ist - wurde bewiesen, dass alle Probleme, die nicht entschieden werden können, auf ein anderes Problem reduziert werden können, das nicht entschieden werden kann. Ist es nicht möglich, dass es ein unentscheidbares Problem gibt, das nachweislich nicht auf ein anderes unentscheidbares Problem reduziert werden kann? (Um die Unentscheidbarkeit eines solchen Problems zu beweisen, kann man keine Reduzierungen verwenden). Wenn wir Reduzierungen verwenden, um eine Reihenfolge für den Grad der Berechenbarkeit zu erstellen, kann diesem Problem kein solcher Grad zugewiesen werden.

Wie Hendrik Jan erwähnte, gibt es tatsächlich unterschiedliche Grade der Unentscheidbarkeit. Zum Beispiel ist das Problem, zu entscheiden, ob eine Turing-Maschine an allen Eingängen stoppt , im folgenden Sinne schwieriger als das Stopp-Problem: Selbst wenn das Stopp-Problem ein Orakel ist, können wir nicht entscheiden, ob eine bestimmte Turing-Maschine an allen Eingängen stoppt .

Eine wichtige Technik, um solche Beziehungen zu zeigen, ist die Diagonalisierung . Bei Verwendung der Diagonalisierung können wir bei einem Problem immer ein schwierigeres Problem finden, nämlich das Stoppproblem für Turing-Maschinen mit Zugriff auf a$P$ Orakel. Das neue Problem P ' ist im folgenden Sinne schwieriger: Eine Turingmaschine mit einem Orakelzugang zu P kann P ' nicht lösen. In diesem Sinne gibt es kein "schwerstes" Problem.$P$$P'$$P$$P'$