Implementieren einer Warteschlange durch Turing-Maschine

Question

Wie kann ich Warteschlange durch Turing-Maschine implementieren?

Answer 1

Nur für den Fall andere Studenten kommen nach einer Antwort auf diese Frage suchen, ist hier eine Idee ...

Wir werden eine Multi-Band TM verwenden, wie möglich, dies so schmerzlos zu machen. Lassen Sie eines Ihrer zusätzlichen Bänder die Warteschlange sein, die Sie implementieren möchten. Um etwas zur Warteschlange hinzuzufügen, bewegen Sie sich nach rechts, bis Sie ein leeres Quadrat treffen, und fügen Sie dann Ihr Symbol zur Warteschlange hinzu. Um etwas aus der Warteschlange zu entfernen, bewegen Sie sich nach links, bis Sie eine Leerstelle (vorausgesetzt, dieses Band beginnt mit einem einzelnen leeren Quadrat), bewegen Sie sich nach rechts, und entfernen Sie, was auf dem Band ist und ein Leerzeichen an seiner Stelle. Also, mit einer leeren Warteschlange beginnen, wo D sind leer und Band Alphabet ist abc, hier ist, wie die folgende Transaktion Sequenz aussehen:

enqueue(a) (1- 3) 
    enqueue(b) (4- 5) 
    enqueue(c) (6- 7) 
    dequeue(-) (7-11) 
    enqueue(c) (12-15) 
    dequeue(-) (16-20) 
    enqueue(b) (21-24) 

Hier ist die Spur der TM auf der Warteschlange Band:

1. DD   2. DDD   3. DaD   4. DaDD  5. DabD 
    ^   ^   ^   ^   ^

    6. DabDD  6. DabcD  7. DabcD  8. DabcD  9. DabcD 
     ^   ^   ^   ^   ^

    10. DabcD  11. DDbcD  12. DDbcD  13. DDbcD  14. DDbcDD 
     ^   ^   ^   ^   ^

    15. DDbccD  16. DDbccD  17. DDbccD  18. DDbccD  19. DDbccD 
     ^   ^   ^   ^   ^

    20. DDDccD  21. DDDccD  22. DDDccD  23. DDDccDD 24. DDDccbD 
     ^   ^   ^   ^   ^