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 es eine Funktion f:N→M gibt, die surjektiv und Turing-berechenbar ist.