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.

Sei A ein Alphabet, 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]]
[[Bild:Soufiane_Aufzaehlen-1-.jpg]]

M heißt Turing-aufzählbar, wenn es eine Funktion f:N→M gibt, die surjektiv und Turing-berechenbar ist.

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