
チューリングマシンとは、1936年にイギリスの数学者アラン・チューリングが考案した、「計算とは何か」を定義するための数学的モデルです。
チューリングが登場する以前、数学者たちは「計算とは何か」「すべての数学的な問題は計算で解けるのか」という直感的な疑問を抱えていましたが、「計算」の厳密な定義がありませんでした。
そこで、チューリングマシンで実行できる処理のことだけを『計算』と定義しました。
チューリングマシンは、単純な4つの要素だけで構成されています。
「プログラムそのもの」を配列のデータとして中に放り込んでしまえば、1台のマシンであらゆる計算(引き算、掛け算、文字検索、ひいては現代のWebアプリのロジックまで)を完全に実行できます。 このマシンで解けない問題(例:無限ループを外から100%判定するプログラムなど)は、未来永劫どんなコンピュータを作っても絶対に解けない問題です。
チューリングマシンは人間の思考を極限までシンプルにすることで生まれました。人が紙とペンで計算するとき、文字を「見る」「書き換える」「目を動かす」「手順を覚える」という動作を繰り返します。その動作を極限まで単純化したのが、先ほどの「テープ、ヘッド、内部状態、規則」の仕組みです。
「チューリングマシンの仕組みを使えば、ルールに従った機械的なパズル(配列操作)だけで『1+2=3』という算術の答えを導き出せます」
今回は、数字の「1」をマスの数で表す世界(一進法)を考えます。
111111目的は、テープ上の 1 + 11という入力を、マシンの力だけで 111という結果に書き換えることです。
[ B ][ 1 ][ + ][ 1 ][ 1 ][ B ] (B は Blank:空っぽの意味)1 のマスを指している状態0(スタート)ご提示いただいたテキストを、ドキュメントにそのまま組み込めるよう、視認性の高いテーブル(表)と見出しを活用した適切なマークダウンに整形しました。
今回は下記の状態を使います。
| 状態番号 | 状態名(コードでのラベル) |
|---|---|
| 0 | "前半通り過ぎ中" |
| 1 | "後半通り過ぎ中" |
| 2 | "右端消去中" |
| 3 | "終了" |
マシンには、以下の4つのルールだけをあらかじめ記憶させておきます。
| 現在の状態 | 目の前のマス目の文字 | 書き換える文字 | 次の移動方向 | 次の状態 | ルールの目的 |
|---|---|---|---|---|---|
| 状態0 | 1 | 1(そのまま) | 右 | 状態0 | 最初の数を通り過ぎる |
| 状態0 | + | 1(書き換え) | 右 | 状態1 | + を 1 に変えて合体 |
| 状態1 | 1 | 1(そのまま) | 右 | 状態1 | 後半の数を通り過ぎる |
| 状態1 | B(空白) | B(そのまま) | 左 | 状態2 | 右端に達したら1マス戻る |
| 状態2 | 1 | B(空白に書き換え) | 停止 | 状態3 | 増えすぎた 1 を1つ消して完了 |
「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 = "前半通り過ぎ中"。switch で case "前半通り過ぎ中" に入ります。currentText は "1" なので、if (currentText === "1") が実行されます。i++ により、ポインタ i が 1 から 2 になり、次の + のマスを指します。状態は変わりません。i = 2 で、currentText は "+" です。else if (currentText === "+") のブロックに侵入します。array[2] = "1" により、真ん中の + が "1" に書き換わります。そして i++ で右へ進み、currentState が "後半通り過ぎ中"(状態1)に切り替わります。switch で case "後半通り過ぎ中" に入ります。後半の "1" を連続で読み込むため、if (currentText === "1") が2回続けてヒットします。i++ が連続で実行され、ポインタ i は後半の数字をすべて通り過ぎて、右端の "B"(空)のマス(i = 5)まで進みます。i = 5 で、currentText は "B" です。else if (currentText === "B") のブロックに入ります。i-- によってポインタを1つ左(i = 4)に戻し、currentState を "右端消去中"(状態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つのルール(遷移規則)だけですべて計算できます。
チューリングマシンは『計算』を定義しました。そして、ステップを踏んで計算できる(アルゴリズムが存在する)問題は、すべてチューリングマシンが実行できる問題と完全に一致すると主張しました。現代では事実上の定説となっています。これが現代のすべてのコンピュータ設計の精神的支柱となっています。