Turing erkennbar => aufzählbar

10

Ich erhalte den Beweis, von einem Enumerator zu einer Turing-Maschine zu wechseln (führen Sie den Enumerator weiter aus und prüfen Sie, ob er mit der Eingabe übereinstimmt), aber ich sehe nicht, wie der andere Weg funktioniert.

Gemäß meinen Notizen und dem Buch (Einführung in die Theorie der Berechnung - Sipser) schreiben wir grundsätzlich alle Kombinationen des Alphabets, um den Turing-Enumerator von einer Turing-Maschine zu erhalten. Anschließend führen Sie das TM für diese Eingabe aus. Wenn es das Ausdrucken akzeptiert, ersetzen Sie es durch eine neue Zeichenfolge, die ad infinitum wiederholt wird.

Das Problem, das ich habe, ist sicherlich, dass die Sprache entscheidbar sein muss. Andernfalls könnte es beim dritten Wort in einer Endlosschleife hängen bleiben, die dazu verdammt ist, niemals die gesamte Sprache zu akzeptieren oder abzulehnen und mit Sicherheit niemals die ganze Sprache auszudrucken.

Was vermisse ich?

T. Kiley
quelle

Antworten:

9

MMMM

w1,S1##wn,SnwiSiMwinMwi

Führen Sie nun die folgende Schleife aus

  1. wΣSM#w,S
  2. M
  3. MM
  4. MM
  5. Gehe zu Schritt 1.

wΣM

Dave Clarke
quelle
4
aka "Taubenschwanz".
Kaveh