Vorlesung 6 Belkouchi

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.

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