ue5

Aus ProgrammingWiki
< BuK < IIm11 < Studenten < simawiel

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.