computer-science - チューリングマシンによるキューの実装

Question

チューリングマシンでキューを実装するにはどうすればよいですか？

Answer 1

他の学生がこの質問に対する答えを探しに来る場合に備えて、ここにアイデアがあります...

これをできるだけ簡単にするために、マルチテープ TM を使用します。余分なテープの 1 つを、実装したいキューにします。キューに何かを追加するには、空白の四角にヒットするまで右に移動してから、シンボルをキューに追加します。キューから何かを削除するには、空白に達するまで左に移動し (このテープは単一の空白の正方形で始まると仮定します)、右に移動して、テープにあるものを削除し、その場所に空白を置きます。したがって、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
         ^               ^               ^               ^              ^