通過圖靈機實現隊列

Question

如何通過圖靈機實現隊列？

Answer 1

以防萬一別的同學過來找一個回答這個問題，這裏有一個想法......

我們將使用多帶TM只是爲了讓這個儘可能無痛。讓你的一個額外磁帶成爲你想要實現的隊列。要添加某些內容到隊列中，請向右移動，直到找到空白的方塊，然後將該符號添加到隊列中。要從隊列中刪除某些內容，請向左移動，直到找到空白爲止（假定此磁帶以一個空白方塊開始），向右移動，並刪除磁帶上的內容並在其位置放置空白。所以，從一個空白的隊列，其中d是空白的，帶字母是ABC，這裏的下列處理流程是什麼樣子：

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) 

這裏是TM的隊列磁帶上的跟蹤：

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 
     ^   ^   ^   ^   ^