チューリングマシン

はじめに

チューリングマシンとは、1936年にイギリスの数学者アラン・チューリングが考案した、「計算とは何か」を定義するための数学的モデルです。

チューリングが登場する以前、数学者たちは「計算とは何か」「すべての数学的な問題は計算で解けるのか」という直感的な疑問を抱えていましたが、「計算」の厳密な定義がありませんでした。

そこで、チューリングマシンで実行できる処理のことだけを『計算』と定義しました。

概要

チューリングマシンは、単純な4つの要素だけで構成されています。

• 紙テープ：無限に長く、1マスごとに文字や記号が書ける記憶領域。
• ヘッド：テープの文字を読み取り、新しい文字に書き換え、左右に移動する装置。
• 内部状態：機械が今どのような「モード（状態）」にあるかを記憶するメモリ。
• 規則（プログラム）：「この状態の時にこの文字を読んだら、こう書き換えて、左右どちらかに動き、次の状態に変化する」という指示書。

「プログラムそのもの」を配列のデータとして中に放り込んでしまえば、1台のマシンであらゆる計算（引き算、掛け算、文字検索、ひいては現代のWebアプリのロジックまで）を完全に実行できます。 このマシンで解けない問題（例：無限ループを外から100%判定するプログラムなど）は、未来永劫どんなコンピュータを作っても絶対に解けない問題です。

きっかけ

チューリングマシンは人間の思考を極限までシンプルにすることで生まれました。人が紙とペンで計算するとき、文字を「見る」「書き換える」「目を動かす」「手順を覚える」という動作を繰り返します。その動作を極限まで単純化したのが、先ほどの「テープ、ヘッド、内部状態、規則」の仕組みです。

具体例

「チューリングマシンの仕組みを使えば、ルールに従った機械的なパズル（配列操作）だけで『$1 + 2 = 3$1+2=3』という算術の答えを導き出せます」

---

前提

今回は、数字の「1」をマスの数で表す世界（一進法）を考えます。

• 「1」は 1
• 「2」は 11
• 「3」は 111

目的は、テープ上の 1 + 11という入力を、マシンの力だけで 111という結果に書き換えることです。

---

マシンの具体的な構成要素

• テープ: [ B ][ 1 ][ + ][ 1 ][ 1 ][ B ] （B は Blank：空っぽの意味）
• ヘッドの初期位置: 先頭の 1 のマスを指している
• マシンの現在の状態: 状態0（スタート）

ご提示いただいたテキストを、ドキュメントにそのまま組み込めるよう、視認性の高いテーブル（表）と見出しを活用した適切なマークダウンに整形しました。

---

マシンに覚えさせる「行動ルール（遷移規則）」

今回は下記の状態を使います。

マシンには、以下の4つのルールだけをあらかじめ記憶させておきます。

---

「$1 + 2 = 3$1+2=3」を計算するチューリングマシンの実行トレース表を、擬似コードに当てはめて解説します。

このマシンのロジックを表現したコードの全体像を以下に示します。

// マシンの状態（モード）を型定義
type MachineState = "前半通り過ぎ中" | "後半通り過ぎ中" | "右端消去中" | "終了";

function runTuringMachine(): string[] {
  // ① メモリ（配列）の初期化
  const array: string[] = ["B", "1", "+", "1", "1", "B"];
  
  // ② ポインタ（ヘッドの位置）の初期化。最初の「1」のインデックスを指定
  let i: number = 1; 
  
  // ③ 初期状態は「状態0」に相当するモードをセット
  let currentState: MachineState = "前半通り過ぎ中";

  // ④ メインループ（終了状態になるまで無限に回る）
  while (currentState !== "終了") {
    const currentText = array[i]; // 現在ポインタが指している文字

    switch (currentState) {
      case "前半通り過ぎ中": // 【状態0】のルール
        if (currentText === "1") {
          i++; // そのまま書き換えずに右へ
        } else if (currentText === "+") {
          array[i] = "1"; // 「1」に書き換えて合体させる
          i++;            // 右へ進む
          currentState = "後半通り過ぎ中"; // 【状態1】へ遷移
        }
        break;

      case "後半通り過ぎ中": // 【状態1】のルール
        if (currentText === "1") {
          i++; // そのまま書き換えずに右へ
        } else if (currentText === "B") {
          i--; // 空白に達したので、1マス左（右端の1の場所）に戻る
          currentState = "右端消去中"; // 【状態2】へ遷移
        }
        break;

      case "右端消去中": // 【状態2】のルール
        if (currentText === "1") {
          array[i] = "B"; // 増えすぎた「1」を空白「B」に戻して帳尻を合わせる
          currentState = "終了"; // 【終了】へ遷移
        }
        break;
    }
  }

  return array;
}

トレース表

上記のコードの分岐を通りながら、トレース表のステップがどう進むかを解説します。

初期状態

• コード上の位置: ループに入る前の宣言部分。
• 状態: i = 1（最初の 1 の位置）、currentState = "前半通り過ぎ中"。

Step 1 （状態0 → 状態0）

• コードの動き: switch で case "前半通り過ぎ中" に入ります。currentText は "1" なので、if (currentText === "1") が実行されます。
• 結果: i++ により、ポインタ i が 1 から 2 になり、次の + のマスを指します。状態は変わりません。

Step 2 （状態0 → 状態1）

• コードの動き: i = 2 で、currentText は "+" です。else if (currentText === "+") のブロックに侵入します。
• 結果: array[2] = "1" により、真ん中の + が "1" に書き換わります。そして i++ で右へ進み、currentState が "後半通り過ぎ中"（状態1）に切り替わります。

Step 3 & Step 4 （状態1 → 状態1）

• コードの動き: switch で case "後半通り過ぎ中" に入ります。後半の "1" を連続で読み込むため、if (currentText === "1") が2回続けてヒットします。
• 結果: i++ が連続で実行され、ポインタ i は後半の数字をすべて通り過ぎて、右端の "B"（空）のマス（i = 5）まで進みます。

Step 5 （状態1 → 2）

• コードの動き: i = 5 で、currentText は "B" です。else if (currentText === "B") のブロックに入ります。
• 結果: 右端を検知したため、i-- によってポインタを1つ左（i = 4）に戻し、currentState を "右端消去中"（状態2）に変更します。

Step 6 （状態2 → 終了）

• コードの動き: switch で case "右端消去中" に入ります。戻った位置の currentText は "1" です。
• 結果: array[4] = "B" によって、余分だった最後の "1" が "B"（空）へと消去されます。最後に currentState = "終了" がセットされ、while ループの条件を満たさなくなるため、マシンが完全に停止します。

最終的な結果の配列

プログラムが停止したときの最終的な配列の中身は、以下のようになります。

// 初期状態（入力：1 + 2）
["B", "1", "+", "1", "1", "B"]

// 最終状態（出力：3）
["B", "1", "1", "1", "B", "B"]

左右の余白である "B"（Blank）を除くと、配列の中には "1" が3つだけが綺麗に並んだ状態になります。一進法において "111"は数字の「3」を意味しますので、データ構造として計算結果が残されたことになります。

[ B ][ 1 ][ + ][ 1 ][ 1 ][ B ]を[ B ][ 1 ][ + ][ 1 ][ 1 ][ 1 ][ B ]にすれば1 + 3を計算できます。正の整数（1以上の自然数）の足し算であれば、どれほど巨大な数字であっても、今回の4つのルール（遷移規則）だけですべて計算できます。

---

まとめ

チューリングマシンは『計算』を定義しました。そして、ステップを踏んで計算できる（アルゴリズムが存在する）問題は、すべてチューリングマシンが実行できる問題と完全に一致すると主張しました。現代では事実上の定説となっています。これが現代のすべてのコンピュータ設計の精神的支柱となっています。