出来事の日付:2026年11月12日
新たに公開された技術論考が、計算可能性理論と計算複雑性理論の成果をまとめ、検証ツールが進歩しても、ソフトウェアの完全な正しさを確保することがなぜ難しいままなのかを説明している。著者は、カンファレンスでの講演と、ソフトウェアプロジェクトGalaxyの改訂版について形式仕様を記述し検証した経験を基に、この文章をまとめた。
中心となるのは、エンジニアが特定の性質を確認する手助けをすることと、あらゆるプログラムに関する意味のあるあらゆる問いに答えられる万能の手続きを作ることとの違いだ。テスト、静的解析、モデル検査、形式的証明はいずれも、定められた範囲内で有用な裏付けを与えられる。論考が取り上げる理論的な成果は、十分に高度なツールがあればその境界を単純に取り払える、とはいかない理由を示している。
出発点となるのは、1936年のアロンゾ・チャーチとアラン・チューリングの研究を通じて確立された、停止問題に関する定理だ。これは、考え得るすべてのプログラムと入力について、実行が最終的に停止するかどうかを判断できるアルゴリズムは存在しないことを示す。ハードウェアの性能不足や工学技術の未熟さについて述べているのではない。汎用的な計算そのものに内在する限界である。
この限界は、検証に直接関わる問いにも及ぶ。もし万能のツールが、どんなプログラムについても、指定された状態にいつか到達するかどうかを判定できるなら、そのツールを使って停止状態に到達するかどうかも判断できてしまい、停止問題の結論と矛盾する。論考はライスの定理も取り上げる。この定理によれば、任意のプログラムが計算する部分関数の、非自明な意味的性質を一般に判定するアルゴリズムは存在しない。したがって、仮に検査ツールがあっても、すべての出力が入力の2乗になっているか、といった性質を、あらゆるプログラムについて判定することはできない。
著者は、こうした不可能性の結果を、解析の実際の負担と結び付ける。エンジニアは、制約のない任意のプログラムを解析しなければならないことはめったになく、選び取った仕様、抽象化、言語、動作上の前提の下で作業している。問題を限定すれば有用な検証が可能になるが、その場合、結論が及ぶ範囲もその選択に依存する。証明は、実装が形式仕様を満たすことを示せても、その仕様が現実世界での期待をすべて捉えていることまで示すとは限らない。
したがって、この論考は、検証が無意味だと主張しているのではない。正しさには避けられない代償があり、ツールはその負担の一部を移し、管理し、軽減するものであって、消し去るものではないと述べている。チームは、どの性質が重要かを決め、それを正確に表現し、扱えるモデルを選び、裏付けを得るために計算資源と人の労力を費やさなければならない。
この捉え方は、コード生成のコストが下がる中で、とりわけ重要になる。ソースコードの量が増えても、その振る舞いが自動的に理解しやすくなるわけではない。レビュー担当者は依然として、要件を特定し、インターフェースや障害の起こり方を調べ、得られた証拠が実際に配備されるシステムをカバーしているかを判断する必要がある。形式手法はこの過程を強化できるが、その結論は、エンジニアがモデル化する際に選んだ前提と性質に結び付いたままだ。
論考は理論的な成果を一か所に集めることで、一つの手法によってソフトウェアの正しさの確保を日常的で容易な作業にできる、という主張を見直す材料を提供している。より優れたツールは、チームが解析できるシステムや性質の範囲を広げられる。しかし、制約を設けないソフトウェアを、完全かつ自動的に理解する手段にはならない。



