決定不可能性

決定不可能性とは、ある形式体系の中で、与えられた命題を体系内の公理と推論規則だけからは証明することも反証することもできない状態を指す。1931年にクルト・ゲーデルが証明した不完全性定理は、算術を含む程度に強力で無矛盾な形式体系には、必ずこのような決定不可能な命題が存在することを示した。この事実は数学の基礎づけをめぐる論争に大きな転換点をもたらすと同時に、新たな謎を生んだ——「証明できない」とはいったい何を意味するのか。

ヒルベルトの夢が破れた日

1920年代、数学者ダフィット・ヒルベルトはヒルベルトのプログラムを掲げ、数学全体を有限の立場から検証できる完全かつ無矛盾な形式体系へとまとめ上げようとした。すべての数学的真理はいつか証明されるはずだという楽観がそこにはあった。だが1931年、若きゲーデルは、体系内部に「この命題は証明できない」と読める自己言及的な命題を構成する手法によって、この夢が原理的に不可能であることを示した。証明可能性そのものに、体系をどれだけ精緻化しても埋まらない限界があることが明らかになったのである。

「証明できない」は「偽」ではない

決定不可能性を理解するうえで最も重要なのは、証明不可能な命題が偽であるとは限らないという区別だ。ある命題が体系から独立している場合、それを真としても偽としても、体系全体は矛盾なく成り立ちうる。代表例が連続体仮説である。ゲオルク・カントールが提起したこの仮説について、ゲーデルは1940年に「否定できない」ことを、ポール・コーエンは1963年に強制法という手法で「肯定もできない」ことを示した。二つの証明が合わさり、連続体仮説は標準的な集合論の公理系(ZFC)から独立していることが確定した。どれほど巧妙な証明を試みても、ZFCの枠内では原理的に決着しない問題なのである。

計算の言葉で語られた同じ限界

ゲーデルの結果から5年後の1936年、アラン・チューリングは別の角度からこの限界に到達した。任意のチューリングマシンが入力に対していつか停止するかどうかを判定する汎用アルゴリズムは存在しない、という停止問題である。これは証明の可否ではなくアルゴリズムの存否を問う、計算論的な意味での決定不可能性であり、論理学的な決定不可能性とは厳密には異なる概念だ。それでも両者の証明は同じ戦略を共有している。停止判定アルゴリズムの存在を仮定すると矛盾が導かれるというチューリングの議論は、ゲーデルの自己言及の構成と同じく、対象を自分自身に適用する対角線論法の系譜に連なる。そしてチューリングの原論文が実際に示したのは、ヒルベルトが問うた「ある命題が証明可能かどうかを判定する手続き」自体の不可能性でもあり、論理と計算という二つの決定不可能性が同じ根から生えていることを明らかにした。

なぜ決定不可能性が今も問われるのか

決定不可能性は数学の欠陥ではなく、形式的証明という営みの本性そのものだ。それは真理が証明よりも広い概念であることを教える。『ゲーデルの哲学』が描くように、ゲーデル自身は決定不可能な命題の存在を、数学的実在が形式体系に還元しきれないことの証拠と捉えていた。証明できないことと、存在しない・偽であることは違う——この区別は、ソフトウェアの完全な自動検証がなぜ原理的に不可能なのかを含め、計算機が「解けない問題」に直面する現代においても、知性と限界の関係を考えるための出発点であり続けている。