Vorlesung 6 Belkouchi

Aus ProgrammingWiki
< BuK < IIm20
Archivierte Version vom 2021-05-02T22:35:05+00:00. Aktuelle Version

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]]

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]]