Wie verschiebe ich Daten in Turing-Maschine?

Question

Beim Konvertieren einer Multitape-Turing-Maschine in eine äquivalente Single-Tape-Turing-Maschine müssen wir die Daten verschieben und eine Leerstelle einfügen. zB:

Multitape = [1,2,3,4] [5,6,7,8] [9,10,11,12] 
Equivalent singletape = [1,2,3,4,#,5,6,7,8,#,9,10,11,12] 
consider this transition function in multitape turing machine : 
[(q1,4) = (q2,4,R) and similar for others] 

nach diesem Übergang ein nächstes Element tape1 ist Blank Aber in einzelnen Band

[(q1,4) = (q2,4,R) and for others] 

Nach diesem Übergang nächste Element tape1 ist #, also müssen wir verschieben verbleibenden Daten einfügen an dieser Stelle leer. Wie geht das? Bitte geben Sie Antworten in Bezug auf die Übergangsfunktion.

Answer 1

Ihre Übergangsfunktion liest nur das erste Band. Ein Übergang für die three.tape Machien sollte etwa so aussehen:

(q1,4,5,10) = (q2,4,R,6,L,11,R) 

, weil Sie Anweisungen für alle drei Bänder benötigen.

Für die Verschiebung: es gibt keinen besseren Weg, als alle Daten auf einer Seite der aktuellen Position um eins zu verschieben. Zum Beispiel:

1. Mark aktuelle Position
2. Run auf das am weitesten rechts stehenden Symbol
3. Bewegung am weitesten rechts stehende Symbol eines nach rechts
4. Verschieben nächstes Symbol auf der auf den rechten Seite eine Position nach links und so weiter bis zum markierten Symbol