正しいソフトウェアを書くことが難しい理由:計算可能性と計算量の理論から
Ron Pressler は、正しいソフトウェアの作成が本質的に困難であると論じている。停止性定理やライスの定理など、計算可能性と計算量の理論における結果を概観している。
本記事は、Ron Pressler のブログに2016年7月23日に掲載された「Why Writing Correct Software Is Hard」である。停止性定理、ライスの定理、ビジー・ビーバー定理、有界停止性問題などの結果を取り上げ、数学だけではソフトウェアの正しさを保証できないと論じている。
数学の限界と停止性定理
Hilbert は、一貫性、完全性、決定可能性を備えた数学全体を形式化するプログラムを提示していた。Hilbert は1930年にケーニヒスベルクで退官記念講演「Naturerkennen und Logik」を行ったが、その前日に Gödel が第一不完全性定理を暫定的に発表したとされる。記事によると、この結果によってHilbert のプログラムの最初の二つの柱が崩れたという。
Hilbert はこの講演で次のように述べたとされる。
「For the mathematician there is no Ignorabimus, and, in my opinion, not at all for natural science either.」
— David Hilbert
記事は、Hilbert のプログラムが Gödel、Church、Turing によって葬られてから80年が経ったと述べている。記事で挙げられている主な結果は以下のとおりである。
- Church と Turing は1936年に、それぞれの論文で停止性定理を証明した。
- ライスの定理は、記事において停止性定理の帰結として提示されている。
- ビジー・ビーバー定理と有界停止性問題を含む関連結果が取り上げられている。
計算量理論と時間の問題
計算量理論は、1965年に Juris Hartmanis と Richard Stearns の論文によって誕生したとされる。Hartmanis は1993年のチューリング賞講演で、計算量を自然法則とみなしていると述べたという。
記事によると、Max Newman は1952年に BBC ラジオで Turing に時間の問題を提起した。その際の発言は以下のとおりである。
「It is all very well to say that a machine could… be made to do this or that, but… what about the time it would take to do it?」
— Max Newman
これに対し Turing は、この時間の要因こそが実際の技術的困難のすべてに関わる問題だと応じたとされる。記事では、Turing の原論文から30年を経て、アルゴリズムの困難さが適切に定義されたと述べられている。
記事は、Church-Turing テーゼに関する議論にも触れている。テーゼは、実現可能な物理過程による計算がいかなるものであっても、万能モデルで計算可能であると推測するものである。記事によると、量子コンピュータの可能性を考慮すると、より強いバージョンのテーゼは誤りである可能性がある。また、人間の心がチューリング計算可能でないものを計算できる可能性は極めて低いとされ、人間が量子アルゴリズムを用いている可能性も低いとされる。
不完全性原理に基づくプログラム
記事によると、Adam Yedidiya と Scott Aaronson は今年5月に、不完全性原理によって動作するプログラムを公開したとされる。このプログラムは、不完全性定理の原理またはそれと同等のものに基づいて動作するとされる。

Stefan O'Rear は、停止することを証明できないチューリングマシンを作成したとされる。その制御状態数は1919である。このマシンは ZFC から独立しているとされ、記事ではその規模が Python プログラムと比較されている。
筆者の見立て
- プログラムの正しさに必要な完全な理解と、プログラムそのものは根本的に相反すると解釈している。
- 正しさのコストは計算の自然法則に起因し、回避することは不可能だと論じている。
- 計算機科学は数学ではないと論じている。
- ツールさえ適切であればソフトウェアの正しさは容易に達成できるという主張に反論することが、執筆の動機だったと解釈している。
- 見出された計算上の限界は、多項式の範囲内で人間にも当てはまる可能性を示唆している。
- 検証は計算機科学で最も困難な問題であると論じている。
- Gödel は有界停止性問題に似た考えを以前に用いていた可能性があると解釈している。
この記事は元記事の事実のみに基づいて自動生成されました。
出典
- 媒体名:Ron Pressler
- 原題:Why Writing Correct Software Is Hard
- 公開日:2016年7月23日
- URL:https://pron.github.io/posts/correctness-and-complexity
- Curry On、Quasar、Galaxy の報道による