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.

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.