チューリングマシンシミュレーター＆解説

チューリングマシンによる論理AND演算：シミュレーターで追う実現ステップ

チューリングマシンは、計算の最も基本的なモデルとして計算機科学の基礎をなす概念です。その抽象的な定義から、具体的なアルゴリズムがどのように実現されるのかを理解することは、計算のメカニズムを深く探求する上で重要となります。本記事では、チューリングマシンを用いて論理AND演算を実現する方法に焦点を当て、その設計と思考プロセスを解説します。特に、シミュレーター上で実際にどのような動作ステップを経て演算が実行されるのかを追体験できるよう、詳細な動作例を示します。

論理演算とチューリングマシン

論理演算は、コンピュータが行うすべての計算の根幹をなす基本的な操作です。AND、OR、NOTといった論理ゲートは、集積回路の基本要素でもあります。チューリングマシンは、これらの基本的な論理演算を含む、あらゆる計算可能な関数を表現できることが知られています。これは、チューリングマシンが現代のコンピュータの理論的な基礎であることを示しています。

ここでは、最も単純な二項演算である論理AND演算（$A \land B$ または $A \text{ AND } B$）を例に、チューリングマシンでの実現方法を考えてみます。論理AND演算は、2つの入力（真または偽）に対して1つの出力（真または偽）を返す演算であり、両方の入力が真の場合にのみ出力が真となります。その真理値表は以下のようになります。

| 入力 A | 入力 B | 出力 (A AND B) | | :----- | :----- | :------------- | | 偽 (0) | 偽 (0) | 偽 (0) | | 偽 (0) | 真 (1) | 偽 (0) | | 真 (1) | 偽 (0) | 偽 (0) | | 真 (1) | 真 (1) | 真 (1) |

チューリングマシンでこれを実現するためには、まず「真」と「偽」をテープ上の記号で表現する必要があります。ここでは一般的な記号として、1を真、0を偽とします。テープの空白記号はBを使用します。

チューリングマシンの設計

論理AND演算を行うチューリングマシンを設計します。入力はテープ上に、例えば ,A,B, の形式で与えられると想定します（ここではカンマ , は区切り記号として使用しないこととし、AとBが隣接して書かれているとします）。演算結果である A AND B の値（0または1）を、テープ上のどこか、例えば入力があった場所に書き出すことを目指します。

簡単な設計として、以下のような動作を考えます。 1. 初期状態でテープヘッドは1つ目の入力記号（A）の上に位置します。 2. 1つ目の入力記号を読み取ります。 3. テープヘッドを移動し、2つ目の入力記号（B）を読み取ります。 4. 読み取ったAとBの値の組み合わせに基づいて、AND演算の結果を計算します。 5. 計算結果をテープ上の所定の位置（例えば1つ目の入力があった場所）に書き込みます。 6. 停止状態へ遷移します。

この動作を実現するためのチューリングマシンの構成要素を定義します。

• 状態 (States):
  • q_init: 初期状態。1つ目の入力を読み取る。
  • q_read_B: 1つ目の入力を読み終え、2つ目の入力を読み取るためにヘッドを移動する状態。
  • q_calc_0: 入力AかBのどちらか、または両方が0であった場合に遷移し、結果として0を書き込むための状態。
  • q_calc_1: 入力AとBが両方とも1であった場合に遷移し、結果として1を書き込むための状態。
  • q_write_0: 結果0を書き込む状態。
  • q_write_1: 結果1を書き込む状態。
  • q_halt: 停止状態。
• アルファベット (Alphabet):
  • 入力アルファベット: {0, 1}
  • テープアルファベット: {0, 1, B} (Bは空白記号)
• 遷移関数 (Transition Function): δ(現在の状態, 読み取った記号) = (書き込む記号, ヘッドの移動方向, 次の状態)

遷移関数を真理値表に従って定義します。ヘッドは常に右(R)または左(L)に移動し、停止(S)する場合もあります。

• δ(q_init, 0) = (0, R, q_read_B): 1つ目が0の場合、0はそのままに右へ移動し、2つ目を読む状態へ。結果は必ず0になる経路。
• δ(q_init, 1) = (1, R, q_read_B): 1つ目が1の場合、1はそのままに右へ移動し、2つ目を読む状態へ。結果は2つ目の入力に依存する。
• δ(q_read_B, 0) = (0, L, q_calc_0): 2つ目が0の場合、0はそのままに左へ移動し、結果0を計算する状態へ。
• δ(q_read_B, 1) = (1, L, q_calc_1): 2つ目が1の場合、1はそのままに左へ移動し、結果1を計算する状態へ。
• δ(q_calc_0, 0) = (0, R, q_write_0): 結果0を書き込む場所（1つ目の入力があった場所）に戻るため左へ移動したが、再び1つ目の入力の0を読んだ状態。0はそのままに右へ移動し、書き込み状態へ。
• δ(q_calc_0, 1) = (0, R, q_write_0): 結果0を書き込む場所に戻るため左へ移動したが、再び1つ目の入力の1を読んだ状態。0はそのままに右へ移動し、書き込み状態へ。
• δ(q_calc_1, 1) = (1, R, q_write_1): 結果1を書き込む場所に戻るため左へ移動したが、再び1つ目の入力の1を読んだ状態。1はそのままに右へ移動し、書き込み状態へ。
• δ(q_write_0, 0) = (0, S, q_halt): 1つ目の入力があった場所に移動し、0を読み取ったら、その位置に結果の0を書き込み、停止。（実際には書き込む記号は0で、ヘッドはその場に留まり停止）
• δ(q_write_0, 1) = (0, S, q_halt): 1つ目の入力があった場所に移動し、1を読み取ったら、その位置に結果の0を書き込み、停止。
• δ(q_write_1, 1) = (1, S, q_halt): 1つ目の入力があった場所に移動し、1を読み取ったら、その位置に結果の1を書き込み、停止。

（注: 上記の遷移は簡略化・一例です。特に q_calc_0 や q_write_0/1 への遷移は、ヘッドがどこにいるべきか、どの記号を読み取るかで調整が必要です。例えば、結果を1つ目の入力の場所に戻って書き込む場合、q_read_B から左へ移動した後、1つ目の入力記号を読み取った時点で書き込み状態へ遷移するのが自然です。）

より洗練された遷移関数を以下に示します。入力はテープ上に B...B00B...B, B...B01B...B, B...B10B...B, B...B11B...B の形式で与えられ、ヘッドは最初の入力記号の上にいるとします。結果は最初の入力記号があった場所に上書きされます。

• δ(q_init, 0) = (0, R, q_read_second): 最初の入力が0。テープに0を書いて右へ移動。2つ目の入力を読む状態へ。結果は確定で0。
• δ(q_init, 1) = (1, R, q_read_second): 最初の入力が1。テープに1を書いて右へ移動。2つ目の入力を読む状態へ。結果は2つ目に依存。
• δ(q_read_second, 0) = (0, L, q_write_0): 2つ目の入力が0。テープに0を書いて左へ移動。結果0を書き込む状態へ。
• δ(q_read_second, 1) = (1, L, q_write_if_first_is_1): 2つ目の入力が1。テープに1を書いて左へ移動。最初の入力が1だった場合に結果1を書き込む状態へ。
• δ(q_write_0, 0) = (0, S, q_halt): 左へ移動して最初の入力位置（0）に戻った。そこに結果の0を上書き（実際には同じ記号なので変化なし）し、停止。
• δ(q_write_0, 1) = (0, S, q_halt): 左へ移動して最初の入力位置（1）に戻った。そこに結果の0を上書きし、停止。
• δ(q_write_if_first_is_1, 0) = (0, S, q_halt): 左へ移動して最初の入力位置（0）に戻った。2つ目が1でも最初の入力が0なら結果は0。そこに結果の0を上書きし、停止。
• δ(q_write_if_first_is_1, 1) = (1, S, q_halt): 左へ移動して最初の入力位置（1）に戻った。2つ目も1だったので結果は1。そこに結果の1を上書きし、停止。
• δ(q_init, B) = (B, S, q_halt): 入力が空白の場合、何もせず停止。

この設計では、q_read_secondから左に戻ることで、必ず最初の入力記号の上に戻れると仮定しています。これは入力が2記号のみで、その間に空白などが挟まらないシンプルなケースで成り立ちます。

シミュレーターで追う動作例：入力 11

それでは、上記の設計に基づき、入力テープが ...BB11BB... で、ヘッドが最初の 1 の上にある場合の動作をシミュレーターで追ってみましょう。

初期状態: * テープ: ... B B [1] 1 B B ... ([]はヘッド位置) * 状態: q_init

ステップ 1: * 現在の状態: q_init * 読み取った記号: 1 * 遷移関数: δ(q_init, 1) = (1, R, q_read_second) を適用。 * アクション: テープに 1 を書き込み (変化なし)、ヘッドを右に移動、状態を q_read_second に変更。 * テープ: ... B B 1 [1] B B ... * 状態: q_read_second

ステップ 2: * 現在の状態: q_read_second * 読み取った記号: 1 * 遷移関数: δ(q_read_second, 1) = (1, L, q_write_if_first_is_1) を適用。 * アクション: テープに 1 を書き込み (変化なし)、ヘッドを左に移動、状態を q_write_if_first_is_1 に変更。 * テープ: ... B B [1] 1 B B ... * 状態: q_write_if_first_is_1

ステップ 3: * 現在の状態: q_write_if_first_is_1 * 読み取った記号: 1 * 遷移関数: δ(q_write_if_first_is_1, 1) = (1, S, q_halt) を適用。 * アクション: テープに 1 を書き込み (結果の 1 を上書き)、ヘッドは移動せず、状態を q_halt に変更。 * テープ: ... B B [1] 1 B B ... * 状態: q_halt

結果: 状態が q_halt になったため、マシンは停止しました。テープ上の最初の入力があった位置には 1 が書き込まれており、これは 1 AND 1 の正しい結果です。

シミュレーターで追う動作例：入力 10

次に、入力テープが ...BB10BB... で、ヘッドが最初の 1 の上にある場合の動作を追ってみましょう。

初期状態: * テープ: ... B B [1] 0 B B ... * 状態: q_init

ステップ 1: * 現在の状態: q_init * 読み取った記号: 1 * 遷移関数: δ(q_init, 1) = (1, R, q_read_second) を適用。 * アクション: テープに 1 を書き込み、ヘッドを右に移動、状態を q_read_second に変更。 * テープ: ... B B 1 [0] B B ... * 状態: q_read_second

ステップ 2: * 現在の状態: q_read_second * 読み取った記号: 0 * 遷移関数: δ(q_read_second, 0) = (0, L, q_write_0) を適用。 * アクション: テープに 0 を書き込み、ヘッドを左に移動、状態を q_write_0 に変更。 * テープ: ... B B [1] 0 B B ... * 状態: q_write_0

ステップ 3: * 現在の状態: q_write_0 * 読み取った記号: 1 * 遷移関数: δ(q_write_0, 1) = (0, S, q_halt) を適用。 * アクション: テープに 0 を書き込み (結果の 0 を上書き)、ヘッドは移動せず、状態を q_halt に変更。 * テープ: ... B B [0] 0 B B ... * 状態: q_halt

結果: マシンは停止し、テープ上の最初の入力位置には 0 が書き込まれました。これは 1 AND 0 の正しい結果です。

入力 01 や 00 の場合も同様に追うことができますが、いずれの場合も q_init で 0 を読み取った経路を通るため、結果は 0 となります。

シミュレーターでの確認と学習

これらの設計と動作ステップは、チューリングマシンシミュレーターに入力して実際に実行することで、より視覚的・直感的に理解を深めることができます。

シミュレーターの状態遷移図を見ることで、各状態がどのような役割を持ち、どの記号を読み取ったときにどう遷移するのか、全体像を把握できます。テープ表示とヘッド位置、そして現在の状態表示をステップ実行と合わせて確認することで、本記事で解説したような「テープの記号がどう変化し、ヘッドがどう動き、マシンの状態がどう移り変わっていくのか」という具体的な動作プロセスを、まさに紙と鉛筆で行うシミュレーションのように追うことができます。

特に、抽象的な遷移関数 δ(q, a) = (b, d, q') が、シミュレーター上での具体的な「状態 q で記号 a を読み取ったら、テープに b を書いて、ヘッドを d 方向に動かし、次の状態を q' にする」という動作にどう対応しているかを確認してみてください。

まとめ

本記事では、チューリングマシンを使って論理AND演算を実現する基本的な方法を解説しました。テープ上の記号で論理値を表現し、状態遷移によってAND演算の真理値表に対応する処理を行うチューリングマシンを設計し、入力 11 および 10 の場合の具体的な動作ステップを示しました。

このような非常に単純な演算ですら、チューリングマシン上では複数の状態と遷移を必要とすることが分かります。しかし、この基本的なステップの組み合わせこそが、チューリングマシンがあらゆる計算可能な問題を解くことができる普遍的な計算能力を持つ根拠となります。

チューリングマシンシミュレーターを活用することで、本記事で紹介したAND演算のような基本的な処理だけでなく、より複雑なアルゴリズムがどのようにチューリングマシン上で動作するのかを体験し、計算可能性理論への理解をさらに深めることができるでしょう。