Zum Inhalt springen

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

Aus Wikiversity
Register-entscheidbar

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

gilt.