なぜ正しいソフトウェアを書くのは難しいのか
Why Writing Correct Software Is Hard (pron.github.io)
要約
この記事は、計算可能性理論、計算複雑性理論、および数学的論理学からの結果を引用し、正しいソフトウェアを書くことの根本的な難しさについて論じています。計算の「自然法」として避けられない複雑さがあり、数学だけでは解決できないことを示しています。検証の限界と、経験主義的なアプローチの必要性を強調しています。
全文翻訳
なぜ正しいソフトウェアを書くのは難しいのか
…そしてなぜ数学(だけ)では助けにならないのか
私はCurry Onで再び講演できたことを非常に嬉しく思っています。昨年は、Quasarでの仕事に続き、継続とモナドについて話しました。今年は、計算複雑性理論の結果をソフトウェア検証に応用したテーマで講演しました。これは、Galaxyの刷新版を形式的に仕様化し検証する作業中に興味を持った分野です。
以下は、上記の講演を拡張したもので、脚注付きで、さらに詳しい証明や結果を含んでいます。読了時間:約45分。
この記事では、プログラムと正しさの関係、特に正しいプログラムを書くことがなぜ難しいのかを理解しようと試みます。計算可能性理論と計算複雑性理論の結果をレビューし、正しさに必要とされる完全な理解とプログラムが根本的に相容れないことを示します。このテキストの主な貢献は、正しいソフトウェアを生成することの「本質的な」難しさに関するいくつかの結果(および参照)を1箇所にまとめることです。私の動機は、オンラインで見つけた様々な声明(例えばこれなど、ただしこれは唯一のものでは全くありません)で、適切なツールを使えばソフトウェアの正しさは達成しやすいと主張されていることでした。確かに、一部のツールはプログラムの正しさを保証するのに役立ちますが(そして役立っています)、正しさには大きなコストがかかります。正しさのコストは、エントロピーを減らすためのエネルギーコストのように、計算の「自然法」の結果であり、決して回避できません。*
第I章:基礎
理論計算機科学の物語は約100年前に始まりました。数学的論理学の成功に伴い、数学者デイヴィッド・ヒルベルトは、すべての数学を形式化するプログラムを提唱しました。彼は、その形式体系が一貫性があり、完全であり、かつすべての形式的命題の真偽を判定するアルゴリズム(決定手続き)を見つけることを望んでいました。
- 一貫性: 形式体系内に矛盾が得られないという証明。
- 完全性: 真であるすべての数学的命題が形式体系内で証明できること。
- 決定可能性: 任意の命題が定理であるかどうかを判定するアルゴリズム(Entscheidungsproblem)。
ヒルベルトは、形式的に推論できるものはすべて完全に理解でき、そのすべての性質を証明できると信じていました。19世紀の知識の限界に対する見方は、「ignoramus et ignorabimus」(「我々は知らず、そして知ることはないだろう」)という格言で表現されていました。1930年の引退に際し、ヒルベルトはケーニヒスベルクでドイツ科学者・医師協会の前で「Naturerkennen und Logik」(自然認識と論理)と題した講演を行い、この見方に異議を唱えました。彼はこう述べました。
数学者のためには、Ignorabimus は存在しない。そして、私の意見では、自然科学のためにも全く存在しない。… 解決不可能な問題を見つけられなかった真の理由は、私の意見では、解決不可能な問題が存在しないということである。愚かなIgnorabimusとは対照的に、我々の信条はこう謳う:我々は知らねばならない。我々は知るだろう!1
Wir müssen wissen. Wir werden wissen というこれらの言葉は、彼の墓石に刻まれています。
[画像: Hilbert's tomb]
ヒルベルトが当時知る由もなかったことですが、彼のプログラムは、クルト・ゲーデルが彼の最初の不完全性定理を暫定的に発表した2前日に打ち砕かれていました。
ゲーデルの不完全性定理は、ヒルベルトのプログラムの最初の2つの柱を打ち砕き(第3の柱も打ち砕いたと言う人もいるが、彼はそれに気づかなかった3)、1936年にはチャーチとチューリングが、今日では停止性定理として知られるものの証明によって、決定問題という第3の柱を打ち砕きました。
計算機科学の最初の定理である停止性定理は、1936年にアロンゾ・チャーチ4とアラン・チューリング5の論文でそれぞれ証明されました。この定理は計算の本質に非常に根本的であるため、両方の計算モデルの定式化と同時に現れたのは偶然ではありません。それは、任意の与えられたプログラムがいつ停止するかを決定するアルゴリズムは存在し得ないことを述べています。証明(ここでは短縮形で示します)は、ゲーデルが不完全性証明で使用したのと同じ対角線論法、または自己参照のアイデアに基づいています。
そのようなプログラムHが存在すると仮定します。
H(M, x) := IF M が x で停止 THEN TRUE
ELSE FALSE
次に、次のようなGを簡単に構築できます。
G(y) := IF H(y, y) = FALSE THEN TRUE
ELSE 無限ループ
次にGをG自身に渡す($G(G)$)と、Gが行うこととHがGが行うと述べていることとの間に矛盾が生じます。
停止性定理がゲーデルの最初の不完全性定理のバージョンを直接的に導くことは興味深いことです。証明は単純に6述べています:ある論理理論(基本的に公理の集合)において、すべての真の命題に対して論理的な証明が存在すると仮定します。そうすれば、プログラムを与えられたとき、それらの公理から始めて、論理的推論を使用して定理を1つずつ列挙できます。すべての命題の数、ましてやすべての定理の数は可算であり、各命題は証明を持つか、その否定が証明を持つかのどちらかなので、最終的にはどちらかの証明を見つけるでしょう。したがって、プログラムを与えられたとき、プログラムが停止することを示す定理、または停止しないことを示す定理を見つけるまで定理を列挙し始めることができ、これは停止性定理に違反します。
しかし、停止性定理には、ソフトウェア検証の問題、すなわち我々の主な焦点に直接関連する他の即時の系があります。最初のものは到達可能性に関する単純な結果です。
プログラムM、初期状態の集合I、および状態構成Sが与えられたとき、MがIのいずれかの状態から開始してSに到達するかどうかを決定するプログラムRは存在しない。
証明は停止性からの単純な還元です。もしそのようなアルゴリズムが存在するなら、入力xから開始して停止状態に到達するかどうかを尋ねることができ、それによって停止性問題を解決できます7。
より興味深い系はライス氏の定理です。プログラムは、部分関数として知られるものを計算できます。入力が与えられたときに停止する場合、テープに書き込まれた出力を初期入力にマッピングされたものと見なします。入力に対して決して停止しない場合、その入力をマッピングされないものと見なします。ライス氏の定理は次のように述べています。
部分関数の非自明な性質について、プログラム(TM)Mがその性質を持つ部分関数を計算するかどうかを決定するアルゴリズムは存在しない。
例えば、プログラムの出力が常にその入力の二乗であるかどうかを決定するアルゴリズムは存在しません。この定理もまた、停止性からの還元によって証明されます。
我々の目的のために、停止性定理の最も興味深い系は、プログラムの分析の複雑さという概念を捉え、それに定量的な尺度を与える「ビジービーバー定理」8と呼ぶものだと考えます。ここでカバーするすべての結果と同様に、この結果はプログラムの動的な側面と静的な側面(すなわち、実行中の動作またはグローバルな性質)の両方に適用されますが、この結果は各側面を個別にターゲットとしているため、それらが同じコインの裏表であることをより直接的に直感的に理解するのに役立ちます。
動的なバージョンでは、自然数に対して次の関数を定義します。
$f(n)$ = $n$個の制御状態を持つ停止するTMが停止するまでに要する最大ステップ数。
チューリングマシンの制御状態はそのプログラムを構成するため、$n$はプログラムのサイズです。この関数は、サイズ$n$のTMの数が有限であるため、適切に定義されています。それらのうち停止するもののサブセットも有限なので、最大ステップ数が存在します。
定理は、$f$が非計算可能であることを述べています。もし$f$が計算可能だと仮定すると、それは停止性定理の違反となります。TMを与えられたとき、制御状態の数$n$を数え、$f(n)$を計算し($f$の計算可能性の仮定により可能)、次にマシンを$f(n)$ステップ実行します。もしその時点で終了しない場合—それは確かに決して終了しないはずです($f$の定義により)、そして我々は停止性問題を決定する手続きを持つことになり、停止性定理と矛盾します。
$f$は非計算可能な関数であるだけでなく、$n$のすべての値に対して$f$よりも大きいことが知られている任意の関数も非計算可能である、なぜならもしそのような関数を知っていた場合、同じ手続きが再び停止性の決定をもたらすからです。
同じ議論がプログラムの静的な側面にも適用されます。この結果を理解するには、有限個の公理を持つ論理体系があれば、アルゴリズムは公理から始めて推論規則を1つずつ適用し、すべての定理(証明可能な命題)を1つずつ列挙できることを知る必要があります。
今回は、次の関数を定義します。
$g(n)$ = サイズ$n$の停止するTMの停止性の最小証明の最大サイズ。
サイズ$n$の終了する各TMについて、停止性の最短証明(証明は少なくとも1つ存在するはずです。終了トレースが証明となるからです)を選択します。次に、サイズ$n$のすべての終了するTM(有限個あります)の中から最大値を取ります。
$f$と同様に、$g$も非計算可能である必要があります。もし$g(n)$が計算可能であれば、サイズ$n$のTMが与えられたとき、マシンをいくつかの公理で記述し、サイズ$\leq g(n)$の証明を持つすべての定理を列挙します—これは有限の数です—そして証明が見つからなければ、マシンは決して終了しないと知ることになります。再び、停止性定理との矛盾です。
停止性定理のこの系は、次の事実を捉えています。プログラムのサイズとそれが停止することを証明することの難しさを結びつける関数は、動的な証明技術か静的な証明技術のどちらに関心があるかに関わらず、すべての計算可能な関数よりも大きい(より正確には、すべての値$n$に対して、我々の関数よりも大きいことが知られている計算可能な関数は存在しません)。
$n$のすべての値に対して$f$を計算することはできませんが、$f$を計算したり、その下限を計算したりすることはできますいくつかの値について。$n = 6$(および2記号アルファベット)の場合、それは$> 7.4 \times 10^{36534}$です。
もう1つ尋ねられる質問は次のとおりです。任意のプログラムが停止するかどうかを決定するアルゴリズムを見つけることはできないことはわかっていますが、停止するかどうかを(たとえそれ専用の決定手続きを調整したとしても)知ることができない特定のプログラムは存在しますか?
ゲーデルの第二不完全性定理は、そのようなプログラムをもたらします。この定理は、論理体系がそれ自身の完全性を証明することは不可能であると述べています。数学の基礎として広く受け入れられている論理体系はZFC—ツェルメロ=フレンケル集合論(選択公理付き)と呼ばれます。この体系内では、我々が気にするほとんどの数学的定理を証明できます(ただし、非常に注目に値する、非常に特別な例外があります)。したがって、ZFC公理から始めて、矛盾(例:1 = 2)に達するまですべての定理を列挙して停止するプログラムを構築できます。プログラムはZFCが一貫している場合にのみ停止します。我々はZFCが一貫していると仮定しており、プログラムが決して停止しないと予想しますが、第二不完全性定理によって、それを証明することはできません。
この5月、Adam YedidiyaとScott Aaronsonはプログラムを発表しました。これはその原理(またはそれに相当するもの)で動作するチューリングマシンにコンパイルされます9。この結果はすぐにStefan O’Rearによって改善されました。彼は、停止することが証明できない(つまり、「ZFCから独立している」)1919個の制御状態を持つチューリングマシンを作成しました。このマシンは非常に小さいため、4Kチャレンジに楽に収まります。これは、100〜200行のPythonプログラムに匹敵します。
これは、数学的に決定できない小さなプログラム—わずか数百行以下—が存在することを意味します。分析が大きすぎる、または実行不可能であるためではなく、数学がこのプログラムの動作を理論的にも証明するには十分強力ではないためです。
計算機科学は数学ではない
いずれにせよ、ゲーデル、チャーチ、チューリングの研究により、ヒルベルトのプログラム—少なくとも当初計画されていた通り—は、80年前に、形式的に推論できるが完全に理解することはできない、単純でコンパクトな数学的対象であるコンピュータプログラムによって、葬り去られました。
[画像: Computer Programs]
1つの根本的な疑問を投げかける必要があります。停止性定理の前提全体は、無限の計算ステップを必要とする関数は計算不可能であるという考えに基づいています。これは完全には明白ではありません。結局のところ、数学はしばしば無限の対象を扱います10。チャーチはこの点を(おそらく明白だと考えて「漠然とした直感的な概念」と呼んで)省略しましたが、彼の論文よりもはるかに哲学的なチューリングは、アルゴリズムは人または機械によって実行されるものであることを説明することに重点を置きました。
1947年、彼はロンドン数学会での講演でこう述べました。
数年前、私は、現在ではデジタル計算機の理論的な可能性と限界の調査として説明されていることについて研究していました。
これらの理論的な議論では、メモリは無限である必要がある…ACEのような機械は、この同じタイプの機械の実用的なバージョンと見なすことができます11。
これがチューリングが1936年の画期的な業績をどのように見なしていたかです。数学的な形式化は無限に訴えかけるかもしれませんが、計算の概念がある物理プロセスと結びついていることはチューリングにとって明らかでした。そうでなければ、停止性問題の中心性とそのEntscheidungsproblemへの否定的な解決策としての使用を正当化する根拠はありませんでした。アルゴリズムとは、物理世界で実行されるものです。
チャーチ=チューリングのテーゼは、今日理解されているように、宇宙のあらゆる物理プロセスによって実行可能なあらゆる計算が、チャーチとチューリングによって記述された普遍的な計算モデルのいずれかによって実行できると推測しています。ある意味では、これは宇宙のすべてがコンピュータプログラムとして形式化されシミュレートできることを意味します。
[画像: The Church-Turing Thesis]
プログラムは、完全な理解、証明、および正しさとは根本的かつ本質的に対立しています。
数学—学術分野として、道具としてではなく—は小さな円の内側に関心があり、計算機科学は主にその外側に関心がある—そして、後述するように、その内側の円内にあるプログラムでさえ、多くのものは原理的には証明可能ですが、現実的に証明可能ではありません—ため、計算機科学は数学ではない12と私は考えています。
第II章:複雑性
実用的な観点からは、代数的次数と指数的次数の違いは、有限と非有限の違いよりも重要であることがよくあります。
検証—すなわち停止性とその系—が決定可能であるか否かは、問題の難しさを完全には捉えていません。チューリングマシンは無限の振る舞いを持ちうるため、それらを検証する問題は、ある意味では、有限または無限長のリストのソートやそのようなリストの最大要素の検索の問題に似ていると考えることができます。どちらも同様に不可能ですが、有限ケースに限定した場合、それらの難易度は非常に異なることがわかっています。
時間と労力のこの問題は、チューリングにとって明らかでした。ケンブリッジでチューリングの教師であり、ブレッチリーパークで暗号解読者でもあったマックス・ニューマンは、1952年の人工知能に関する最初の公開パネルディスカッションで、BBCラジオでチューリングにこの問題を提起しました14。
マックス・ニューマン: 機械が…これをしたりあれをしたりできると言ってもいいですが…それにどれくらいの時間がかかるのでしょうか?…機械で問題を解決することは、今から永遠の間に解決策を見つけることを意味するのではなく、合理的な時間内に解決することです…
チューリング: 私の考えでは、この時間要因こそが、すべての真の技術的困難を伴う問題です。14
アルゴリズムの難しさの問題が適切に定義されるまでには、チューリングの元の論文からさらに30年かかりました。計算複雑性理論は、1965年にJuris HartmanisとRichard Stearnsによる論文で誕生しました。その論文は次のように始まります。
A. M. Turingは、彼の有名な論文で、機械的手順によるシーケンス(関数)の計算可能性を調査し、シーケンスの集合を計算可能シーケンスと非計算可能シーケンスに分割できることを示しました。しかし、一部の計算可能シーケンスは計算が非常に容易である一方、他の計算可能シーケンスは計算を困難にする固有の複雑性を持っているように思われます。本稿では、シーケンスを計算の難しさに基づいて分類するスキームを調査します。15
1993年のチューリング賞講演で、Hartmanisは、複雑性を物理法則に似た自然法則と見なしていると述べました。
私は物理学を、物理世界の振る舞いを支配し説明する美しく正確な法則のために愛していました。シャノンの仕事では、初めて、情報の抽象的な実体を支配する正確な定量的法則を見ました…これは、計算の抽象的なプロセスを支配する定量的法則が存在するのではないかという疑問を提起しました…物理法則に直接制約されるものではありませんでした。各問題について、その解決にどれだけの計算労力(仕事)が必要か、そしてそれをどのように測定し決定できるかを決定する定量的法則は存在しうるでしょうか?16
ここでチャーチ=チューリングのテーゼを再訪するのに良い機会です。今日理解されているように、このテーゼは、宇宙のあらゆる物理システムによって実行可能なあらゆる計算が、普遍的な計算モデルのいずれかによっても実行できることを述べています。このテーゼの反例はこれまで見つかっていないことを強調することが重要です。
テーゼのより強力なバージョンは、チューリングマシンが多項式計算コストを超えない限り、任意の物理プロセスをシミュレートできると述べています。このバージョンは、量子コンピュータの可能性を考えると誤っている可能性があり、その記述には修正がありますが、ここで議論する複雑性クラスは、それらの興味深い複雑性クラスとは関係がないため、次のことを強調することが重要です。
見つかる計算上の限界が何であれ、それらは(多項式内では)人間にも適用されます。Hartmanisが言うように、それらは自然法則と見なすことができます。人間がチューリング計算不可能なものを計算できる可能性は非常に低い(理論的には可能ですが)ですし、人間がチューリングマシンよりも速く計算するのに役立つ可能性のある量子アルゴリズムを採用している可能性も低いです。経験的には、複雑性の限界を違反する人間の例は観察されていません。
制限された停止性と償却制限停止性
停止性問題の正確な難しさに関する我々の同じ問いが、HartmanisとStearnsが一部の問題の固有の難しさを明らかにし、現在時間階層定理として知られているものを証明することを可能にしたことは驚くことではありません。これは、計算問題が難しさの無限の適切な階層を形成すると述べています。
ここで提示する問題は、しばしば「制限停止性」として知られており、次のことを尋ねます。任意のプログラムMが入力xに対してnステップ以内に停止するかどうかを決定する複雑性はどうでしょうか?
プログラムを低オーバーヘッドでシミュレートできると仮定すると、$O(n)$で実行できますが、それより速くできますか?これが不可能であるという証明は、停止性定理の同じ対角線論法証明を正確に模倣します(証明スケッチの提示は、他のマシンをシミュレートするオーバーヘッドを考慮しておらず、チューリングマシンよりも1972年のStephen CookによるRAMマシンに関する結果により近いことを指摘します17)。
より速く質問に答えられると仮定します。
$H_n(M, x)$ :=
IF$M$ が $x$ で $n$ ステップ以内に停止THEN TRUE ELSE FALSEただし、$TIME(H_n)
次に定義します。
$G(y)$ :=
IF$H_n(y, y)$ =FALSE THEN TRUE ELSE$n$ 回ループしてFALSEを返す。
停止性定理の証明と同様に、$G$を自身に渡す($G(G)$)と、$G$が行うことと$H$が$G$が行うと述べていることとの間に矛盾が生じます。なぜなら、$H_n$は$n-2$ステップ以内に結果を返し、$G$はさらに1ステップでTRUEを返し、$n$ステップ未満で終了することに注意するからです。
簡単に言えば、プログラムを実行するよりも速く、プログラムが何をするかを知ることはできません。制限停止性は$\theta(n)$です。
しかし、1つの入力から別の入力へと一般化できますか?一部の入力で一生懸命働くことで、他のすべての入力で高速化できますか?ある入力でのプログラムの動作を分析することに一生懸命取り組むことで、他の入力で利益が得られるなら、$K$という十分大きな数の入力が存在し、それらすべてに対する制限停止性の質問に$K
この問題は文献で見つけられなかったので、私はそれを償却制限停止性と呼び、正確に次のように述べることができます。
自然数$n$、$K$が与えられたとき、すべてのTM $M$に対して、$HA_{n,k}(M, x_1,…, x_k)$が$M$がすべての$x_1…x_k$で$n$ステップ以内に停止するかどうかを決定し、それを$K
これもまた、制限停止性からの還元により、否定的な答えです。$UTM$を、与えられたマシンと入力を単にシミュレートする汎用チューリングマシンとします。もし可能であれば、それを使用して次のように$H_{K
ここで、$r_1,…,r_{k-1}$は任意の入力とします。
さて、制限停止性に関する$\theta(n)$の結果は、停止性問題の複雑さに関する我々の質問に実際に答えます。プログラムに関するどんな質問も、それを実行するよりも速く答えることはできないため、プログラムが以前に訪れた状態に達するとすぐに、それは決して停止しないことを知るので、最悪の場合、複雑性は少なくとも状態の数(状態の記録のオーバーヘッドを含む)です。一般的なケースでは、TMは無限の状態を持つことができるため、最悪の場合の複雑性は無限であり、一般的な停止性問題の決定不可能性は、制限停止性の特別なケースとして得られます。
この結果を$\Omega(|S|)$と表記します。そして、我々が見るように、それは非常に堅牢です。計算能力をチューリング完全からより弱いモデルに剥ぎ取ったとしても、それは保持されます。
余談ですが、制限停止性の問題はHartmanisとStearnsによって1965年に時間階層定理の一部として直接証明されましたが(停止性問題は今やその極限ケースと見なすことができます)、ゲーデルがそれ以前に同様のアイデアを使用した可能性があると私は信じています。彼の有名な1956年のジョン・フォン・ノイマンへの手紙[停止性問題の解決不可能性の証明の一般化から導き出せる唯一の推定値は、φ(n) ≥ Knであるように思われる]で、彼は次のように述べています。
… Entscheidungsproblem の解決不可能性の証明の一般化から導き出せる唯一の推定値は、φ(n) ≥ Kn であるように思われる。
ゲーデルもまた、停止性定理の対角線論法証明の有限ケースへの単純な拡張を認識していたようです。
検証は計算機科学における最も困難な問題である
先に進む前に、検証を最も一般的な方法で何を意味するか—検証に関して、もし可能であれば最も望むものは何か—を述べたいと思います。プログラム$M$と、プログラムの性質について言及できる論理における命題$\varphi$が与えられたとき、$M$が$\varphi$を満たすかどうかを決定したいのです。
この非常に一般的な問題が、停止性、「ライス」性(関数表記)、到達可能性などを包含することは容易にわかります。したがって、計算上はそれらすべてよりも簡単ではありません。これは、モデル検査問題としてよりよく知られています(後で簡単に議論する特定の自動モデル検査アルゴリズム、モデルチェッカーとは混同しないでください)。
$M$が$\varphi$のモデルであるかどうか、つまり$\varphi$を満たすかどうかをどのように決定するかは、私たち次第です。計算複雑性理論は、問題の難しさに対処するのであり、特定の解法の難しさに対処するのではありません。例えば、$M$の動作を論理公理の集合で記述し、$\varphi$の証明を演繹的に見つけようと選択するかもしれません。これは満足を示す1つの特定の方法であり、一般的には一般的なモデル検査問題よりも簡単ではなく、したがってその複雑性境界内に留まる必要があります。ここでも、結果はマシンと人間の両方に適用されます。
一般の場合の検証の難しさ(あるいはむしろ不可能性)をすでに確立しているにもかかわらず、現実的な検証を求めてチューリング完全性を放棄しようとする前に、少し異なる視点からもう一度見てみましょう。終了するプログラムの結果を決定するという特定の検証問題に限定することさえできます。これは明らかに一般的なモデル検査問題の特別なケースです。計算可能性と複雑性理論でしばしば慣習的に行われるように、決定問題—真または偽を返すもの—に限定します。さらに、計算可能な上限複雑性を持つ(常に終了する)全域アルゴリズムが知られている問題のみを考慮します。そのような任意の決定問題$P$があり、既知の時間複雑性上限$f(n)$($n$は$P$の入力、$x$の長さ)があるとします。$P$の複雑性の上限がわかっているので、$f(n)$ステップ以内に$P$を決定するアルゴリズム$M_P$が存在することがわかります。次に、決定プログラム$M_P$と入力$x$が与えられたとき、$M$が$x$を受け入れる(真を返す)かどうかを伝える検証プログラム$V$があると仮定します。アルゴリズム$V$は存在し、決定可能である、なぜなら最悪の場合、それは単に$M_P$をシミュレートできるからです。
これらすべてを考慮すると、決定問題$P$を単純に$V(M_P, x)$(これは$P(x)$に等しい)に答える問題に還元できます。$M_P$は特定のプログラム$P$に対して定数なので、この還元は多項式的です。これは、$V$の複雑性が$P$の下限以上でなければならないことを意味します。しかし、$P$は完全に任意に選択されており、時間階層定理により、任意の計算可能な$g(n)$に対して、その複雑性が$g$よりも大きい問題$P$を見つけることができるため、$V$は既知の計算上限を持つすべての問題よりも難しいです。既知の計算上限を持つ任意の決定問題は、制限停止性に還元可能であると言います。言い換えれば、検証は計算機科学における最も困難な問題です。
範囲の限定
検証に取り組むために、左側(プログラム)または右側(プロパティ)を制限することで、生活を楽にすることができます。これまでのところ、プロパティを制限してもあまり役立ちません。なぜなら、最も単純なプロパティ(停止性、結果、到達可能性)でさえ、決定不可能または実行不可能な結果が得られるからです。したがって、マシンを制限してみましょう。
1つの方法は、ループや再帰呼び出しにデクリメントされるカウンターを必要とするスタイルまたは言語でプログラムを書くことによって、容易に停止することが証明できるプログラムに限定することです。これらの言語は総関数言語18と呼ばれ、すべての総関数の有用なサブセットを記述できます。
しかし、制限停止性の対角線論法証明を見ると、$M$を総関数言語で書かれたプログラムに制限した場合、$H_n$もそのような言語で書くことができ、$G$も同様です。同一の結果が保持されます。検証は依然として$\Omega(|S|)$です。しかし、総関数言語におけるプログラムのサイズと状態数の関係は何でしょうか?それは間違いなくすべての原始帰納関数(およびTurnerが総関数言語で容易に計算できると言うアッカーマン関数のような一部の非原始帰納関数)よりも大きいですが、それでも計算可能かもしれません。いずれにせよ、我々の目的のためには依然として無限に等しい19です。
したがって、総関数言語による制限は、検証を容易にするのに役立ちません。実際、不可能だった問題が少し制限するだけで簡単になるという発見があれば驚くでしょう(革張りのシートをなくしても車のコストが90%削減されるわけではありません)。また、すべてのプログラムは、例えば$2^{100}$のような大きなカウンターをすべてのループに追加することで、自明に総関数にすることができることにも注意します。これは物理的な意味を変えることはありません。したがって、一般性を失うことなく、すべての実世界のプログラムは総関数言語で書かれていると仮定できます。総関数言語が役立つなら、すべての言語が総関数であると仮定できたはずです。
総関数プログラムの証明がいかに難しいかについての直感を与えるために、次の10行のJavaまたはCの例は総関数スタイルで書かれています。すべてのループにはデクリメントされるカウンターがあります。これは明らかに常に終了します。また、トリッキーな数学的演算は行わず、減算のみです。
int foo(int x) {
if (x <= 2 || (x & 1) != 0)
return 0;
for (int i = x; i > 0; i--)
if (bar(i) && bar(x - i))
return i;
crash(); // reachable?
}
boolean bar(int x) {
for (int i = x - 1; i >= 2; i--)
for (int s = x; s >= 0; s -= i)
if (s == 0)
return false;
return true;
}
しかし、数学者たちは、このプログラムが決して失敗しない(つまり、crash()に到達しない)ことを270年間証明できませんでした。このプログラムは、ゴールドバッハの予想が偽である場合にのみクラッシュします(もちろん、intをより大きな整数型に置き換えると仮定します。32ビット整数では成り立つことはわかっていますが、64ビット整数については確信がありません)。この時点で、一部の人は「もちろん、難しい数論の問題をエンコードするプログラムの動作を証明するのは難しいだろう!」と言うかもしれませんが、それは問題の誤解です。このプログラムが有名な難解な数論の問題をエンコードしていることに気づくことは、この特定のプログラムが検証するのが難しいことを納得させる方法にすぎません。しかし、それは、私たちが日常的に遭遇するプログラムよりも、このプログラムが検証するのがどれほど難しいかを教えてくれるわけではありません。プログラムがゴールドバッハの予想に対応していることを知らなかった場合(またはゴールドバッハが予想をしなかった場合)、それを見て、プログラムの検証がそれほど難しいと判断できたでしょうか?
さて、計算モデルを制限する他のさまざまな方法があります。例えば、Stephen BellantoniとStephen Cookは、すべてのプログラムがPTIMEで計算可能である言語を発明しました20。別のモデルはプッシュダウンオートマトン(PDA)です。これは興味深くトリッキーです。多くのPDAの性質は、モデルが無限の状態を許容するにもかかわらず検証できますが、わずかな風でも言語をチューリング完全にすることができます(例:通信する2つのPDAはチューリング完全です。なぜなら、一方のマシンのスタックが読み書きヘッドの左側のテープであり、もう一方のマシンがヘッドの右側のテープであると想像してください)。
代わりに、最も有用な計算モデルである有限状態機械に直接ジャンプし、そこで最も興味深い結果を見つけることができます。
有限状態機械(FSM)の完全な検証のための自動化された手法—モデルチェッカーと呼ばれる—は1980年代から存在し、おそらく業界で最も一般的な形式検証技術です。実用的な自動化手法が存在するため、問題の複雑性は広範囲に研究されてきました。ただし、用語に惑わされないでください。このセクションで提示する2つの結果は、モデル検査問題の固有の複雑性に関するものであり、特定のモデル検査アルゴリズムの複雑性に関するものではありません。
時間論理(1977年にAmir Pnueliによって計算機科学に導入され、彼はチューリング賞を受賞しました)は、1970年代後半からプログラムプロパティを指定するための主要な論理となっています。1980年代には、有限状態機械と時間論理プロパティのための完全自動化されたモデル検査アルゴリズムが発明されました(最初にEmerson、Clarke、Sifakisによって)。ある種の時間論理、計算木論理(CTL)と呼ばれるものについては、モデル検査の複雑性は$O(|\varphi||S|)$です。別のもの、線形時間論理(LTL)については、$2^{O(|\varphi|)} O(|S|)$です。プロパティ式$\varphi$の長さが定数と見なされる場合、両方の境界は基本的に$O(|S|)$であり、停止性問題によって指示されるものと同じです。この結果、すなわち非常に有用な論理に対して、状態空間のサイズに対して線形である(したがって、モデル検査問題の右辺に対して比較的弱く感応する)モデル検査アルゴリズムが存在するという結果は、Emerson、Clarke、Sifakisにチューリング賞をもたらしました。
正しさの分解はできない
一般的な複雑性クラスは、時には粗すぎます。パラメータ付き複雑性は、一部のケースでパラメータ$k$(実際には入力$x$の関数である$k(x)$)によっては非現実的(例えば指数関数的)である可能性があるが、それ以外は入力の長さに対して多項式的であるという、より細かいクラスを導入することによって、この問題に対処します。問題は、複雑性が$f(k) \cdot |x|^{O(1)}$($k(x)$をパラメータとする)である場合、FPTに属します。現実世界でパラメータが小さく保たれる場合、問題は現実的になります。FPTに属する問題の例はSAT、ブール充足可能性問題です。これはNP完全ですが、ナイーブなアルゴリズムは変数の数に対して指数関数的であり、式の長さに対して線形です。別の例はHindley-Milner型推論であり、それが実用的に効率的である理由です。
検証(FSMの)はFPTであり、実用的に現実的にすることができますか?2005年の論文はこの問題を調査し、プログラムをモジュール化することによって検証の複雑性をパラメータ化しようとします。アイデアは、おそらく各モジュールまたはコンポーネントを個別に検証でき、次にコンポーネントの合成を検証することは、コンポーネントの数(ただしこれは低いでしょう)に対して非現実的になるかもしれませんが、各コンポーネントのサイズまたは各コンポーネントの内部「隠し」状態の数に対して非現実的になることはないということです。結果は否定的であり、証明は$k$個のFSMが約$k$個のテープ平方を持つNDTMをシミュレートできることに気づくことに基づいています。空間制限されたNDTMの検証はFPTではないことが知られています。
[我々の結果は、これらの問題が、パラメータ付きの意味でFPTであっても、おそらく現実的ではないことを示しています…パラメータを$k$として扱う他の方法を考慮しても、この難しさを解決できるとは考えていません21。
この結果は非常に深遠です。これは、モジュール化によってプログラムの正しさを証明する労力を一般的に減らすことができないことを意味します。正しさは分解できません。
上記のfoo/barプログラム、別名ゴールドバッハプログラムは、そのような効果を示しています。barは正しいです(つまり、パラメータが素数であるかどうかを正しく決定します。私の特定のルの実装のバグは無視します)。これによりfooが残ります。最初の2行は自明であり、次の3行が残ります。これ以上モジュール化され、構成可能であるものはありません!これらは単なる単純な下降forループ、単一の減算操作、およびbarの2つの非常にモジュール化された使用法を組み合わせた単一の論理和です。それにもかかわらず、それら3行の動作の証明は300年間私たちを悩ませてきました。なぜなら、bar(つまりisPrime)は、正しいにもかかわらず、ある文脈では推論できますが、この文脈ではそれほど容易ではありません。私たちは、正しく指定されたモジュール(bar)の単純な構成(foo)でさえ、依然として解読不能な全体につながることを示しています。
言語抽象化は一般的に悪用できない
最後に言語の問題に取り組みます。私たちはプログラムを巨大な状態遷移図として記述しません。私たちは、抽象化を備えた、おそらく適切な意味論さえ備えた、優れたプログラミング言語を使用して、その状態空間と比較して非常に簡潔なプログラムを作成します。したがって、FSMソースコードの構造を悪用できますか?これはシンボリックモデル検査問題です。
理論的には、楽観的な余地があります。検証問題の計算複雑性を研究しているPhilippe Schnoebelenは次のように述べています。
計算複雑性理論の観点からは、シンボリックモデル検査が、たとえ最悪の場合でも、より効率的に解決できない理由はありません…シンボリックモデルチェッカーは、非常に特殊な種類の巨大な構造、すなわち簡潔な表現を持つもののみを扱います…(非常に少数の巨大な構造が簡潔な表現を持つことに注意してください。単純な基数論で示されるように)22
ここには、FSMの言語を記述するための言語とは具体的に何を意味するかを説明する必要がある微妙な点があります。理論的には、チューリング完全モデルとFSMの違いは非常に明確です。一方は文脈依存言語を認識でき、もう一方は正規言語のみを認識できます。しかし、実際には、すべてのコンピュータは有限であるため、すべての実際のプログラムは有限状態機械であると言えます。したがって、FSMに適用される結果は、もちろん、一般的に(つまり、実際には巨大なFSMであるチューリング完全言語でさえ)保持されますが、FSM言語について話すときは、ソースコードを見ただけで各プログラムの最大状態数が容易に計算できる言語を意味します。
残念ながら、簡潔な表現を持つプログラムに限定しても役立たないことが判明しました。シンボリックモデル検査問題はPSPACE完全であり、これは状態図を簡潔なプログラムの状態図を展開してその構文表現を完全に忘れることと同じ複雑性です。これは最悪の場合だけでなく、多くの実世界のケースでも当てはまります。
言い換えれば、簡潔な表現を許容するKripke構造は、モデル検査の目的では、任意のKripke構造よりも単純ではありません。
実際、これは到達可能性問題から同値性問題まで、多くのインスタンスで観察されており、現在では経験的事実と呼ぶことができます22。
(Kripke構造は基本的にプログラムの状態遷移グラフであり、記述されている言語とは無関係です。構文表現を考慮せずにプログラムについて抽象的に話す方法です。)
実際、プログラムの抽象化が検証複雑性にどのように影響するかを図示できます。次の図は、Rajeev Alur23による論文からのもので、言語で利用可能な抽象化に基づいて、プログラムサイズに対するモデル検査の複雑性を示しています。
[画像: Programming Abstractions]
一般に、変数や並行性などの抽象化は、小さな状態空間の直積である状態空間を作成できるようにしますが、簡潔性は指数関数的に増加しますが、検証複雑性は同じ量だけ増加します。これは最後の結果を考えると驚くことではありません。
実際には、階層と呼ばれる1つの抽象化があり、簡潔性を指数関数的に増加させますが、特定のケースでは複雑性を多項式的にしか増加させません。この特性により、組み込みおよびRTソフトウェアで広く使用されていますが、「プレーン」プログラミング言語では一般的ではありません(引数なしのサブルーチンは階層を構成すると信じています)。関数の単純な抽象化、つまり引数付きのサブルーチンは、変数抽象化と階層抽象化の組み合わせです。
簡単な例として、FSMの検証でさえなぜ難しいのかを考えてみましょう。ブール変数と関数呼び出しのみを持つ言語を考えます。高階関数、再帰、反復は提供されていません。そのような言語は明らかにFSM言語です。例えば、このプログラムの状態数は$\leq 2^6$です。
A() = B(TRUE) ∧ B(FALSE)
B(a) = C(a, TRUE) ∨ C(a, FALSE)
C(a, b) = D(a, b, TRUE) ∧ D(a, b, FALSE)
D(a, b, c) = E(a, b, c, TRUE) ∨ E(a, b, c, FALSE)
E(a, b, c, d) = F(a, b, c, d, TRUE) ∧ F(a, b, c, d, FALSE)
F(a, b, c, d, e) = X(a, b, c, d, e, TRUE) ∨ X(a, b, c, d, e, FALSE)
X(a, b, c, d, e, f) = ((a ∧ b) ∨ c) ∧ ¬d ∧ (e ∨ f)
しかし、この言語でプログラムを検証することはPSPACE困難です。なぜなら、上記の自明なプログラムでさえ、PSPACE完全であるTQBF—真の量化ブール式—問題を直接エンコードしているからです(この場合、式は$\forall a \exists b \forall c \exists d \forall e \exists f . ((a \land b) \lor c) \land \lnot d \land (e \lor f)$です)。
ただし、シンボリックモデル検査の結果は、モデル検査問題の右辺に敏感であることを指摘する必要があります。言語抽象化は任意のプロパティを検証するのに役立ちませんが、それらは(そして実際に)状態空間削減を作成するのに役立ち、それを使用して特定のプロパティを効率的に検証できます。これについては、次の章で抽象解釈に言及する際に簡単に説明します。例えば、上記の単純な「TQBF」プログラムでは、変数aの値がプログラムの結果に影響を与えるかどうかを安価にチェックするために、言語抽象化と抽象解釈を使用できます。
これまで見てきたすべての結果を踏まえると、次の非公式定理を述べることができます。
すべてのプログラムが現実的に検証可能な、一般的に有用なプログラミング言語は存在しない。
これで、正しいプログラムを書くのがなぜ難しいのかがわかりました。それはそうしなければならないからです。しかし、プログラムの書き方に関わらず、常にすべてのプログラムを検証することはできませんが、一部のプログラムを一部のプロパティについて検証することを妨げるものはありません。次の章で見るように、ソフトウェア検証のどの方法も、私たちが探求してきた限界を克服することはできません。そして、まさにそれらの限界が、すべての検証アプローチの設計とトレードオフに影響を与えます。もちろん、ソフトウェア検証は広大な主題であり、私の目標は、アプローチとその複雑性結果との関係を簡単に説明することだけです。
第III章:検証
これで、正しいプログラムを書くのがなぜ難しいのかがわかりました。それはそうしなければならないからです。しかし、プログラムの書き方に関わらず、常にすべてのプログラムを検証することはできませんが、一部のプログラムを一部のプロパティについて検証することを妨げるものはありません。次の章で見るように、ソフトウェア検証のどの方法も、私たちが探求してきた限界を克服することはできません。そして、まさにそれらの限界が、すべての検証アプローチの設計とトレードオフに影響を与えます。もちろん、ソフトウェア検証は広大な主題であり、私の目標は、アプローチとその複雑性結果との関係を簡単に説明することだけです。
チューリングは、正しいソフトウェアを書くことの難しさを十分に理解していました。1947年の講演で彼はこう述べました。
[… ]何ができるかの可能性は計り知れません。私たちの困難の1つは、適切な規律を維持することであり、私たちが何をしているのかを見失わないようにすることです。
機械は、ユーモアのセンスや比例感覚なしに、指示されたことをすべて非常に明確に解釈します。それと通信する際に、あなたが正確に何を意味するかを言わない限り、問題が発生するのは避けられません。
チューリングの解決策は?型です!
私たちは、秩序を保つために、多くの効率的な図書館員タイプを必要とするでしょう。
[これはうまくいかなかったジョークです…]
型について主に言及するのは、プログラミング言語に関心のある開発者の間で人気のあるトピックであり、それらはオンライン開発者コミュニティで不均衡に代表されているためですが、型は形式検証の一形態と見なすことができ、検証方法の議論の最後にうまく収まるためでもあります。
動機として、次の質問をしたいです。ここでライス氏の定理をもう一度示します。
部分関数の非自明な性質について、プログラム(TM)Mがその性質を持つ部分関数を計算するかどうかを決定するアルゴリズムは存在しない。
しかし、これは可能であるだけでなく、例えばC、Java、またはHaskellプログラムがintを返すことを保証するのは非常に簡単です。これは定理との矛盾ではありませんか?
「構築による正しさ」のため、矛盾はないと仮定する人もいるようです。これは誤りです。ライス氏の定理は構築については何も述べておらず、それには正当な理由があります。型を使用してプログラムの結果の性質を簡単に証明できると仮定すると、「構築による正しさ」のためです。次に、プログラムを検証するための効率的なアルゴリズムを次に示します。私がPythonでプログラムを書き、あなたがそれを例えばHaskellに翻訳し、 voilà!問題解決です。これは不可能です。なぜなら、複雑性はコンピュータだけでなく人間にも適用されるからです。
真の答えはライス氏の定理に直接対処する必要があります。性質が自明であるか、または部分関数を計算しているものがTMではないかのどちらかです。
int戻り値の型の場合、実際には、プログラムが決して終了しないか、整数を返すかのどちらかであることを意味します。これは自明な性質です。なぜなら、すべてのプログラムは決して終了しないか、整数として解釈できるものを返すかのどちらかだからです。結果に関する1ビットの情報さえも知ることはできません。
さて、一部の人は、これが常にそうではないことをすぐに認識するでしょう。例えばHaskellでは、プログラムの結果が数字の文字列であることを比較的簡単に示すことができます。これは多くのビットを指定し、各バイトの出力を256通りのうち10通りの可能な結果に制限します。では、なぜこれはライス氏の定理の違反ではないのでしょうか?それは、その性質がチューリングマシンによって生成されたのではなく、有限状態機械によって生成されたからです。次にこれを示します。しかし、まず、他のいくつかの検証方法を調べるために迂回する必要があります。
モデルチェッカー
有限状態機械が十分に小さい場合、実用的な自動モデル検査アルゴリズムが存在することがわかりました。一般に、モデルチェッカーという名前は、プログラムの特定の構文表現にあまり依存しないアルゴリズムに適用されます。
最新のモデルチェッカーは、ますます大きな状態空間を探索するために非常に洗練されたアルゴリズムを使用しています24。そして、一部のケースでは無限の状態空間を探索します。それらの主な利点は、使いやすく、非常に一般的であることです。それらは実際にモデル検査問題を自動的に解決します。通常、それらがチェックするプロパティは時間論理のフレーバーで指定されており、これは任意のプログラムプロパティを表現するのに十分豊かです。それらの主な欠点は、それらがモデル検査問題を解決するため、いわゆる「状態爆発問題」の影響を受けることです。つまり、小さなプログラムでさえ、巨大で非常に不規則な状態空間を生成する可能性があるということです。
これは、交互ビットプロトコルの状態空間の例です。プログラムは約30行です。
[画像: Alternating Bit Protocol (ProB)]
そして、これは車で使用されるCANバスプロトコルの状態空間です。
[画像: CAN Bus Protocol (ProB)]
幸いなことに、最も厳密な検証を必要とするほとんどのプログラム—少なくとも歴史的には—は比較的小さかった(ハードウェアまたは組み込みリアルタイム)ため、モデル検査が業界で最も広く使用されている形式検証方法であることは驚くことではありません。
状態爆発問題がモデルチェッカーに影響を与えるのは、使用するアルゴリズムのためではなく、一般的なケース—すなわちすべてのプログラム、すべてのプロパティ—に対するモデル検査問題を正確に解決しようとするためであり、したがって、私たちが示した結果($O(|S|)$)のすべての負担を負うことを理解することが重要です。
ちなみに、ハノイの塔プログラムの状態空間はシェルピンスキーの三角形です!
[画像: Towers of Hanoi, 6 discs (ProB)]
その他の例は、ProBウェブサイトで見つけることができます。
演繹的証明
演繹的証明(すなわち、$M \vdash \varphi$を使用して$M \vDash \varphi$を示す)は、もう1つの一般的なアプローチです。モデルチェッカーと同様に、それは正確であり、したがって計算上はモデル検査問題よりも簡単ではありません(実際、多くのケースで両者は同等にすることができます)。
しかし、それも同じ最悪ケースの複雑性境界の影響を受けるにもかかわらず、モデルチェッカーよりもスケーラブルになる可能性があります。なぜなら、それは非常に特定の問題に合わせて調整できるからです。そして、演繹的方法で検証されたプログラムは、通常、演繹的証明を念頭に置いて記述されます。演繹的証明を使用する人々は、プログラムを記述してからそれを証明するわけではありません。彼らは手と手を組んで記述し、証明します。証明が可能になるように、プログラムを厳しく制限することがよくあります。
自動証明ツール(特にSMTソルバー)には興味深い進歩がありますが、これらは通常、単純な定理の多くを支援できます。しかし、一般的には、現在、人間が作業の大部分を行っています。
経験的な証拠は、このアプローチ—機能するように調整できるものの—非常にコストがかかることを示唆していますが、現在の高信頼性ソフトウェア開発方法論(例えば防衛産業で使用されるもの)よりも高くはありません。しかし、それらがなぜそれほど難しいのかがわかりました。誰かが複雑性の代償を支払わなければならず、それがコンピュータでなければ、それは私たちです。業界では、手動の演繹的証明は、通常、自動証明とモデルチェッカーの結果を結びつけるために使用されますhttp://events.inf.ed.ac.uk/Milner2012/J_Harrison-html5-mp4.html。
証明を見つけることの難しさを脇に置いたとしても、現実的な証明—つまりプログラムのサイズに対して多項式長である証明—が存在しない可能性さえあります。これはよく知られた結果です(CookとReckhowによる25)。命題計算論—すべての論理の中で最も単純な、ブール変数とブール演算子(and、or、not)のみ—でさえ、すべてのトートロジーに対して短い証明が存在するのは、$NP = coNP$の場合のみであり、これはそうではないと仮定されています。
抽象解釈(静的解析)
検証に対するエレガントで数学的に深い解決策は、抽象解釈と呼ばれ、1970年代にPatrickとRadhia Cousotによって導入されました26。通常、この手法を採用するツールは静的解析ツールと呼ばれます。この手法は完全に自動化されていますが、不正確であることによって実行不可能な複雑性境界を回避します(言い換えれば、「わかりません」と質問に答える場合があります)。
非常に大まかな考え方は、入力プログラムの健全だが精度が低い抽象化、通常は状態数が少ないFSMを考慮し、それをモデル検査することです。複雑性は抽象化の$O(|S|)$です。例えば、次のプログラムを考えます。
p0: while (true)
p1: if isEven(x)
p2: then x := x div 2
p3: else x := x + 1
このプログラムは無限の状態空間を持ちます(xが無制限の整数であると仮定)。しかし、$x$のパリティのみを気にする場合、xの値に次の変換を適用できます。
[画像: The data abstraction]
そして、次の4状態の抽象プログラムを作成し、ラベルp2、p3で何が起こるかを知ることができます。
[画像: The abstract program]
この手法の複雑性コストは、常にそうであるように、$O(|S|)$、状態数のオーダーですが、抽象プログラム内であり、これは非常に小さいです(変換のコストに加えて)。欠点は、当然のことながら、抽象化が常に興味のあるプロパティを捉えるとは限らず、たとえ捉えたとしても—すべての状況でそうとは限りません。この例では、ラベルp0とp1でのXのパリティを知りません。
型
型の見方の1つは、値の集合を具体的な型として抽象化する抽象解釈27です。抽象プログラムでは、変数は型を値として取ります。抽象化の状態数はいくつですか?具体的な型の連鎖の数と同じくらいです。各状態は、適用中の関数と「現在の」値(型)であり、したがって、具体的な型の数にまで関数の数を掛けたものになる可能性があります。
[画像: Types as Abstract Interpretation]
具体的な型の数は、直接記述された型よりも多い場合があります。なぜなら、プログラムは多相関数でジェネリック型を持つことができるからです。抽象プログラムでは、これは具体的な型インスタンスを取り、別のものを返す関数になります。具体的な関数が値3を取り、値5を返すのと同様に、抽象関数は抽象値Integerを取り、値[Integer](整数のリスト)を返すことができます。型によって作成される抽象化の主題は、ここで非常に大まかにしか議論されていないことに注意してください。
したがって、計算結果の$O(|S|)$と抽象解釈の理解のみを使用して、型推論アルゴリズムの境界をすぐに得ることができます(型推論は制約問題の解決を必要とするため、これはより難しい可能性があります)。
依存型を持たないプログラミング言語(そしてそれが何であるかわからない場合は、それほど重要ではありません)では、その数は比較的少なく、有限状態機械です。型はFSMの性質を表現するため、証明できる性質はチューリング完全プログラムの結果ではなく、FSMの結果であるため、ライス氏の定理との矛盾はありません。
非依存型システムがFSMの性質のみをエンコードしているというさらなる確信が必要な場合は、Haskell開発者であれば、次の演習を試して確信を得ることができます。各関数本体(ライブラリ関数も含む)を、再帰を定数深度または無限深度(ほとんどの場合、型をインスタンス化するには深度0または1で十分です)を使用して、明らかにFSMであるものに置き換えてみてください。元のプログラムとは完全に異なり、おそらく完全に間違っているFSMプログラムにHaskellプログラムを置き換えることができることに気づくでしょう。ただし、シグネチャの変更は必要ありません。
修正: 読者@samthと@kamatsu8は、上記の記述は多相再帰が使用されている場合(Haskellはサポートしていますが、推論しません)は正しくないと指摘しました。彼らは、制御状態数が少ないプッシュダウンオートマトン(モデル検査も現実的である)にしか置き換えられない例を提供しました。
一方、依存型を持つ言語では、具体的な型の数は無限になる可能性があり、したがって型推論(依然として$\Omega(|S|)$)は無限の複雑性、つまり決定不可能性を持ちます。それは本当にそれほど単純です。
型と演繹的証明の対応(命題型対応またはCurry-Howard対応と呼ばれる28)に精通している読者は、演繹的証明も抽象解釈の特別なケースと見なすことができる理由を理解できますが、ここではこれ以上探求しません。
このセクションを締めくくるために、Xavier Leroy29(形式的に検証され認定されたCコンパイラCompCerthttp://compcert.inria.fr/の著者)の講演からの素晴らしいスライドを以下に示します。これは、要求される労力、提供される保証、および最も適したプログラムサイズによって、さまざまな形式検証方法の特性をチャート化しています。
[画像: Formal Verification Methods]
結論
彼の有名な記事「No Silver Bullet」の続編で、彼はプログラマーの生産性が10倍になるような単一の進歩は決して見られないだろうと主張しました31。Fred Brooksは次のように書いています。
アインシュタインの光速を超えるものは何もないという声明は「暗い」または「陰鬱」ですか?計算できないものがあるというゲーデルの結果はどうですか?… ソフトウェアの本質的な性質は、生産性、信頼性、単純性において、10倍の改善がもたらされる可能性が低いことを示唆しています32。
そして彼はWladyslaw M. Turskiの「No Siver Bullet」に対する見解を引用しています。
すべての誤った科学的試みの中で、卑金属を金に変えるとされる物質、賢者の石の探求ほど哀れなものはありません。何世代にもわたる研究者によって熱心に追求され、世俗的および精神的な支配者から多額の資金提供を受けた錬金術の至高の対象は、物事が私たちの望む通りであるという一般的な仮定、つまり願望的観測の純粋な抽出物です。それは非常に人間的な信念です。解決不可能な問題の存在を受け入れるには多大な努力が必要です。たとえそれが存在しないことが証明されていても、あらゆる困難に逆らって抜け道を見たいという願望は非常に、非常に強いです。そして、私たちのほとんどは、不可能を達成しようとするこれらの勇敢な魂に多くの同情を持っています。そして、それは続きます。円の二等分に関する論文が書かれています。失われた髪を回復するローションが調合され、よく売れています。ソフトウェアの生産性を向上させる方法は考案され、非常によく売れています。あまりにも頻繁に、私たちは自分たちの楽観主義に従う(またはスポンサーの楽観的な希望を利用する)傾向があります。あまりにも頻繁に、私たちは理性の声を無視し、万能薬販売業者のサイレンの呼び声に耳を傾けることをいとわないのです。
最初の2つのセクションでカバーしたすべてが、BrooksとTurskiが正しいという数学的な証明であると私は信じています。しかし、私たちは何をすべきでしょうか?
経験主義への呼びかけ
計算機科学は、基本的な構成要素—ラムダ計算のベータ還元やチューリングマシン命令—で構成される対象—コンピュータプログラム—を研究していることを見てきました。それらはそれ自体では数学的推論に容易に服従しますが、それらの相互作用は本質的に実行不可能であることです。これは物理学に似ていると思います。例えば、重力方程式は非常に単純で、複数のインスタンスに対する方程式の合成は非常にうまく機能しますが、3体の相互作用でさえすでにカオスであり、閉形式解はありません。
物理学から学ぶべきであり、経験主義を受け入れるべきだと思います。検証の問題をもう一度考えてみましょう。
左側または右側を制限する必要があります。検証が手頃な価格になるような一般的に有用なプログラムのカテゴリを見つけることは unlikely であることは、これまでのところ明らかになったはずです。なぜなら、最も単純な計算モデルであるFSMでさえ、一般的には検証が実行不可能だからです。しかし、次の明白な観察を行うことができます。私たちが気にかけているすべてのプログラムは、人間によって作成されます。もしあなたが望むなら、人間が生成するすべてのマシン$M$を生成する、一つの大きなTMとして人類を考えることができます。人類が生成するマシンにパターンが見つかり、手頃な価格の検証が可能になる可能性があります。しかし、人類をプログラムとして分析することは真に実行不可能であるため、唯一実行可能な方法は、人間が書くプログラムの経験的研究です。プログラムの種類、サイズ、コストなどの分類から始めることができます。
この観察は、右側の有用な制限も可能にします。これまでのところ、私たちが検討した最も単純なプロパティ(停止性のような)でさえ、グローバルなものでした。しかし、実際には、一部のローカルプロパティも証明に非常に役立つことを—経験的に!—知っています。その良い例はメモリ安全性であり、これは一般的でコストのかかるバグの原因であることが知られています。他の有用なローカルプロパティを見つけることができるかもしれませんが、これも経験的研究が必要です。原因、普及率、プログラムの種類との関連性、そして最も重要なこととしてコストによるバグの分類から始めるのが良いでしょう。
そのような経験的研究には、学術界と産業界の協力が必要です。その経験的知識があれば、物理学が行うように、特殊な数学的手法—単純化された仮定、ヒューリスティック、または近似—を使用して、興味深い特殊なケースに取り組むことができます。
そのような経験的研究の美しい例の1つは、トロント大学での最近の研究です。この研究では、大規模分散システムにおける壊滅的な障害の大部分が、プログラマーがエラー処理コードに十分な注意を払っていないことに起因することが発見されました。これは明らかに心理的な影響です。
壊滅的なシステム障害のほぼすべて(92%)は、ソフトウェアで明示的に通知された非致命的なエラーの不適切な処理の結果であり、壊滅的な障害の58%では、根本的な障害はエラー処理コードの単純なテストによって容易に検出できた可能性があります33。
彼らは分散システムにおける壊滅的な障害を研究し、多くのエラーが人々が例外処理コードに注意を払っていない結果であることを発見しました。これは明らかに人間がソフトウェアを書く際の心理現象です。研究者たちは次に、この危険なパターンを特定する単純なリンターを作成しました。この単純なツールは、Cassandra、HBase、HDFS、およびMapReduceにおける壊滅的な障害の33%を防ぐことができたでしょう。
計算機科学は物理学ではありませんが、数学でもありません。
Juris Hartmanisは次のように書いています。
計算機科学は、既知の科学とは非常に異なっており、科学の中で新しい種として見なされる必要があります34。
複雑性は不可欠!
Fred Brooksが書いた言葉で締めくくります。「複雑性は私たちが扱っているビジネスであり、複雑性は私たちを制限するものなのです。」
しかし、Turskiが認識したように、一部の人々は哲学的にこの概念に不快感を抱き、証明された限界に逆らおうとします。彼らは、世界—そしてここでは計算だけを指しているわけではありません—は本質的に単純であり、それを不必要に複雑にしているのは人や組織の愚かさである(あるいは、ソフトウェアの場合、「愚かな」プログラミング言語である)と考えています。注意深い数学的推論を適用すれば、あらゆる問題の解決策を見つけることができるはずです。
計算複雑性理論を一文で要約すると、「難しい問題に簡単な解決策はない」ということです。ここで提示された結果を要約すると、「…そして、あなたの問題が計算プロセスを予測、作成、または指示することであるなら、それは難しい」となります。
計算機科学は、最も小さなシステムでさえ本質的な複雑性が生じうることを証明したまさにその学問です。しかし、時には計算機科学者やソフトウェア開発者自身が、彼らの分野の基盤に挑戦しようとします。複雑性は本質的です。それは飼いならすことはできず、唯一の万能な答えはありません。私たちができる最善のこと—社会においても計算においても—は、多くの場当たり的なテクニックを適用し、もちろん、問題の特定の性質について可能な限り多くを学ぶことです。
オンラインディスカッション
選定参考文献
エントリは、記事/講演で言及された順序で並べられています。参考文献の完全なリストは以下の脚注にあります。
-
A. M. Turing, On Computable Numbers, with an application to the Entschidungsproblem, 1936
-
A. M. Turing, A lecture to the London Mathematical Society, February 20, 1947
-
J. Hartmanis and R.E. Stearns, On The Computational Complexity of Algorithms, 1965
-
Juris Hartmanis, Turing Award Lecture: On Computational Complexity and the Nature of Computer Science, 1994
-
S. Demri, F. Laroussinie and Ph. Schnoebelen, A Parametric Analysis of the State-Explosion Problem in Model Checking, 2005
-
Philippe Schnoebelen, The Complexity of Temporal Logic Model Checking, 2002
-
Edmund M. Clarke, Model checking: my 27-year quest to overcome the state explosion problem, 2007
-
Edmund M. Clarke, Progress on the State Explosion Problem in Model Checking, 2001
-
David A. Schmidt, Binary Relations for Abstraction and Refinement, 1999
-
Patrick Cousot, Abstract Interpretation Based Formal Methods and Future Challenges, 2001
-
Patrick Cousot, Types as Abstract Interpretations, 1997
-
Jean-Yves Girard (Translated and with appendices by Paul Taylor, Yves Lafont), Proofs and Types, 1989
-
Juris Hartmanis, Some Observations About the Nature of Computer Science, 1993
-
Frederick P. Brooks, Jr., No Silver Bullet and No Silver Bullet, Refired in The Mythical Man-Month, Essays on Software Engineering, Anniversary Edition, Addison-Wesley 1995
会議では、産業界のソフトウェア開発と場当たり的な解決策の経験的研究(または少なくとも経験的観察への配慮)の必要性を強調する研究者たちを見て嬉しく思いました。このテーマを含むいくつかの講演は次のとおりです。
-
James Noble, Notes on Post-Post-Modern-Modern Programming
-
Peter O’Hearn, Move Fast to Fix More Things
-
Ross Tate, Redesigning Type Systems for Industry OO
-
Emina Torlak, Synthesis and Verification for All
-
Sean McDirmid, The Future of Programming will be Live
また、Truffle/Graalのクールな講演/デモもぜひご覧ください。
-
John W. Dawson, Jr., Logical Dilemmas, The Life and Work of Kurt Gödel, A K Peters,1997 p. 71 ↩
-
Dawson, p.69 ↩
-
Saul Kripke, The Origins and Nature of Computation, Lecture at Tel Aviv University, June 13, 2006, 1:45:50-1:47:10 ↩
-
Alonzo Church, An Unsolvable Problem of Elementary Number Theory, 1936 ↩
-
A. M. Turing, On Computable Numbers, with an application to the Entschidungsproblem, 1936 ↩
-
Scott Aaronson, Rosser’s Theorem via Turing machines, July 2011 ↩
-
到達可能性が停止性より難しくないことを示すには、任意の到達可能性問題を考え、既存のすべての停止状態を無限ループに置き換え、テストしたい状態を停止状態としてマークします。停止性問題を解決することは、変換されたプログラムが元のプログラムでテストされた状態が到達可能であった場合にのみ停止するため、到達可能性問題を解決することと同一になります。↩
-
Tibor Rado, On Non-Computable Functions, 1961 ↩
-
Adam Yedidia and Scott Aaronson A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory, 2016 ↩
-
無限の対象の概念は、一部の論理学者がそれに反対する意見を持っているなど、数学においては常に議論の的となってきましたが、反対の理由は、まさに計算に関連付ける物理的な限界と同じであると私は言いたいと思います。↩
-
A. M. Turing, A lecture to the London Mathematical Society, February 20, 1947 ↩
-
一部の読者は異議を唱えるかもしれません。結局のところ、プログラムは抽象的な数学的概念です。しかし、学術分野としての物理学が、すべての物理オブジェクトのすべての性質の研究に関心がないのと同様に(そうでなければ化学や生物学は別個の分野として存在しないでしょう)、数学という学術分野は、すべての数学的オブジェクトの研究に関心を持つ必要はありません(もちろん、数学は道具として、物理学、化学、生物学で使用されるのと同様に、計算機科学で広く使用されています)。↩
-
Jack Edmonds, Paths, Trees, and Flowers, 1965 ↩
-
A panel on BBC radio, recorded January 10, 1952, as appears in, B. Jack Copeland (Editor), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life: Plus The Secrets of Enigma, Oxford University Press, 2004, p. 503 ↩ ↩2
-
J. Hartmanis and R.E. Stearns, On The Computational Complexity of Algorithms, 1965 ↩
-
Juris Hartmanis, Turing Award Lecture: On Computational Complexity and the Nature of Computer Science, 1994 ↩
-
Stephen A. Cook and Robert A. Reckhow, Time Bounded Random Access Machines, 1972 ↩
-
D. A. Turner, Total Functional Programming, 2004 ↩
-
全域性—特に関数型言語では—有用な目的を果たす可能性があることに注意すべきです。ただし、検証を容易にすることはその1つではありません。↩
-
Stephen Bellantoni and Stephen Cook, A New Recursion-Theoretic Characterization of the Polytime Functions, 1992 ↩
-
S. Demri, F. Laroussinie and Ph. Schnoebelen, A Parametric Analysis of the State-Explosion Problem in Model Checking, 2005 ↩
-
Philippe Schnoebelen, The Complexity of Temporal Logic Model Checking, 2002 ↩ ↩2
-
Rajeev Alur, Formal Analysis of Hierarchical State Machines, 2003 ↩
-
Edmund M. Clarke, Model checking: my 27-year quest to overcome the state explosion problem, 2007 and Progress on the State Explosion Problem in Model Checking, 2001 ↩
-
Stephen A. Cook and Robert A. Reckhow, The Relative Efficiency of Propositional Proof Systems, 1979 ↩
-
導入については、Patrick Cousot, Abstract Interpretation Based Formal Methods and Future Challenges, 2001 を参照してください。抽象化と洗練の一般理論に関する魅力的で読みやすい概要については、David A. Schmidt, Binary Relations for Abstraction and Refinement, 1999 を参照してください。↩
-
型システム専門家は、次の2つの論文を参照したいかもしれません。Patrick Cousot, Types as Abstract Interpretations, 1997 および Roberta Gori, Giorgio Levi, An experiment in type inference and verification by abstract interpretation, 2002。これらの論文は私の理解を超えています。↩
-
詳細な概要については、Jean-Yves Girard, Proofs and Types, 1989 を参照してください。↩
-
Xavier Leroy, Desperately seeking software perfection, October 20, 2015 ↩
-
F. P. Brooks, No Silver Bullet: Essence and Accidents of Software Engineering, 1986 ↩
-
実際、Brooksは「技術または管理技術のいずれにおいても、10年以内に生産性、信頼性、単純性のいずれかで1桁の改善を約束する単一の開発はありません」と書いています。30年が経過しても、すべての開発を合わせても生産性が1桁向上していないことを考えると、そしてBrooksが後に彼の非公式な予測を自然法則として扱ったことを考えると、簡略化のために言い換えを許可しました。↩
-
F. P. Brooks, No Silver Bullet, Refired, The Mythical Man-Month, Essays on Software Engineering, Anniversary Edition, Addison-Wesley 1995, p.213 ↩
-
Ding Yuan et al., Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures in Distributed Data-Intensive Systems, 2014 ↩
-
Juris Hartmanis, Some Observations About the Nature of Computer Science, 1993 ↩