計算可能性と決定不能問題（停止性問題）

なぜこの話が実務に効くのか

「コードを実行せずに、無限ループするか、null参照を起こすか、デッドコードかを完璧に判定するツールが欲しい」——この願いは、原理的に叶いません。リンタや型検査器がときに「保守的すぎる警告」を出し、ときに「見逃し」をするのは、ツールの実装が未熟だからではなく、完全かつ正確な静的解析が数学的に不可能だからです。その根拠が停止性問題の決定不能性です。

チューリングマシンと計算可能性

チューリングマシンは、無限長のテープ・ヘッド・有限個の状態と遷移規則だけからなる、極限まで単純化した計算モデルです。重要なのは性能ではなく境界を定めることにあります。

チャーチ＝チューリングのテーゼは「直感的に『計算できる』ものは、すべてチューリングマシンで計算できる」と主張します。λ計算・再帰関数・現実のプログラミング言語（チューリング完全なもの）は、どれも計算能力が等価であることが証明されています。つまり Python で書けない計算は C でも書けず、その逆も成り立ちません。

停止性問題：その主張と証明の骨格

停止性問題とは「任意のプログラム P と入力 x を与えたとき、P(x) が停止するか無限に走り続けるかを、常に正しく判定する」という問題です。これを解くプログラム halts(P, x) は存在しません。

証明は対角線論法による背理法です。仮に正しい halts が存在したとして、次の意地悪なプログラム trap を作ります。

def trap(P):
    if halts(P, P):   # P に「P自身」を入力したら停止する？
        while True:    # 「停止する」なら、あえて止まらない
            pass
    else:
        return         # 「止まらない」なら、すぐ止まる

ここで trap(trap) を考えます。halts(trap, trap) が「停止する」と判定すれば、定義上 trap(trap) は無限ループに入り停止しません。逆に「停止しない」と判定すれば、trap(trap) はすぐ return して停止します。どちらの判定も実際の挙動と矛盾します。よって最初の仮定（正しい halts の存在）が誤りです。

ライスの定理：話は停止だけではない

停止性は氷山の一角です。ライスの定理は「プログラムが計算する関数の、自明でない意味的性質はすべて決定不能」と述べます。「この関数は常に正の値を返すか」「この入力で例外を投げるか」「2つの関数は等価か」——これらは原理的に完全判定できません。

最終行が鍵です。正規表現エンジンが静的に振る舞いを解析できるのは、対象がチューリング完全より弱い計算モデル（有限オートマトン）だからです。表現力を絞れば決定可能性が戻る——これが実務での回避策の本質です。

実務的含意：健全性と完全性のトレードオフ

完全な解析が無理なら、ツールはわざと間違える方向を選ぶしかありません。静的解析の評価軸は次の2つです。

決定不能性ゆえに、汎用の解析で両方を同時に100%達成することはできません。だから各ツールは立場を決めています。

• 型検査器は健全性を重視し、「実行時には起きないが証明できない」コードも弾く（コンパイルエラー）。だから安全だが、ときに余計に厳しい。詳細は型システムへ。
• 多くのリンタやバグ検出器は完全性寄りで、確度の高い問題だけ報告して偽陽性を抑える。代わりに見逃しが残る。
• 「到達不能コード」警告が出ないことがあるのも、判定が一般に決定不能で、安全に判定できる範囲に限っているからです。

チューリング完全という諸刃の剣

設定ファイルやテンプレート言語が「チューリング完全になってしまった」という話を聞きます。表現力が上がる一方で、その設定が停止するか・何を出力するかを静的に保証できなくなることを意味します。逆に、意図的に表現力を制限した言語（全関数が停止する全域言語、SQL の中核、正規言語など）は、停止性や一部の性質を静的に保証できます。

まとめ

• チューリングマシンは計算可能性の境界を定める数学モデル。チャーチ＝チューリングのテーゼにより、現実の汎用言語の計算能力はすべて等価です。
• 停止性問題は決定不能で、対角線論法により「常に正しい停止判定器」は存在しないと証明されます。ライスの定理はこれを「自明でない意味的性質すべて」へ拡張します。
• だから完全かつ正確な静的解析は原理的に不可能。実用ツールは健全性か完全性を捨て、近似と保守的判定で折り合いをつけています。ツールの偽陽性・偽陰性は欠陥ではなく、理論的限界の現れです。

計算量の上限（Big-O）が「どれだけ速く解けるか」の話なら、計算可能性は「そもそも解けるのか」というさらに手前の問いです。両者を区別できると、「遅い」と「不可能」を取り違えずに設計判断ができます。