正規表現という「最小限の武器」でDOOMを動かす——計算理論が示すチューリング完全性の実践的限界

「正規表現でゲームを動かす」という狂気の実装

2026年7月、プログラマーのアーテム・リトキン氏が公開したプロジェクト「DOOM on regex」は、一見するとただのネタプロジェクトに見えるかもしれません。しかし、その実態は計算機科学の深い理論を実装レベルで検証する、極めて示唆的な事例なのです。

本プロジェクトは、文字列の検索や置換に使われる正規表現という「最小限のツール」だけを使い、名作FPS「DOOM」を完全に動作させるというもの。96.6MBの単一文字列にレジスタやRAM、フレームバッファまで詰め込み、544個の置換ルールのみで仮想コンピューターを構築しています。数十年前のゲーム開発の常識では考えられない、デジタル時代の逆転劇です。

「チューリング完全性」の理論と実装のギャップ

計算理論の教科書では、正規表現はチューリング完全（理論的にはあらゆる計算が可能）であると教えられます。しかし、DOOM on regexが暴露するのは、この「理論的完全性」と「実務的実行可能性」の絶望的なギャップです。

理論の約束： チューリング完全ならば、あらゆるプログラムが実装可能
現実の課題： 1フレームの描画に約1399万回の置換が必要で、5台マシンの並列処理でも約180秒かかる
何が起こっているのか： 理論的には可能だが、計算量が爆発的に増加する「NP困難」領域に転落

つまり、このプロジェクトは「正規表現でDOOMを動かせるか」という問いではなく、「理論的完全性は実装的効率性を保証しない」という、より根本的な洞察を示しているのです。これはAIやアルゴリズム開発に携わるエンジニアにとって、すぐに他人事ではない教訓です。

1フレーム180秒という「非効率性」が教えてくれる本質

現代のゲームエンジンは、1秒間に60フレーム（60fps）の描画を目指しています。つまり、1フレームあたり約16ミリ秒で画面を更新する必要があります。対するDOOM on regexは、1フレーム描画に180秒（180,000ミリ秒）を費やします。

この11,250倍の時間ギャップは、単なる「遅い」の一言では済みません。むしろ、これは以下の重要な原則を示唆しています：

抽象化のコスト： 正規表現という汎用ツールを使うことで、CPU命令という「具体的な最適化」を放棄している
中間表現の必要性： 理論と実装の間には、機械語やバイトコードといった「変換レイヤー」が不可欠
並列処理の限界： 5台マシンでも180秒かかる現実が、アルゴリズムの根本的な計算量問題を浮き彫りにしている

これは、最近のAI開発でも同じ問題が表面化しています。大規模言語モデルも「理論的には完全」ですが、推論速度の改善には、量子化やプルーニング、エッジAIといった実装的工夫が必須です。

なぜプログラマーはこんなプロジェクトに挑むのか

DOOM on regexの価値は、実用性ではなく、計算理論と現実のプログラミングの関係を可視化する点にあります。このプロジェクトは、以下のような実践的な示唆をもたらします：

言語とランタイムの選択が決定的である： Pythonで統計処理をするのと、アセンブラで最適化するのでは、計算量が異なる次元で変わる
「動くコード」と「効率的なコード」は別物： ChatGPTやClaude、Geminiなども、理論的には同じ「ニューラルネットワーク」ですが、実装と最適化により大きく異なる
開発戦略の多様性： 正規表現という「最小限のツール」でも動くDOOMは、逆説的に、適切な道具選びがいかに重要かを証明している

また、このプロジェクトはオープンソースコミュニティの検証文化をも象徴しています。「これは理論的に可能なはず」という仮説を、実装レベルで検証する姿勢は、ブロックチェーンやP2Pネットワークの開発でも同じです。