Kann mir jemand den Unterschied erklären?
Ebenso Turing-entscheidbar und Turing-erkennbar??
Eine Menge M ist genau entscheidbar, genau wenn es eine Turing-Maschine A existiert, die M = L(A) akzeptiert und auf JEDER Eingabe w aus Sigma-Stern anhält.
Eine Sprache L ist Turing-erkennbar, wenn es eine Turingmaschine A existiert, die L akzeptiert, dh für die gilt L = L(A)
Bsp: du hast irgendein beliebiges Wort "abcde", und du gibt dieses wort in die Turingmaschine(TM) ein, wenn die TM nach dem Einlesen von "abcde" zum Endzustand kommt, dann wird das wort von der Turingmaschine akzeptiert.
Mir ist dieser Unterschied auch noch nicht ganz klar und ich bin mir nicht sicher, ob ich es jetzt richtig verstanden habe.
entscheidbar bedeutet, dass die Turingmaschine bei jedem beliebigen Wort (auch bei nicht akzeptierten Wörtern) entweder den accept oder den reject zustand erreicht aber nicht die ganze zeit weiterrechnet
und erkennbar bedeutet, dass die Turinmaschine nur bei akzeptierten Worten einen Endzustand erreicht aber bei nicht akzeptierten Wörtern eventuell ewig weiterrechnet.
Mit akzeptieren Wörtern meine ich in dem Fall Wörter aus L für L = L(A)
Hab ich das jetzt richtig verstanden/wiederholt?
