Benutzer:Maria Michel-Suarez

Wiki-Quelltext dieser Seite.

== Turing-Maschine als Akzeptator ==
Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptator an:
* für semi-entscheidbare Sprachen
[[Bild:Maria Michel-Suarez Funktionsklassen1.png|250px]]

<popup name="Alternative Darstellung (Marlene Knoche)">
[[Bild:Simaknoc_trichter_semi_entsch_TM.png]]
</popup>

* für entscheidbare Sprachen
[[Bild:Sistluet_Trichter_entscheid.png|250px]]

<popup name="Alternative Darstellung (Marlene Knoche)">
[[Bild:Simaknoc_trichter_entsch_TM.png]]
</popup>

=== 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.