Aufgabe vollständig gelöst
-
Konfigurationen, die das Palindrom-Programm bei 1 0 1 0 1 durchläuft 5 Schritte
Das Palindrom-Programm startet auf dem Band 1 0 1 0 1, Kopf auf Zelle 0, Zustand
q0. Zählen Sie jede Konfiguration, die es durchläuft, bevor es anhält — anhand der Regeltabelle, ohne es Schritt für Schritt auszuführen — und sagen Sie dann, was diese Anzahl tut, wenn die Eingabe länger wird.-
Lesen Sie die Tabelle als Runden, nicht als Liste von Zügen. Nur eine Regel kann eine Runde eröffnen:
q0löscht das ganz linke Symbol und verzweigt je nachdem, was es gerade gelöscht hat, zuq1für eine 1 und zuq2für eine 0. Diese Verzweigung ist der gesamte Vergleichsmechanismus. Die Maschine speichert das Symbol nie auf dem Band; sie speichert es darin, in welchem Zustand sie sich befindet, sodass das spätere Testen des entgegengesetzten Endes dagegen keine zusätzlichen Züge kostet. -
Zählen Sie eine Runde auf einem Block von m Symbolen. Das Löschen des linken Endes ist 1 Zug. Der Kopf überquert dann die m − 1 noch stehenden Symbole und wendet 1 weiteren Zug auf dem Leerzeichen dahinter auf, um umzukehren. Das Löschen des rechten Endes ist 1 Zug, das Zurückgehen über die m − 2 verbleibenden Symbole entspricht m − 2 Zügen, und 1 letzter Zug auf dem Leerzeichen am linken Ende richtet die Maschine wieder nach rechts in
q0aus. -
Unser Band liefert einen Block von 5, dann 3, dann ein einzelnes Symbol — und ein einzelnes Symbol ist keine Runde.
q0löscht es,q1läuft am rechten Ende heraus und dreht um, undq1cfindet ein Leerzeichen dort, wo ein Partner sein sollte. Ein Palindrom ungerader Länge hat ein ungepaartes Zentrum, und das Finden dieses Leerzeichens ist das, was akzeptiert. -
Addieren Sie die drei, und achten Sie dann auf den Zaunpfahlfehler. 21 ist die Anzahl der Züge; der Transport zählt Konfigurationen, und 21 Züge besuchen 22 von ihnen, sobald man diejenige einbezieht, in der man begonnen hat.
-
Verallgemeinern Sie auf eine beliebige ungerade Länge n. Die Blöcke laufen n, n − 2 und so weiter hinab bis 3, wobei jeder 2m + 1 kostet und das Zentrum 3 kostet. Die Summe dieser Liste ergibt einen quadratischen Ausdruck in n, keinen linearen.
Antwort
22 Konfigurationen — 21 Züge. Der quadratische Anteil ist derjenige, den man sich merken sollte. Ein 21-Symbol-Palindrom kostet 253 Züge: 12-mal so viel Arbeit für eine 4,2-mal so lange Eingabe. Der Grund ist eher geometrischer Natur als raffiniert — die zwei verglichenen Symbole befinden sich stets an entgegengesetzten Enden dessen, was übrig ist, und es gibt nur einen Kopf, sodass jedes Paar einen vollständigen Durchlauf des verbleibenden Bandes kostet. Gibt man der Maschine ein zweites Band, wird dieselbe Aufgabe linear: Kopieren Sie die Eingabe beim Lesen hinüber, lassen Sie dann die zwei Köpfe in entgegengesetzte Richtungen laufen und vergleichen Sie in einem einzigen Durchgang, ungefähr 3n Züge. Auf einem einzigen Band gibt es keinen Platz für diese Kopie, und das Hin- und Herfahren ist erzwungen.
-
Quellen (3)
- The single-tape quadratic lower bound for palindromes: F. C. Hennie, "One-tape, off-line Turing machine computations." Information and Control 8(6), 553–578, 1965.
- Where multi-tape time complexity classes were set out: J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms." Transactions of the American Mathematical Society 117, 285–306, 1965.
- The machine itself: A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42(1), 230–265, 1937.