チューリングマシン・シミュレーター

チューリングマシンは、無限のテープ、テープヘッド、および状態遷移表からなる計算の形式的数学モデルです。計算可能な限界を定義し、あらゆるアルゴリズムはチューリングマシンでシミュレート可能であるとします（チャーチ＝チューリングのテーゼ）。また、プログラムが停止するかどうかを判定する一般アルゴリズムは存在しないという「停止性問題の決定不能性」を証明します。

チューリングマシンの構成はごく単純です。テープ、1マスを読むヘッド、そして短い規則表だけ。各ステップでは現在の状態とヘッド下の記号だけを見て、記号を書き込み、左か右へ1マス動き、状態を切り替えます。二進インクリメントのプリセットを実行すると、右端まで滑って進み、+1 の繰り上がりを左へ戻していく様子が見えます。まさに筆算の足し算と同じです。

最も素朴な問い——小さな機械は停止するまでどれだけ走れるか——を立てるだけで、計算は爆発します。状態5個・記号2個の機械は停止までにちょうど 47,176,870 ステップ進み、この値は2024年にようやく証明されました。状態6個では既知の記録はすでに 2↑↑↑5 を超え、宇宙のあらゆる原子をかすませる冪(べき)の塔となります。だからこそ、このようなシミュレータは各実行に上限を設けます。わずかな状態が永遠より長く生き延びうるのです。