Benutzer:Maria Michel-Suarez

Aus ProgrammingWiki

Turing-Maschine als Akzeptator

Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptator an:

• für semi-entscheidbare Sprachen

• für entscheidbare Sprachen

Turing-Aufzählbarkeit, Turing-Entscheidbarkeit (Max Wielsch, Raik Bieniek, Ingo Körner, Christof Ochmann)

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

Sei A ein Alphabet, $M \subseteq A^*$. M heißt Turing-entscheidbar, falls die charakteristische Funktion $\chi_M$ Turing-berechenbar ist.

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