現場で停止の問題に個人的に遭遇したのはいつですか? これは、同僚や上司が計算の根本的な限界に違反する解決策を提案したとき、または解決しようとしていた問題が実際には解決できないことに気付いたときです。
私が最近それを思いついたのは、型チェッカーを研究していたときでした。私たちのクラスは、完全な型チェッカー (型エラーなしで実行されるすべてのプログラムを受け入れ、型エラーで実行されるすべてのプログラムを拒否するもの) を書くことは不可能であることに気付きました。 . もう1つは、同じクラスで、型チェック段階でゼロによる除算が発生するかどうかを判断することは不可能であることに気付いたときです。実行時に数値がゼロであるかどうかをチェックすることも停止問題のバージョン。
「ホストが永久にダウンしているかどうかを判断するための監視プラグインを作成する」のように、文字通り停止の問題が割り当てられました。真剣に？では、しきい値を設定します。「いいえ、後で再発するかもしれないから」
多くの理論的な説明が続きました。
数年前、Basic Infinite Loop FinderまたはBILFと呼ばれる製品のレビュー（Byteマガジンで）を読んだことを覚えています。BILFは、Microsoft Basicのソースコードをスキャンして、終了しなかったループを見つけることになっています。コード内の無限ループを見つけることができると主張しました。
レビューアは、そのプログラムがすべての場合に機能するためには、停止性問題を解決する必要があり、すべての場合に機能しなかった理由の数学的証明を提供するまでに至ったことを指摘するのに十分な知識がありました。
次号では、次のリリースで問題が修正されることを説明する会社の代表者からの手紙を発表しました。
更新： imgurに関する記事の画像に出くわしました。間違った雑誌を思い出しました。それは、バイトではなく、クリエイティブコンピューティングでした。そうでなければ、それは私がそれを覚えていたのとほとんど同じです。
あなたはそれの高解像度バージョンをimgurで見ることができます。
私が現在取り組んでいるプロジェクトには、決定的な問題があちこちにあります。これは単体テスト ジェネレーターであるため、一般に、「このプログラムは何をするのか」という質問に答えることを達成しようとします。これは停止問題の例です。開発中に発生したもう1つの問題は、「2つの（テスト）機能が同じである」ということですか？または、「これらの 2 つの呼び出し (アサーション) の順序は重要ですか」 ?
このプロジェクトの興味深い点は、すべての状況でこれらの質問に答えることができない場合でも、問題を 90% の確率で解決するスマートなソリューションを見つけることができることです。これは、このドメインにとって実際には非常に優れています。
コンパイラー/インタープリターの最適化、静的コード分析ツール、さらにはリファクタリング・ツールなど、他のコードについて推論しようとする他のツールは、停止問題にヒットする可能性があります (したがって、回避策を見つけることを余儀なくされます)。
例1.レポートのページ数はいくつですか。
プログラムを学んでいたとき、データからきれいなレポートを印刷するツールを作って遊んでいました。明らかに、私はそれが本当に柔軟で強力であることを望んでいたので、すべてのレポートジェネレーターを終了するのはレポートジェネレーターになるでしょう。
レポートの定義は非常に柔軟であるため、チューリング完全でした。変数を調べたり、選択肢から選択したり、ループを使用して繰り返したりすることができます。
レポートインスタンスのページ数である組み込み変数Nを定義したので、各ページに「Nのページn」という文字列を配置できます。2つのパスを実行しました。最初のパスはページをカウントし（Nがゼロに設定されている間）、2番目のパスは最初のパスから取得したNを使用して実際にページを生成しました。
最初のパスでNが計算され、次に2番目のパスで異なるページ数が生成される場合があります（ゼロ以外のNは、レポートの動作を変更するため）。Nが落ち着くまでパスを繰り返してみました。それで、落ち着かなかったらどうなるので、これは絶望的だと気づきました。
これにより、「レポートが生成するページ数の安定した値が反復で確定しない場合は、少なくともユーザーを検出して警告できますか？」という質問につながります。幸いなことに、この時までに私はチューリング、ゲーデル、計算可能性などについて読むことに興味を持ち、つながりを築きました。
数年後、MSAccessが「6/5ページ」を印刷することがあることに気づきました。これは本当に素晴らしいことです。
例2：C++コンパイラ
コンパイルプロセスには、テンプレートの拡張が含まれます。テンプレート定義は、複数の専門分野（「条件」として機能するのに十分）から選択でき、再帰的にも使用できます。つまり、これはチューリング完全（純粋な関数型）メタシステムであり、テンプレート定義は言語であり、型は値であり、コンパイラーは実際にはインタープリターです。これは事故でした。
したがって、特定のC ++プログラムを調べて、プログラムのコンパイルが成功したときにコンパイラが原則として終了できるかどうかを判断することはできません。
コンパイラベンダーは、テンプレート再帰のスタック深度を制限することでこれを回避します。深さはg++で調整できます。
何ヶ月も前、私は、金属部品のバスケットを 1500 度の高炉に出し入れするための非常に複雑なレール システムを実装していた当社のコンサルタントを支援していました。線路自体は、製造現場にあるかなり複雑な「ミニ鉄道車両基地」で、いくつかの場所で交差していました。いくつかの電動パレットは、スケジュールに従って部品のバスケットを往復します。炉のドアが開いている時間をできるだけ短くすることが非常に重要でした。
プラントはフル稼働状態だったため、コンサルタントはソフトウェアを「リアルタイム」で実行してスケジューリング アルゴリズムをテストすることができませんでした。代わりに、彼はきれいでグラフィックのようなシミュレーターを書きました。仮想パレットが彼の画面上のトラック レイアウト上を動き回るのを見ながら、私は「スケジュールの競合があるかどうかをどのように知ることができますか?」と尋ねました。
彼の素早い答えは、「簡単です。シミュレーションは決して停止しません。」
洗練された静的コード分析により、停止の問題が発生する可能性があります。
たとえば、コードの一部が範囲外の配列インデックスに決してアクセスしないことを Java 仮想マシンが証明できる場合、そのチェックを省略してより高速に実行できます。一部のコードでは、これが可能です。より複雑になると、停止の問題になります。
これは、GPU アプリケーションのシェーダーでは依然として問題です。シェーダーに無限ループ (または非常に長い計算) がある場合、ドライバーは (一定の制限時間後に) 停止するか、フラグメントを強制終了するか、またはそのまま実行する必要がありますか? ゲームやその他の商業的なものでは、おそらく前者が必要ですが、科学/GPU コンピューティングでは後者が必要です。さらに悪いことに、Windows の一部のバージョンでは、グラフィックス ドライバーがしばらく応答していないため強制終了すると想定し、GPU で計算を行うときに計算能力を人為的に制限します。
ドライバーがどのように動作するか、またはタイムアウトなどを設定する方法を制御するアプリケーション用の API はありません。また、シェーダーが終了するかどうかをドライバーが判断する方法はまったくありません。
この状況が最近改善されたかどうかはわかりませんが、知りたいです。
これの別の一般的なバージョンは、「マルチスレッド コードのデッドロックを排除する必要がある」というものです。管理の観点からは完全に合理的な要求ですが、一般的なケースでデッドロックを防ぐために、ソフトウェアが陥る可能性のあるすべてのロック状態を分析する必要があります。これは当然のことながら、停止の問題に相当します。
複雑なシステムのデッドロックを部分的に「解決」する方法は、ロックの上に別のレイヤーを課すことによって (定義された取得順序のように) ありますが、これらの方法が常に適用できるとは限りません。
これが停止問題と同等である理由:
A と B の 2 つのロックと、X と Y の 2 つのスレッドがあるとします。スレッド X にロック A があり、ロック B も必要とし、スレッド Y にロック B があり、ロック A も必要な場合、デッドロックが発生します。
X と Y の両方が A と B の両方にアクセスできる場合、悪い状態に陥らないようにする唯一の方法は、各スレッドがコードを通過できる可能性のあるすべてのパスと、その順序を決定することです。これらすべてのケースでロックを取得して保持できます。次に、2 つのスレッドが異なる順序で複数のロックを取得できるかどうかを判断します。
ただし、各スレッドがコードを介してたどることができるすべての可能なパスを決定することは、(一般的なケースでは) 停止問題と同じです。
Perl のテスト システムは、テスト カウンターを維持します。実行するテストの数をプログラムの先頭に置くか、追跡しないことを宣言します。これは、テストが途中で終了するのを防ぎますが、他のガードがあるため、それほど重要ではありません。
ときどき、誰かがテストの数をカウントするプログラムを作成しようとします。もちろん、これは単純なループによって無効になります。彼らはとにかく前進し、ループを検出して試行し、反復回数を推測して停止問題を解決するために、ますます精巧なトリックを実行します。通常、彼らはそれが「十分に良い」ものでなければならないと宣言します。
私はかつてATM（現金自動預け払い機）ドメインで統合プロジェクトに取り組んでいました。クライアントは、私のシステムで受信されなかった国のスイッチによって送信されたトランザクションについて、私のシステムからレポートを生成するように要求しました!!
バークレーの論文を見つけました: Looper: Lightweight Detection of Infinite Loops at Runtime http://www.eecs.berkeley.edu/~jburnim/pubs/BurnimJalbertStergiouSen-ASE09.pdf
ほとんどの無限ループは些細なエラーであるため、LOOPER が役立つ場合があります。ただし、この論文では停止の問題については触れていません。
彼らは自分たちの限界について何と言っていますか?
[LOOPER] 通常、非終了がすべてのループ反復におけるヒープの変更の詳細に依存するループについて推論することはできません。これは、シンボリック実行がポインターの具体化において保守的であり、シンボリック推論が十分に強力ではないためです。私たちの技術を形状解析とより強力な不変式の生成と証明と組み合わせることは、価値のある将来の仕事になると信じています。
つまり、「問題は次のリリースで修正される」ということです。
（Eclipse）Visual Editorの機能概要から：
Eclipse Visual Editor (VE) を使用して、任意の.java ファイルを開くことができます。次に、ビジュアル Bean を探して Java ソース コードを解析します。...
一部のビジュアル編集ツールは、その特定のビジュアル ツール自体が生成したコードのビジュアル モデルのみを提供します。その後、ソース コードを直接編集すると、ビジュアル ツールがコードを解析してモデルを構築できなくなる可能性があります。
ただし、Eclipse VE は、GUI を最初から編集するために使用することも、「ハードコード」された Java ファイルや別のビジュアル ツールでビルドされた Java ファイルから編集することもできます。ソース ファイルは、グラフィカル ビューア、JavaBeans ツリー、またはプロパティ ビューを使用して更新するか、ソース エディタで直接編集することができます。
たぶん、今のところマティスに固執する必要があります。
関係ありませんが、 Eclipse 内で停止する問題について尋ねている人がいます。
公平を期すために言うと、VE のドメインは非常に限定されており、リフレクションなどのトリッキーなことに夢中になることはおそらくないでしょう。それでも、任意のJava ファイルから GUI を構築するという主張は停止しているように見えます。
「あなたのコードに 100% バグがないことをどのように保証できますか?」