通过图灵机实现队列

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