Registermaschine/Teilmenge der natürlichen Zahlen/Entscheidbarkeit/Definition

Register-entscheidbar

Es sei  $T\subseteq \mathbb{N}$  eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge $R$-entscheidbar (oder Register-entscheidbar) ist, wenn es ein Programm $P$ für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

$n\in T\text{ genau dann, wenn }P(n)\text{ die Ausgabe }0\text{ besitzt}$

gilt.