BuK/IIm20/Vorlesung 6 Belkouchi

Wiki-Quelltext dieser Seite.

== Seite 30 ==

Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.

Turing-aufzählbar , wenn alle Worte von A auf einem ihrer Bänder ausgibt. Dabei dürfen Worte von M auch mehrfach ausgegeben werden.

[[Bild:Soufiane_Aufzaehlen-1-.jpg]]

M heißt Turing-entscheidbar, wenn bei Eingabe eines Wortes w feststellt, ob w zu A gehört oder nicht.

[[Bild:Soufiane_Entscheiden-1-.jpg]]