なぜプログラムを証明できないのですか？
https://stackoverflow.com/questions/476959
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
数学プログラムのようにコンピュータープログラムを証明できないのはなぜですか？数学的証明は他の証明の上に構築され、それはさらに多くの証明から公理に至るまで構築されます-私たちが自明であると考える真実
コンピュータープログラムは、そのような構造を持たないようです。コンピュータープログラムを作成する場合、以前の実績のある作品をどのように使用してプログラムの真実を示すことができますか？存在しないため、できません。さらに、プログラミングの公理は何ですか？現場の非常に原子的な真実？
上記に対する良い答えはありません。しかし、ソフトウェアは科学ではなく芸術であるため、証明できないようです。ピカソをどのように証明しますか？
解決
証明プログラムです。
プログラムの正式な検証は、巨大の研究分野です。 （たとえば、カーネギーメロンのグループを参照してください。）
多くの複雑なプログラムが検証されています。たとえば、この Haskellで書かれたカーネルを参照してください。
他のヒント
プログラムは絶対に正しいことが証明されます。お粗末なプログラムを証明するのは難しいです。それを合理的にうまく行うには、プログラムを進化させ、手をつないで証明する必要があります。
停止の問題のため、証拠を自動化することはできません。ただし、任意のステートメントまたはステートメントのシーケンスの事後条件と前提条件を手動で証明できます。
Dijsktraのプログラミングの規律を読む必要があります。
その後、Griesのプログラミングの科学を読む必要があります。
その後、プログラムが正しいことを証明する方法がわかります。
不完全さを持ち込んだ人々へのちょっとしたコメント-それはすべての公理系の場合ではなく、十分に強力なものだけです。
言い換えれば、ゲーデルは、それ自体を記述するのに十分強力な公理的システムは必然的に不完全であることを証明した。だからと言って、それが役に立たないというわけではなく、他の人がリンクしているように、プログラムの証明でさまざまな試みが行われています。
二重問題（証明をチェックするプログラムを書く）も非常に興味深い。
実際、証明可能な正しいプログラムを書くことができます。たとえば、Microsoftは Spec＃というC＃言語の拡張機能を作成しました。自動定理証明器が含まれます。 Javaの場合、 ESC / java があります。もっと多くの例があると確信しています。
（編集：明らかにspec＃は開発されていませんが、契約ツールは.NET 4.0の一部になります）
停止問題または不完全性定理は、おそらくプログラムの自動検証を妨げます。もちろんこれは真実ではありません。これらの問題は、単に正しいか間違っていると証明できないプログラムを書くことができることを教えてくれます。それは私たちが 確かに正しいプログラムを構築することを妨げません。
停止の問題は、検証できないプログラムがあることのみを示しています。はるかに興味深い、より実用的な質問は、どのクラスのプログラムを 正式に検証できるかです。おそらく、誰もが気にするすべてのプログラムを（理論的には）検証することができます。 実際には、これまでのところ、非常に小さなプログラムのみが正しいことが証明されています。
このトピックに本当に興味がある場合は、まずこのトピックに関する古典的な入門作品であるDavid Griesの<！> quot; The Science of Programming <！> quot;をお勧めします。
実際には、プログラムがある程度正しいことを証明することは可能です。前提条件と事後条件を記述してから、前提条件を満たしている状態を指定すると、実行後の状態が事後条件を満たしていることを証明できます。
しかし、トリッキーになるのはループです。これらの場合、ループ不変量を見つける必要があり、正しい終了を示すには、各ループの後に残っている可能な最大反復数の上限関数を見つける必要があります。また、ループを繰り返すたびにこれが少なくとも1つ減少することを示す必要があります。
プログラムについてこれをすべて取得したら、証明は機械的です。しかし、残念ながら、ループの不変関数とバインド関数を自動的に導出する方法はありません。小さなループの些細なケースでは人間の直観で十分ですが、現実的には、複雑なプログラムはすぐに手に負えなくなります。
まず、なぜあなたは<！> quot;プログラムを証明できない<！> quot;と言っているのですか？
<！> quot; programs <！> quot;とはどういう意味ですか？とにかく
プログラムでアルゴリズムを意味しているなら、クラスカルのことを知らないのですか？ダイクストラ？ MST？プリムの？バイナリ検索？マージソート？ DP？これらすべてのものには、その動作を記述する数学モデルがあります。
DESCRIBE。数学は、物事の理由を説明せず、単に方法を描くだけです。太陽が明日東に昇ることを証明することはできませんが、過去にそのことを行っていた場所のデータを示すことはできます。
あなたは言った： <！> quot;コンピュータープログラムを作成する場合、過去の実績のある作品をどのように使用してプログラムの真実を示すことができますか？存在しないため<！> quot;
待って？できない？ http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis
お見せできません<！> quot; truth <！> quot;私はあなたに見せることができないほど多くのプログラム<！> quot; truth <！> quot;言語で。どちらも世界の経験的理解の表れです。 <！> quot; truth <！> quot;ではありません。意味のないものをすべて脇に置いて、Mergesortアルゴリズムがリスト上の要素をO（nlogn）パフォーマンスでソートすること、Dijkstraが重み付きグラフで最短パスを見つけること、またはEuclidのアルゴリズムが最も優れていることを数学的に示します。 2つの数値間の公約数。 <！> quot;私のプログラムの真実<！> quot;その最後のケースでは、多分私はあなたに2つの数字の間の最大公約数を見つけるでしょう、あなたは思いませんか？
回帰方程式を使用して、フィボナッチプログラムの動作を説明できます。
今、コンピュータープログラミングは芸術ですか？そうだと思います。数学と同じくらい。
私は数学的な背景から来たわけではないので、私の無知を許しますが、<！> quot;プログラムを証明するために<！> quot;平均？ 何を証明していますか？正しさ？正確さは、プログラムが<！> quot; correct <！> quot;であることを検証する必要がある仕様です。しかし、この仕様は人間によって決定され、この仕様が正しいことをどのように検証しますか？
私の考えでは、プログラムにはバグがあります。なぜなら、人間は本当に欲しいものを表現するのが難しいからです。 代替テキストhttp://www.processdevelopers.com/images/PM_Build_Swing.gif
では、何を証明していますか？注意不足が原因のバグ？
さらに、プログラミングの公理は何ですか？現場の非常に原子的な真実？
契約ベースのプログラミングと呼ばれるコースをTAしました（コースホームページ： http：// www.daimi.au.dk/KBP2/ ）。ここで、コース（および受講した他のコース）から推定できるもの
言語のセマンティクスを正式に（数学的に）定義する必要があります。簡単なプログラミング言語を考えてみましょう。グローバル変数のみ、int、int配列、算術、if-then-else、while、代入、do-nothingを持つもの[おそらく、主流言語のサブセットを<！> quot; implementation <！> quotとして使用できます;この]。
実行状態は、ペアのリスト（変数名、変数の値）です。 <！> quot; {Q1} S1 {Q2} <！> quot;を読んでください。 as <！> quot; execting statement S1は、実行状態Q1から状態Q2 <！> quot;に移動します。
1つの公理は"if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}"になります。つまり、ステートメントS1が状態Q1からQ2に移動し、ステートメントS2がQ2からQ3に移動すると、<！> quot; S1; S2 <！> quot; （S1に続いてS2）、状態Q1から状態Q3に移動します。
別の公理は"if {Q1 && e != 0} S1 {Q2} and {Q1 && e == 0} S2 {Q2}, then {Q1} if e then S1 else S2 {Q2}"です。
今、ちょっとした改良：{}のQnは、実際には状態そのものではなく、状態に関するステートメントです。
M（out、A1、A2）は、2つのソートされた配列をマージし、結果をoutに保存するステートメントであり、次の例で使用するすべての単語が正式に（数学的に）表現されたとします。 "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}"は、Mがマージアルゴリズムを正しく実装しているという主張です。
上記の公理を使用することでこれを証明することができます（おそらく他のいくつかが必要になります。ループが必要になる可能性があります）。
これが、正しいプログラムの証明がどのように見えるかを少し説明することを願っています。そして、私を信じてください。一見単純なアルゴリズムであっても、正しいことを証明するにはたくさんの作業が必要です。私は知っている、私は多くの試みを読んだ;-）
[これを読んだ場合：あなたのハンドインは問題ありませんでした。頭痛を引き起こしたのは他のすべてです;-）]
もちろん、他の人が投稿したように、可能です。
非常に小さなサブルーチンを正しく証明することは、プログラミング関連の学位プログラムのすべての学部生が行うべき 必須 の良い演習です。コードを明確にし、簡単にレビューおよび保守できるようにする方法についての優れた洞察を提供します。
ただし、現実の世界では実際の使用は限られています。
まず、プログラムにバグがあるように、数学的な証明もそうです。数学的な証明が本当に正しく、エラーがないことをどのように証明しますか？できません。また、反例として、公開されている数学的証明の多くには、数年後にエラーが発見されました。
第二に、プログラムが何をすべきかについて明確な定義を「先験的に」持たなければ、プログラムが正しいことを証明することはできません。しかし、プログラムが行うべきことの明確な定義はプログラムです。 （それは、コンパイラを持たない何らかの仕様言語のプログラムかもしれません。）したがって、プログラムが正しいことを証明する前に、まず同等で事前に知られている別のプログラムが必要です。正しいこと。したがって、QEDはすべて無駄です。
古典的な<！> quot; No Silver Bullet <！> quot;を追跡することをお勧めします。ブルックスによる記事。
この分野では多くの研究が行われています。他の人が言ったように、プログラム言語内の構成は複雑であり、特定の入力を検証または証明しようとすると悪化します。
ただし、多くの言語では、どの入力が受け入れられるか（前提条件）を指定でき、最終結果（ポスト条件）を指定することもできます。
このような言語には、B、イベントB、Ada、fortranが含まれます。
そしてもちろん、プログラムに関する特定の特性を証明するのに役立つ多くのツールがあります。たとえば、デッドロックの自由を証明するために、SPINを介してプログラムを処理できます。
論理エラーの検出にも役立つ多くのツールもあります。これは、静的解析（goanna、satabs）またはコードの実際の実行（gnu valgrind？）で実行できます。
ただし、開始（仕様）から実装、展開まで、プログラム全体を実際に証明できるツールはありません。 Bメソッドは近づいていますが、その実装チェックは非常に弱いです。 （それは、人間がspeicficaitonの実装への翻訳において不死身であると仮定します。）
補足として、Bメソッドを使用する場合、小さな公理から複雑な証明を作成することがよくあります。 （そして、他の大げさな定理証明者にも同じことが当てはまります。）
できます。私は大学の新入生としてプログラムの正確性を証明するために何時間も費やしました。
マクロスケールでは実用的ではない理由は、プログラムの証明を書くことはプログラムを書くよりもはるかに難しい傾向があるためです。また、今日のプログラマは、関数やプログラムを書くのではなく、システムを構築する傾向があります。
マイクロスケールでは、個々の機能に対して精神的に行うこともあり、コードを整理して確認しやすくする傾向があります。
スペースシャトルソフトウェアに関する有名な記事があります。彼らは証明、または同等のものを行います。それは信じられないほど費用と時間がかかります。そのレベルの検証が必要な場合もありますが、現在の技術を使用するあらゆる種類の消費者または商用ソフトウェア会社では、19.9％のコストで99.9％のソリューションを提供する競合他社が昼食を食べます。わずかに安定したMS Officeに5000ドルを支払う人はいません。
自信をお探しの場合、プログラムを証明する代わりにテストします。これは理解しやすく、自動化できます。また、上記で説明したように、数学的に証明が不可能なプログラムのクラスも許可します。
何よりも、受け入れテストに合格するための証拠はありません：*
-
プログラムが実際にそれが言うことをするからといって、ユーザーが望んでいることをするというわけではありません。
-
それ以外の場合、それが言うことはユーザーが望むと言うことを証明できます。
- ユーザーが実際に何を望んでいるのかわからないため、本当に欲しいものを証明する必要があります。などReductio ad abdardum。
-
*ユニット、カバレッジ、機能、統合、その他すべての種類のテストは言うまでもありません。
これがあなたのパスに役立つことを願っています。
プログラムを証明できるだけでなく、コンピューターにプルーフからプログラムを構築させることもできます。 Coq を参照してください。そのため、実装を間違えた可能性を心配する必要さえありません。
Godelの定理にもかかわらず...何がポイントになる？なんて単純な<！> quot; truths <！> quot;証明しますか？それらの真実から何を導き出したいですか？私はこれらの言葉を食べるかもしれません...実用性はどこにありますか？
プログラムを証明できます。たとえば、New JerseyのStandard ML（SML / NJ）などの言語で記述すれば、静かで簡単です。
あなたの声明は幅広いので、たくさんの魚を捕まえています。
要点：一部のプログラムは間違いなく正しいことが証明できます。すべてのプログラムが正しいことを 証明することはできません。
これはさっきの簡単な例です。念のため、当時の集合論を破壊したのとまったく同じ種類の証拠です。それ自体が正しいかどうか、それが 正解、不正解。
これはG <！>＃246;デルの定理、単純明快です。
ただし、多くのプログラムを証明できるため、これはそれほど問題ではありません。
純粋に機能的な言語（つまりHaskell）を想定しましょう。このような言語では、副作用を非常に明確に考慮することができます。
プログラムが正しい結果を生成することを証明するには、以下を指定する必要があります：
- データ型と数学セットの対応
- Haskell関数と数学関数の対応
- 他の関数からどの関数を作成できるかを指定する公理のセット、および対応する数学的な側面。
この一連の仕様は、表記法のセマンティクスと呼ばれます。数学を使用したプログラムの理由を証明できます。
良いニュースは、<！> quot;プログラムの構造<！> quot; （上記のポイント3）および<！> quot;数学セットの構造<！> quot;よく似ている（流行語は topos 、またはデカルト閉カテゴリー）ので、1 /数学側で行った証明は、簡単にプログラム構造2 /作成するプログラムは数学的に正しいことが簡単に示されます。
停止の問題（簡単なものを証明することの難しさについて）プログラムが完了するかどうかなど）。基本的に、問題はG <！>＃246; delの不完全性定理に関連しています。
プログラムの一部を証明できます。たとえば、コンパイルが成功した場合、型の安全性を静的に検証および保証するC＃コンパイラ。 しかし、あなたの質問の核心は、プログラムが正しく動作することを証明することだと思います。多くの（あえて言わないが）アルゴリズムは正しいことが証明できますが、次の理由でプログラム全体を静的に証明できない可能性があります。
- 検証では、可能なすべてのブランチ（呼び出し、if、interupts）をトラバースする必要があります。これは、高度なプログラムコードでは非常に複雑な時間の複雑さを持っています（したがって、妥当な時間内に完了しません）。
- コンポーネントの作成またはリフレクションを使用したプログラミング技術によっては、コードの実行を静的に予測することができません（つまり、他のプログラマがライブラリをどのように使用するかわからず、コンパイラはリフレクションの予測が困難です）消費者が機能を呼び出します。
これらはほんの一部です...
プログラムに明確に定義された目的と初期の仮定（Godelを無視...）がある場合、それを証明できます。 6 <！> lt; = x <！> lt; = 10のすべての素数xを見つけると、答えは7であり、それを証明できます。 NIMを再生するプログラム（最初のPythonプログラムゲームはコンピューターが勝てる状態になった後、理論的にはコンピューターが常に勝ちます。私はそれを真であると証明することはできませんでしたが、それは真実です（数学的にはデジタルバイナリサムプルーフによる）コードでエラーを犯さない限り私は信じています。エラーを犯しましたか、まじめに言って、誰かがこのプログラムに勝てるかどうか教えてもらえますか？
<！> quot;実証済み<！> quot;である数学定理がいくつかあります。 4色の定理のようなコンピューターコードを使用します。しかし、あなたが言ったように、あなたはプログラムを証明できるので、異議がありますか？
さらに、プログラミングの公理は何ですか？現場の非常に原子的な真実？
opcodes は<！> quot; atomic truths <！> quot ;?例を見ると...
mov ax,1
...プログラマーは、ハードウェアの問題を除いて、このステートメントを実行した後、CPUのaxレジスタに1？
コンピュータプログラムを作成する場合、以前の実績のある作品をどのように使用してプログラムの真実を示すことができますか？
<！> quot;前の仕事<！> quot;次に、新しいプログラムが実行されるランタイム環境になります。
新しいプログラムは証明できます。正式な証明とは別に、<！> quot;検査で！<！> quot;さまざまな形式の<！> quot; testing <！> quot; （<！> quot;受け入れテスト<！> quot;を含む）。
どのようにしてピカソを証明しますか？
ソフトウェアが芸術よりも工業デザインやエンジニアリングに似ている場合、より良い質問は<！> quot;橋や飛行機をどのように証明しますか？<！> quot;
プログラムが正しいことの証明は、プログラムの仕様に関連してのみ行うことができます。可能ですが、高価/時間がかかります
一部のCASEシステムは、他のシステムよりも証明に適したプログラムを生成しますが、これも仕様の正式なセマンティクスに依存しています...
...では、仕様が正しいことをどのように証明しますか？右！より多くの仕様で！
これについて少し読みましたが、2つの問題があります。
最初に、正確性と呼ばれる抽象的なことを証明することはできません。適切に設定されていれば、2つの正式なシステムが同等であることを証明できます。プログラムが一連の仕様を実装していることを証明できます。これを行うには、証明とプログラムを多少並行して作成するのが最も簡単です。したがって、仕様は、証明するものを提供するために十分に詳細である必要があり、したがって仕様は事実上プログラムです。目的を満たすためにプログラムを作成する問題は、目的を満たすためにプログラムの正式な詳細仕様を作成する問題になります。それは必ずしも前進ではありません。
第二に、プログラムは複雑です。正確性の証明も同様です。プログラムの記述を間違えた場合は、必ず1つ証明してください。ダイクストラとグリスは、本質的に、私が完璧な数学者であれば、優れたプログラマーになることができると言っていました。ここでの価値は、証明とプログラミングが2つの異なる思考プロセスであり、少なくとも私の経験では、さまざまな種類の間違いを犯すことです。
私の経験では、プログラムの証明は無駄ではありません。正式に説明できることをしようとすると、実装が正しいことを証明することで、見つけるのが難しい多くのエラーを排除し、主に愚かなエラーを残します。非常にバグのないコードを生成する必要があるプロジェクトでは、有用な付属物になる可能性があります。すべてのアプリケーションに適しているわけではなく、特効薬でもありません。
他の人が指摘したように、（一部の）プログラムは実際に証明できます。
実際の問題の1つは、証明したい何か（つまり、仮定または定理）が最初に必要なことです。そのため、プログラムについて何かを証明するためには、最初にプログラムが何をすべきかについての正式な説明が必要です（例えば、事前条件と事後条件）。
つまり、プログラムの正式な仕様が必要です。しかし、合理的な（はるかに厳密ではない）仕様を取得することは、すでにソフトウェア開発で最も難しいことの1つです。そのため、（現実の）プログラムについて興味深いことを証明することは一般的に非常に困難です。
しかし、より簡単に定式化できる（そして証明された）ものがいくつかあります。プログラムがクラッシュしないことを少なくとも証明できれば、それはすでに何かです：-）。
ところで、いくつかのコンパイラの警告/エラーは、本質的にプログラムに関する（単純な）証拠です。たとえば、Javaコンパイラは、コード内の初期化されていない変数にアクセスしないことを証明します（そうしないと、コンパイラエラーが発生します）。
すべての答えを読んだわけではありませんが、プログラムの証明方法は無意味です。だから誰もそれをしません。
比較的小規模/中規模のプロジェクト（たとえば、1万行のコード）がある場合、その証明はおそらく、もう1万行にもならないでしょう。
考えてみてください。プログラムにバグがある場合は、プルーフに<！> quot; bugs <！> quot;も含めることができます。たぶん、証明のために証明が必要になるでしょう！
もう1つ考慮すべき点は、プログラムは非常に形式的で正確なことです。プログラムコードは非常に愚かなマシンで実行する必要があるため、これ以上厳密で形式的なものを取得することはできません。
プルーフは人間によって読み取られますが、実際のコードほど厳密ではない傾向があります。
証明したいのは、特定のデータ構造（クイックソート、バイナリツリーへの挿入など）で動作する低レベルアルゴリズムのみです。
これらはやや複雑ですが、なぜ機能するのか、および/または常に機能するのかはすぐにはわかりません。他のすべてのソフトウェアの基本的な構成要素でもあります。
ほとんどの回答は練習に焦点を当てており、それで構いません。実際には、正式な校正は気にしません。しかし、理論的には何ですか？
プログラムは、数学的なステートメントのように証明できます。しかし、あなたが意図した意味ではありません！ 十分な強力なフレームワークには、証明できない数学的ステートメント（およびプログラム）があります！ こちら
をご覧ください。ここではノイズが多いですが、とにかく風に向かって叫ぶつもりです...
<！> quot;正解<！> quot;文脈によって意味が異なります。 フォーマルシステムで、<！> quot;正しいことを証明<！> quot;式は、他の実証済み（または公理的）式から導出できることを意味します。 <！> quot;正しいことを証明する<！> quot;プログラミングでは、コードが正式な仕様と同等であることを示します。しかし、正式な仕様が正しいことをどのように証明しますか？残念なことに、バグがないことや、現実の問題を解決するための仕様をテスト以外に示す方法はありません。
ちょうど2セントで、そこにある興味深いものに追加されます。
証明できないすべてのプログラムの中で、最も一般的なものはIO（世界またはユーザーとの予測不可能な相互作用）を実行するプログラムです。自動化された証明でさえ、<！> quot; proven <！> quot;プログラム<！> quot;モデルで記述されている理想的なハードウェアではなく、いくつかの物理ハードウェアで実行します。
反対に、数学の証明は世界の大部分を気にしません。 Mathsでよくある質問は、それが現実のものを説明するかどうかです。虚数や非ユークリッド空間のような新しいものが発明されるたびに発生します。これらの新しい理論は非常に優れたツールであるため、質問は忘れられます。良いプログラムのように、それはただ動きます。
