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

Maria Michel-Suarez Funktionsklassen1.png

Alternative Darstellung (Marlene Knoche)

Simaknoc_trichter_semi_entsch_TM.png

  • für entscheidbare Sprachen

Sistluet_Trichter_entscheid.png

Alternative Darstellung (Marlene Knoche)

Simaknoc_trichter_entsch_TM.png

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.