チューリングマシンによる加算の実装例：シミュレーターでステップを追う
はじめに：チューリングマシンによる計算とは
前回の記事では、チューリングマシンの基本的な構成要素と動作原理について解説しました。チューリングマシンは、簡単な仕組みでありながら、現代のコンピュータが行うあらゆる計算を実行できる究極の計算モデルとして知られています。しかし、その抽象的な定義から、「実際にどのように計算を行うのか」という具体的なイメージを持つことは容易ではないかもしれません。
本記事では、チューリングマシンが具体的な計算を行う例として、「2つの自然数の加算」を取り上げます。加算という身近な演算をチューリングマシンでどのように実現するのかを解説し、その動作をシミュレーターで追体験することを通じて、チューリングマシンによる計算のメカニズムへの理解を深めることを目指します。
加算問題のチューリングマシンによる表現
まず、チューリングマシンが加算を行うために、計算対象となる数値をテープ上にどのように表現するかを決める必要があります。ここでは、最も単純な方法として「単項表現」を用います。
単項表現では、自然数 $n$ を $n$ 個の記号 1 の列で表現します。例えば、数値 3 は 111、数値 2 は 11 と表現されます。
2つの自然数 $a$ と $b$ の加算 $a+b$ を計算する場合、これらをテープ上の記号列として「1の列（$a$個） # 1の列（$b$個）」のような形式で与えることとします。# は2つの数値を区切るための特殊な記号です。例えば、3 + 2 を計算する場合、初期テープ内容は ...B111#11B... のようになります（Bはブランク記号）。
加算の結果は、テープ上に $a+b$ 個の 1 が並んだ状態（例: ...B11111B...）となることを目指します。
加算アルゴリズムの概要
1の列（$a$個） # 1の列（$b$個） という形式で与えられたテープ内容を、1の列（$a+b$個） に変換するアルゴリズムを考えます。様々な方法が考えられますが、ここでは比較的簡単な方法を採用します。
- テープ上の最初の
#記号を探します。 #記号を1に書き換えます。これでテープ上には $a$個の1、#が1になった記号、$b$個の1が並び、合計 $a+b+1$ 個の1がある状態になります。- 最初の
1を探し、それをブランクBに書き換えます。 - ヘッドをテープの右端まで移動させます。
- 右端のブランク
Bを1に書き換えます。 - ステップ3に戻り、テープの左端に残っている最初の
1を削除し、右端に1を追加するという操作を繰り返します。 - この操作を $a$ 回繰り返すと、左側の $a$ 個の
1が全てブランクに置き換えられ、右側に $a$ 個の1が追加された状態になります。 - テープ全体を見ると、$a$個のブランク、$#$が置き換わった
1、$b$個の1、そして追加された$a$個の1が並んでいます。先頭のブランク列の右にある1の列は、$1$（元の#） $+ b$個（元の右側の1）$+ a$個（追加された1）で、$a+b+1$個の1になっています。 - しかし、目標は $a+b$ 個の
1です。ステップ2で#を1に置き換えたことで、余分な1が1つ増えています。そこで、右端に移動させる操作を $a$ 回繰り返した後、左端に残った $a$個のブランクの右にある最初の1をブランクに置き換える最終処理を加えます。 - 最後に、ヘッドをテープの左端（最初の
1が現れる位置）まで移動させ、停止します。
このアルゴリズムをより単純化するために、少し異なるアプローチをとることもできます。例えば：
- テープ上の最初の
#を探し、それを1に書き換えます。 - ヘッドを一番左に戻り、最初の
1を探し、それをブランクに書き換えます。 - ヘッドを一番右に移動させます。
- 一番右の
1を探し、それをブランクに書き換えます。 - ヘッドを一番左に戻り、まだ
1が残っていればステップ2に戻ります。 - 全ての
1が消えたら（つまり、元の数が0になったら）、停止します。これは加算ではありませんね。
より一般的な方法として、最初の 1 の列と二番目の 1 の列を連結する方法があります。
- テープ上の最初の
1を探し、それをブランクに置き換えます。 - ヘッドを右に移動させ、最初のブランクにぶつかるまでスキップします。これは、元の
#が1に置き換わった後、右側の1の列の末尾、あるいはそれより右側のブランクになります。 - 直前に通過した記号が
#から置き換わった1であることを確認し、その右隣のブランクに1を書き込みます。 - ヘッドを左に移動させ、最初のブランクにぶつかるまでスキップします。これは、ステップ1で
1を置き換えた位置のすぐ右隣になります。 - 左端に残っている最初の
1を探し（ステップ1で置換した位置から右方向）、あればステップ1に戻ります。 - 左端に
1が見つからなくなったら、全ての1が移動されたので、テープ上の#から置き換わった1を探し、それをブランクに置き換えます。 - ヘッドを左端（結果の
1の列の始まり）まで移動させ、停止します。
今回は、より直感的な「片方の 1 の列を全て削除し、その数を記憶しておき、もう片方の列の右にその数だけ 1 を追加する」という方法に似たアプローチを考えます。ただし、チューリングマシンには「数を記憶する」ためのメモリはありません。状態を使ってこれを実現する必要がありますが、状態数が増えて複雑になります。
シンプルな方法として、前述の「# を 1 に置き換え、左側の 1 を一つずつ消しながら右端に追加する」アルゴリズムの変種を考えます。
アルゴリズム詳細（例：3+2 を計算する 111#11 の場合）
- 初期状態：テープは
...B 1 1 1 # 1 1 B...ヘッドは最初の1の上にいるとします。 - 最初の
1をBに書き換え、ヘッドを右に移動し始めます。 - 右方向へ移動しながら、最初の
Bにぶつかるまで1と#をスキップします。 Bにぶつかったら、それを1に書き換えて、ヘッドを左に移動し始めます。- 左方向へ移動しながら、最初の
Bにぶつかるまで1と#をスキップします。 Bにぶつかったら、その右隣の記号を確認します。もしそれが1であれば、ステップ2に戻り、その1をBに書き換える操作を繰り返します。- ステップ6で右隣の記号が
1ではなく#であった場合、それは左側の全ての1を処理し終えたことを意味します。 - 今、ヘッドは左端の
Bの右隣（元の#の位置）にいます。この#を1に書き換えます。 - ヘッドを一番左に戻り、最初の
1がある位置で停止します。
このアルゴリズムでは、入力が 111#11 の場合、
* 最初の 1 (左端) を B に → B11#11
* 右端に移動し B を 1 に → B11#111 (ヘッドは一番右の 1 の右の B にいてそれを1にした後、左に戻り最初のBの右まで来る)
* 次の 1 (左から2番目) を B に → BB1#111
* 右端に移動し B を 1 に → BB1#1111
* 次の 1 (左から3番目) を B に → BBB#1111
* 右端に移動し B を 1 に → BBB#11111
* 左端の B の右隣を見ると # なので、左側の 1 は全て移動済み。
* # を 1 に → BBB11111
* ヘッドを一番左に戻る → 最初の 1 (元の#) の上で停止。テープは ...BB B 1 1 1 1 1 B... となり、3+2=5 が正しく計算されています。
チューリングマシンの定義
上記のアルゴリズムを実現するためのチューリングマシンを定義します。チューリングマシンは以下の要素で構成されます。
- 状態の有限集合 Q: 例として、$q_0$ (初期状態), $q_1$ (左端の1を消して右へ移動), $q_2$ (右端のBを探して左へ移動), $q_3$ (左端のBを探して右へ移動), $q_f$ (停止状態) など。
- アルファベット Σ: テープ上に書き得る記号の有限集合。ここでは ${1, #, B}$ とします。
- 遷移関数 δ: $(現在の状態, 読み取った記号) \to (次の状態, 書き込む記号, ヘッドの移動方向)$ という写像。ヘッドの移動方向は L（左）、R（右）、S（停止）です。
- 開始状態 q₀: 計算を開始する状態。
- 受理状態（または停止状態）Q_accept / Q_halt: 計算が終了する状態。今回は $q_f$ を停止状態とします。
遷移関数 δ を表形式で示します（これはあくまで一例です。アルゴリズムの解釈によって遷移は変わります）。
| 現在の状態 | 読み取った記号 | 書き込む記号 | 移動方向 | 次の状態 | 説明 |
| :--------- | :------------- | :----------- | :------- | :------- | :--------------------------------------- |
| $q_0$ | 1 | B | R | $q_1$ | 左端の 1 を消して右へ 이동開始 |
| $q_0$ | # | 1 | R | $q_1$ | # が先頭にある場合は # を 1 にし右へ |
| $q_0$ | B | B | S | $q_f$ | 空のテープなら停止 |
| $q_1$ | 1 | 1 | R | $q_1$ | 右へスキップ (1) |
| $q_1$ | # | # | R | $q_1$ | 右へスキップ (#) |
| $q_1$ | B | 1 | L | $q_2$ | 右端の B を 1 にし左へ移動開始 |
| $q_2$ | 1 | 1 | L | $q_2$ | 左へスキップ (1) |
| $q_2$ | # | # | L | $q_2$ | 左へスキップ (#) |
| $q_2$ | B | B | R | $q_3$ | 左端の B に到達。右隣を確認するため右へ |
| $q_3$ | 1 | B | R | $q_1$ | 右隣が 1 なら、それを消して再び右へ移動 |
| $q_3$ | # | 1 | S | $q_f$ | 右隣が # なら、加算終了。# を 1 にし停止 |
| $q_3$ | B | B | S | $q_f$ | (エラーケースまたは特殊ケース) |
補足: 上記の遷移表は簡易的なものであり、実際のシミュレーター実装には詳細な状態設計が必要です。特に、入力が 1#1 や 11# のような場合、テープの端の処理や B の扱いは注意が必要です。上記の表は、あくまで「1の列 # 1の列」という標準的な入力形式を想定したアルゴリズムの一例を示しています。
シミュレーターでの動作確認
この遷移表をもとに、お手元のチューリングマシンシミュレーターで機械を構成し、動作を追ってみましょう。シミュレーターでは、以下の要素が通常表示されます。
- テープ: 現在のテープの内容と、各セルの記号が表示されます。
- ヘッド: テープ上のどのセルを読んでいるか、その位置が示されます。
- 現在の状態: 機械が今どの状態にあるかが表示されます（例: $q_0$, $q_1$ など）。
- 遷移: 現在の状態と読み取った記号に基づき、どのルール（遷移関数 $\delta$ のエントリ）が適用され、次の状態、書き込む記号、ヘッドの移動方向が決定されるかが表示されます。
- ステップ実行/自動実行: 1ステップずつ機械の動作を進めたり、自動で停止状態まで実行させたりできます。
例えば、入力 11#1 (2+1) に対してシミュレーターを実行すると、以下のようなステップが視覚的に表示されるはずです。
- 初期状態 $q_0$、テープは
...B 1 1 # 1 B...、ヘッドは最初の1の上。 遷移: $(q_0, 1) \to (q_1, B, R)$ テープ:...B B 1 # 1 B...、ヘッドは2番目の1の上、状態 $q_1$。 - 状態 $q_1$、読み取り
1。 遷移: $(q_1, 1) \to (q_1, 1, R)$ テープ:...B B 1 # 1 B...、ヘッドは#の上、状態 $q_1$。 ... (右方向への移動が続く) - 状態 $q_1$、読み取り
B(右端)。 遷移: $(q_1, B) \to (q_2, 1, L)$ テープ:...B B 1 # 1 1...、ヘッドは右から2番目の1の上、状態 $q_2$。 ... (左方向への移動が続く) - 状態 $q_2$、読み取り
B(左端のB)。 遷移: $(q_2, B) \to (q_3, B, R)$ テープ:...B B 1 # 1 1...、ヘッドは左から2番目のBの上、状態 $q_3$。 - 状態 $q_3$、読み取り
1(左から3番目の1)。 遷移: $(q_3, 1) \to (q_1, B, R)$ テープ:...B B B # 1 1...、ヘッドは#の上、状態 $q_1$。 ... (再び右端への移動) - 状態 $q_1$、読み取り
B(右端)。 遷移: $(q_1, B) \to (q_2, 1, L)$ テープ:...B B B # 1 1 1...、ヘッドは右から2番目の1の上、状態 $q_2$。 ... (左方向への移動が続く) - 状態 $q_2$、読み取り
B(左端のB)。 遷移: $(q_2, B) \to (q_3, B, R)$ テープ:...B B B # 1 1 1...、ヘッドは左から2番目のBの上、状態 $q_3$。 - 状態 $q_3$、読み取り
#。 遷移: $(q_3, #) \to (q_f, 1, S)$ テープ:...B B B 1 1 1 1...、ヘッドは#が1に置き換わったセルの上、状態 $q_f$ (停止)。
最終的なテープの状態は ...B B B 1 1 1 B... となり、最初の 1 の列から数えて3つの 1 が並んでいます。これは 2 + 1 = 3 という正しい計算結果を示しています。
シミュレーターの各ステップでのテープ内容、ヘッド位置、状態、そして適用される遷移ルールを注意深く観察することで、抽象的な遷移関数がどのように具体的なテープ操作や計算手順に対応しているのかを視覚的に理解することができます。
まとめ
本記事では、チューリングマシンがどのようにして具体的な計算を行うのかを理解するために、「2つの自然数の加算」を例に解説しました。単項表現で数値を表現し、特定のアルゴリズムに基づいてテープ上の記号を操作することで加算が実現できることを示しました。また、そのアルゴリズムを遷移関数として定義し、シミュレーター上でその動作を追体験することの重要性を述べました。
チューリングマシンによる加算は、非常に単純な計算の例ですが、この仕組みを応用することで、より複雑な計算も原理的には実行可能です。シミュレーターを活用し、様々な入力に対してこの加算機を動かしてみたり、他の簡単な計算（例：特定の記号列をコピーする、回文を認識するなど）を行うチューリングマシンを自分で設計してみたりすることで、チューリングマシンの計算能力とその限界について、より深く探求することができるでしょう。
チューリングマシンは計算機科学の基礎であり、その動作原理を深く理解することは、コンピュータやアルゴリズムの本質を捉える上で非常に役立ちます。ぜひシミュレーターを活用して、自らの手を動かしながら学習を進めてください。