Ich habe gesehen, wie Turingmaschinen mit unendlichen Bändern in einer und in zwei Richtungen dargestellt wurden. Gibt es einen Unterschied in der Leistung solcher Turingmaschinen oder sind sie grundsätzlich gleichwertig? In meinem Kopf denke ich, dass sie gleichwertig sind, da ich denke, dass es eine Möglichkeit geben muss, das unendliche Zwei-Wege-Band als ein unendliches Ein-Wege-Band darzustellen, aber ich kann anscheinend keinen Beweis oder kein Beispiel finden.
turing-machines
user2795095
quelle
quelle
Antworten:
Sie haben eine äquivalente Rechenleistung. Alles, was mit einer dieser beiden Arten von Turing-Maschinen berechnet werden kann, kann mit der anderen Art berechnet werden. Schauen wir uns an, wie man eine Turing-Maschine mit einem doppelt unendlichen Band auf einer Turing-Maschine mit einem einfach unendlichen Band simuliert.
Die Idee ist, Ihr doppelt unendliches Band in zwei Teile zu schneiden, so dass Sie zwei einfach unendliche Bänder haben, ein linkes und ein rechtes, die Sie letztendlich zusammenführen werden. Sie können die Enden mit einer Bandposition markieren, die ein spezielles EOF-Symbol enthält. Sie duplizieren auch Ihr endliches Steuerelement, sodass Sie zwei identische endliche Steuerelemente haben. Sie gehen davon aus, dass Sie über ein Steuergerät verfügen (siehe unten). Wenn das linke Gerät versucht, über das rechte Ende seines Bandes hinauszugehen, leitet es das Steuerelement an das rechte Gerät an der am weitesten links liegenden Bandposition (kurz vor dem) linkes Ende des rechten Bandes). Und umgekehrt, wenn Sie versuchen, das linke Ende des rechten Bandes zu passieren.
Jetzt können wir die beiden Halbbänder zusammenführen, indem wir beispielsweise das rechte auf das linke falten. Dazu drehen Sie die rechte Bandhälfte um und achten darauf, die Übergänge entsprechend zu ändern, indem Sie rechts gegen links und links gegen rechts austauschen. Dann verschmelzen Sie die beiden halben Bänder zu einem einzigen Band mit Symbolpaaren, einem linken und einem rechten, wobei jede Komponente möglicherweise leer ist.
Sie ändern die Übergänge beider Maschinen erneut, sodass die linken (bzw. rechten) Übergänge nur die linken (bzw. rechten) Teile der Paare auf dem Band verwenden und ändern. Dann führen Sie die Steuerung der beiden Maschinen durch einfache Mengenvereinigung für Zustände bzw. für Übergänge zusammen.
Sie fügen für jeden vorhandenen Status eine Reihe von Übergängen hinzu, sodass das Bandsymbol, wenn es EOF ist, zum vorherigen Bandspeicherort (dem ersten Nicht-EOF-Speicherort) zurückkehrt und der Status zu seinem chiralen Gegenstück wechselt: Wenn es ein linker ist (bzw. rechts) Zustand ändert sich zu seinem rechten (bzw. linken) Gegenstück. Das ist das Steuergerät.
Ich habe vielleicht ein Detail vergessen, aber das ist die allgemeine Idee der Konstruktion. Der Beweis bleibt als Vollstreckung.
Natürlich muss das ursprüngliche Band (Eingang) entsprechend geändert werden. Dies kann jedoch vereinfacht werden, indem der Eingang (falls endlich) vollständig auf der linken Seite (die nicht umgedreht ist) des Bandschnitts platziert wird.
Dann legen Sie den Schraubenzieher weg, da dies für die Kinder gefährlich sein kann.
PS Ich habe nur gezeigt, dass das doppelt unendliche Band mit einem einfach unendlichen Band simuliert werden kann. Das Gegenteil scheint zu offensichtlich.
quelle