Wie kann man alle Turing-Maschinen auflösen?

Question

Warum ist das wahr: "Dortsind zählbar viele Turing-Maschinen "

In der ersten Antwort für diese Frage wird eine Beschreibung des Aufzählens aller Turing-Maschinen gegeben.

Es ist alles klar, außer einem Teil: Woher wissen Sie, ob eine Zeichenfolge eine gültige Kodierung einer Turingmaschine ist?In Schritt 3 muss der Algorithmus prüfen, ob eine Zeichenfolge eine gültige Kodierung einer Turingmaschine ist.Wie ist das gemacht?

Answer 1

Eine Turing-Maschine hat eine Darstellung als Zeichenfolge.Genauer gesagt, Sie schreiben die Übergangsfunktion .Denken Sie dazu einfach als einen großen Tisch an, in jeder Zeile zwei Zustände einen Buchstaben und einen Kopfübergang (L für links oder r nach rechts).

Nun, codieren Sie jetzt jeden Eintrag der Übergangsfunktionstabelle und den Speicherplatz zwischen ihnen mit 3 Nullen (es ist wie eine "magische Zahl", also würden wir wissen, wohin die Einträge starten und enden).Jeder Eintrag enthält zwei Zahlen - jede Zahl, die einen Zustand darstellt, ein weiteres Bit für den Buchstaben und ein weiteres Bit für den Kopfübergang (sagen 1 wäre R und 0 ist l).

zwischen den beiden Zahlen und den anderen Bits setzen 2 weitere Nullen, nur so dass Sie zwischen ihnen unterscheiden könnten.

Nun, um auf allen Turing-Maschinen aufzulinern, einfach auf alle Saiten aufzählen und überprüfen, ob sie sich in dem oben beschriebenen Format befinden