BuK/IIm11/Studenten/simawiel/ue5

Wiki-Quelltext dieser Seite.

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

* Turing-aufzählbar

Eine Funktion f ist Turing-aufzählbar, wenn es für die Funktion f eine deterministische Turing-Maschine gibt, die für jedes Wort des Eingabe-Alphabets in einem Endzustand stoppt.

* Turing-entscheidbar

Eine Menge heißt Turing-entscheidbar, wenn es für die charkteristische Funktion $\chi_M$ eine deterministische Turing-Maschine gibt, die für jedes Wort des Eingabe-Alphabets in einem Endzustand stoppt.