Probleme, deren Entscheidbarkeitsstatus unbekannt ist, von denen jedoch bekannt ist, dass sie weniger schwierig sind als das Stoppproblem

Gibt es Probleme, deren Entscheidbarkeit unbekannt ist, aber es ist sicher bekannt, dass die Probleme weniger schwierig sind als das Stoppproblem.

Unter der Annahme, dass mit "weniger hart" "reduzierbar auf" gemeint ist, erfüllt jedes Problem, von dem bekannt ist, dass es sich in jedoch nicht bekannt ist, dass es sich in diese Bedingung.$RE$$R$

Nehmen Sie zum Beispiel das PCP-Problem mit 4 Kacheln, deren Entscheidbarkeit offen ist. Es ist eine einfache Übung, das Problem (oder ein anderes Problem in RE) auf HALT zu reduzieren.