– Ein Entscheidungsproblem P heißt semi-entscheidbar (d. h. einen Semi-Algorithmus haben), wenn die Sprache L aller Ja-Instanzen von P wahr ist. – (Äquivalenzproblem für DFA) Akzeptieren zwei DFAs dieselbe Sprache? Beweis: Man erinnere sich an Cantors Argument aus der ersten Vorlesung.
Wenn ein Problem halbentscheidbar ist?
Semi-Entscheidbare Probleme sind solche für die eine Turing-Maschine bei der von ihr akzeptierten Eingabe anhält, aber bei der Eingabe, die von der Turing-Maschine zurückgewiesen wird, entweder anh alten oder eine Endlosschleife durchlaufen kann. Solche Probleme werden als von Turing erkennbare Probleme bezeichnet.
Was ist ein teilweise entscheidbares Problem?
Definition: Eine deren zugehörige Sprache eine rekursiv aufzählbare Sprache ist. Entsprechend gibt es einen Algorithmus, der anhält und 1 für jede Instanz mit einer „Ja“-Antwort ausgibt, aber für Instanzen mit einer „Nein“-Antwort darf er entweder nicht anh alten oder anh alten und 0 ausgeben.
Ist das H alteproblem teilweise entscheidbar?
Alan Turing bewies 1936, dass ein allgemeiner Algorithmus, der auf einer Turing-Maschine läuft und das H alteproblem für alle möglichen Programm-Eingabe-Paare löst, notwendigerweise nicht existieren kann. Daher ist das H alteproblem für Turingmaschinen unentscheidbar.
Warum ist das H alteproblem semi-entscheidbar?
Eine Sprache heißt semi-entscheidbar, wenn es eine Turingmaschine gibt, die anhält, wenn ein Wort zu der Sprache gehört (JA-Fälle) und ablehnen oder ins Unendliche gehen kann Schleife, wenn das Wort nicht zur Sprache gehört (NO-Fall).
