チューリングマシンによるスタック操作（Push/Pop）：シミュレーターで追う動作ステップ
はじめに
このサイトでは、チューリングマシンの動作シミュレーションを通じて、計算理論の基礎を視覚的に理解することを目指しています。今回の記事では、計算機科学で広く利用される基本的なデータ構造の一つである「スタック」を、チューリングマシン上でどのように実現し、その主要な操作であるPush（データの追加）とPop（データの取り出し）がどのように行われるかを解説します。
スタックは「Last-In, First-Out」（後入れ先出し）の原則に従うデータ構造であり、その抽象的な性質をチューリングマシンのテープ上での具体的な記号操作として表現することは、計算モデルとしてのチューリングマシンの能力を理解する上で非常に有益です。シミュレーターを活用しながら、抽象的な概念がどのように具体的な動作に落とし込まれるかを一緒に追ってみましょう。
チューリングマシンでのスタック表現
チューリングマシン上でスタックを表現するためには、テープの特定領域をスタック領域として使用します。ここでは、テープの右方向に向かってデータが積まれていく形式を採用し、スタックの終端（一番上に積まれたデータの次）を特別な記号でマークすることにします。
例えば、スタックにA、B、Cというデータがこの順でPushされた場合、テープ上では以下のように表現されるとします。
...□ □ [スタック開始マーカー] A B C [スタック終端マーカー] □ □...
ここで、
* □ は空白記号とします。
* [スタック開始マーカー] はスタック領域の始まりを示す記号（例: [）です。
* [スタック終端マーカー] は現在スタックの一番上にあるデータの次を示す記号（例: ]）です。
* スタック内のデータは、空白やマーカーと区別できるアルファベットを使用します。
この表現において、スタックの「トップ」は常に[スタック終端マーカー]の左隣の記号、またはスタックが空の場合は[スタック開始マーカー]の右隣の記号の位置に存在すると考えることができます。Push操作ではこの終端マーカーの直前にデータを書き込み、Pop操作では終端マーカーの直前のデータを読み取って削除します。
使用するアルファベットは、データに使用する記号（例: A, B, C, 0, 1など）、空白記号（□）、そしてスタック開始・終端マーカー（例: [, ]）を含む必要があります。
Push操作の動作ステップ
スタックに新しいデータ（例: X）をPushする操作を考えます。現在のスタックが [ A B C ] とテープに表現されているとします。
目標の状態は [ A B C X ] となることです。
この操作を実現するためのチューリングマシンの基本的な動作ステップは以下のようになります。
- スタック終端への移動: ヘッドは現在の位置からテープを右方向に移動し、
[スタック終端マーカー]（]）を探します。 - 終端マーカーの右への退避:
]を見つけたら、その記号を一時的に記憶（状態や特別なテープ領域を利用する構成もありますが、ここでは単純にテープ上の別の場所へ移動させるイメージで解説します）し、その位置を空白にします。あるいは、より単純に、]の直前に新しい記号を挿入するために、]より右にある全ての記号を一つ右にシフトさせる動作を行います。ここでは後者の「シフト」の考え方で解説します。 - 記号の右シフト:
]を見つけたら、ヘッドを一つ右に移動します。そこから右方向の空白でない最初の記号まで移動し、その記号を読み取ります。 - シフト実行: 読み取った記号を一つ右のセルに書き込みます。そしてヘッドを元の位置（一つ左）に戻し、その位置の記号を読み取ります。これを繰り返し、
]まで左に戻りながら、読み取った記号を一つ右にずらして書き込んでいきます。最終的に、]も一つ右にシフトされます。この結果、元の]があった位置が空白になります。 - 新データの書き込み: 空白になった元の
]の位置に、Pushしたい新しいデータXを書き込みます。 - ヘッドの移動: 操作完了後、ヘッドを次の操作に備えた位置（例: スタック終端マーカーの直前、または開始位置）に移動させます。
シミュレーター上での状態遷移は、現在の状態と読み取った記号に応じて、「書き込む記号」「ヘッドの移動方向（L/R/S）」「次の状態」が決定されるという形で表現されます。
例えば、スタック終端を探す状態（find_end）で ] を読み取った場合、「書き込む記号：] （動かさない場合）、ヘッド移動方向：R、次の状態：shift_symbols」のような遷移が考えられます。shift_symbols 状態では、右端まで移動して記号を読み取り、それを左に戻って書き込むという一連の動作を繰り返すことになります。
Push操作の動作例：スタック [ A B ] に C をPush
| Step | 現在の状態 | 読み取り | 書き込み | ヘッド移動 | 次の状態 | テープの状況 (ヘッド位置^) |
| :--- | :--------- | :------- | :------- | :--------- | :----------- | :------------------------- |
| 0 | q_start | [ | [ | R | find_end | [ ^A B ] |
| 1 | find_end | A | A | R | find_end | [ A ^B ] |
| 2 | find_end | B | B | R | find_end | [ A B ^] |
| 3 | find_end | ] | ] | R | shift_init | [ A B ]^ |
| 4 | shift_init| □ | □ | L | shift_copy | [ A B ]^□ |
| 5 | shift_copy| ] | □ | L | shift_copy | [ A B ^] |
| 6 | shift_copy| B | ] | L | shift_copy | [ A ^B ] |
| 7 | shift_copy| A | B | L | shift_copy | [ ^A B ] |
| 8 | shift_copy| [ | A | R | write_C | [ A^ B ] |
| 9 | write_C | □ | C | R | move_end | [ A C^ ] |
| 10 | move_end | ] | ] | S | q_accept | [ A C ]^ |
※これは動作の一例です。具体的な遷移設計は多岐にわたります。特にシフト操作は、記号を一時保持するなど、より複雑な状態遷移やアルファベット設計が必要になる場合があります。上記の例は、shift_copy 状態で一つ左の記号を読み取り、その読み取った記号を現在の位置に書き込むという、簡略化した表現を含んでいます。シミュレーターで再現する際は、一時的な記号や状態を工夫する必要があります。
Pop操作の動作ステップ
スタックからデータをPopする操作を考えます。現在のスタックが [ A B C ] とテープに表現されているとします。
目標の状態は [ A B ] となり、取り出したデータ C を知ることです。チューリングマシンでは「データを取り出す」という概念を、そのデータを読み取り、特定の状態に到達するか、別のテープ領域に書き込むことで実現します。ここでは、読み取った記号を記憶した状態で終了する、という簡単な形式で考えます。
- スタック終端への移動: ヘッドは現在の位置からテープを右方向に移動し、
[スタック終端マーカー]（]）を探します。 - Popするデータの特定:
]を見つけたら、ヘッドを一つ左に移動します。そこにある記号が、Popするデータです（この例ではC）。 - データの読み取りと削除: その記号を読み取ります（これにより、その記号が「取り出された」とみなせます）。読み取ったセルは空白記号
□で上書きします。 - 終端マーカーの移動:
]を一つ左（データのあった位置）に移動させます。これは、Popするデータがあったセルに]を書き込むことによって実現されます。 - ヘッドの移動: 操作完了後、ヘッドを次の操作に備えた位置に移動させます。
Pop操作の動作例：スタック [ A B C ] からデータをPop
| Step | 現在の状態 | 読み取り | 書き込み | ヘッド移動 | 次の状態 | テープの状況 (ヘッド位置^) |
| :--- | :--------- | :------- | :------- | :--------- | :----------- | :------------------------- |
| 0 | q_start | [ | [ | R | find_end | [ ^A B C ] |
| 1 | find_end | A | A | R | find_end | [ A ^B C ] |
| 2 | find_end | B | B | R | find_end | [ A B ^C ] |
| 3 | find_end | C | C | R | find_end | [ A B C ^] |
| 4 | find_end | ] | ] | L | pop_read | [ A B ^C ] |
| 5 | pop_read | C | □ | S | move_end_marker| [ A B ^□ ] |
| 6 | move_end_marker| □ | ] | S | q_accept_C | [ A B ^] |
※q_accept_C は、「PopしたデータがCであった」ことを示す状態と考えることができます。実際には、Popしたデータ自体を計算結果として出力するための複雑なメカニズムが必要になる場合もありますが、ここでは「スタックのトップを削除し、終端マーカーを移動させる」というLIFOの核心部分の動作に焦点を当てています。
シミュレーターでの確認と理解深化
これらのPushおよびPopの動作は、チューリングマシンシミュレーター上で具体的な状態遷移ルール（遷移関数）を定義し、初期テープの内容を設定することで実際に動作させることができます。
シミュレーター画面で、以下のような要素と理論上の概念がどのように対応するかを確認してください。
- 状態遷移図: 理論上の遷移関数
δ(現在の状態, 読み取った記号) = (書き込む記号, ヘッド移動方向, 次の状態)がグラフィカルに表示されます。各状態がノード、遷移がエッジとして示され、ヘッドの動きに伴って現在のアクティブな状態や遷移がハイライトされることが多いです。 - テープ: テープ上の記号列がそのまま表示されます。各ステップでどのセルが読み取られ、書き換えられ、ヘッドがどこに移動したかが視覚的に追えます。スタックのPush/Pop操作によって、終端マーカーの位置やデータ記号列がどのように変化するかを確認してください。
- ヘッド位置: ヘッドが現在どのセルを見ているかが示されます。上記のステップ解説における
^マークの位置に対応します。 - 現在の状態: マシンの内部状態がリアルタイムで表示されます。上記のステップ解説における「現在の状態」に対応します。
シミュレーターでこれらの要素を注意深く追うことで、スタックという抽象的なデータ構造が、テープ上の記号の読み書きとヘッド移動というチューリングマシンの基本的な動作の組み合わせによって実現されていることを実感できるでしょう。特に、Push時の記号のシフト操作や、Pop時のデータの読み取り・削除・マーカー移動といった一連のシーケンスが、定義された遷移ルールに従って正確に実行される様子を確認することは、チューリングマシンの計算能力に対する理解を深めます。
まとめ
この記事では、チューリングマシン上でスタックを表現し、そのPushおよびPop操作を実現するための基本的な考え方と動作ステップを解説しました。スタックの「Last-In, First-Out」という性質が、テープ上の終端マーカーの位置を操作し、データの挿入や削除を行うことでどのように表現されるかを見てきました。
チューリングマシンは非常に単純な計算モデルですが、このような基本的なデータ構造やアルゴリズムを実装できる能力を持っています。これは、チューリングマシンが「計算可能」とされるあらゆる問題を解くことができるという、その普遍性を示す一例でもあります。
シミュレーターを使って実際にスタック操作を実装してみることで、遷移関数の設計の工夫や、テープ上の記号操作の面白さをより深く体験できるでしょう。この記事が、チューリングマシンの理論的な理解と、シミュレーターを用いた実践的な学習を結びつける一助となれば幸いです。