图灵机实现队列

发布于 2024-10-08 04:54:01 字数 19 浏览 2 评论 0原文

如何通过图灵机实现队列？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

阳光下慵懒的猫 2024-10-15 04:54:01

以防万一其他学生来寻找这个问题的答案，这里有一个想法......

我们将使用多磁带 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
         ^               ^               ^               ^              ^

Just in case other students come looking for an answer to this question, here's an idea...

We'll use a multi-tape TM just to make this as painless as possible. Let one of your extra tapes be the queue you want to implement. To add something to the queue, move right until you hit a blank square, then add your symbol to the queue. To remove something from the queue, move to the left until you hit a blank (assuming this tape starts with a single blank square), move right, and remove what's on the tape and put a blank in its place. So, starting with a blank queue where D is blank and tape alphabet is abc, here's how the following transaction sequence would look:

  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)

Here's the trace of the TM on the queue tape:

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

回复收藏 0 原文

~没有更多了~