Implementing a queue by Turing machine [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. 开发者_JAVA技巧 Closed 10 years ago.

How can I implement queue by Turing machine?

---

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