Registermaschine/Entscheidbarkeit und Aufzählbarkeit/Fakt

Es sei ${}T\subseteq \mathbb {N}$ eine Teilmenge der natürlichen Zahlen.

Dann ist ${}T$ genau dann ${}R$-entscheidbar, wenn sowohl ${}T$ als auch das Komplement ${}\mathbb {N} \setminus T$ ${}R$-aufzählbar ist.

Zum Beweis, Alternativen Beweis erstellen