フィールドで停止する問題に出くわしたのはいつですか？ [閉まっている]

StackOverflow https://stackoverflow.com/questions/235984

質問

停止の問題 現場で？これは、同僚/上司が計算の基本的な制限に違反する解決策を提案したとき、または解決しようとしている問題が実際には解決不可能であることに気付いたときです。

最近思いついたのは、型チェッカーを勉強したときでした。私たちのクラスは、完璧な型チェッカー（型エラーなしで実行されるすべてのプログラムを受け入れ、型エラーで実行されるすべてのプログラムを拒否するもの）を書くことは不可能だと認識しました。 。もう1つは、同じクラスで、型検査段階で除算がゼロになるかどうかを判断することは不可能であることに気づいたときでした。停止する問題のバージョン。

役に立ちましたか？

解決

I literally は、「ホストが永続的にダウンしているかどうかを判断するためのモニタープラグインを作成する」など、停止の問題を割り当てられました。マジ？ OK、それで私はそれに閾値を与えます。 「いいえ、後で戻ってくる可能性があるためです。」

多くの理論的説明が続いた。

他のヒント

数年前、私はBasic Infinite Loop FinderまたはBILFと呼ばれる製品のレビュー（Byte誌で）を読んだことを覚えています。 BILFは、Microsoft Basicソースコードをスキャンし、終了しなかったループを見つけることになっています。コード内の無限ループを見つけることができると主張しました。

レビュアーは、そのプログラムがすべての場合に機能するためには、停止の問題を解決する必要があることを指摘するのに十分に精通しており、すべての場合に機能しない理由の数学的証明を提供するまでに行きました。

次の号で、彼らは問題が次のリリースで修正されるであろうことを説明する会社の代表者からの手紙を発行しました。

更新： imgurに関する記事の画像を見つけました。間違った雑誌を思い出しました。 ByteではなくCreative Computingでした。そうでなければ、それは私がそれを思い出したようにほとんどです。

imgur で高解像度版を見ることができます。

ここに画像の説明を入力 ここに画像の説明を入力

現在取り組んでいるプロジェクトには、決定できない問題があります。単体テストジェネレーターなので、一般的に達成しようとするのは、質問＆quot;このプログラムの機能＆quot; に答えることです。これは停止する問題のインスタンスです。開発中に発生した別の問題は、＆quot; 2つの（テスト）関数が同じであるということです＆quot; ？または、＆quot;これら2つの呼び出し（アサーション）の順序は重要ですか？？

このプロジェクトの興味深い点は、すべての状況でこれらの質問に答えることができない場合でも、 問題を解決するスマートなソリューションを見つけることができるということです。このドメインでは実際に非常に良い時間です。

コンパイラ/インタープリターの最適化、静的コード分析ツール、リファクタリングツールなど、他のコードについて推論しようとする他のツールは、停止問題にぶつかります（したがって、回避策を見つけることを余儀なくされます）。

例1.レポートのページ数

プログラミングを学んでいたとき、データからきれいなレポートを印刷するツールを作成して遊んでいました。明らかに、すべてのレポートジェネレーターを終了するレポートジェネレーターになるように、本当に柔軟で強力なものにしたかったのです。

レポートの定義は非常に柔軟であるため、チューリングが完了しました。変数を見て、選択肢を選択し、ループを使用して物事を繰り返すことができます。

レポートインスタンス内のページ数である組み込み変数Nを定義したので、「page n of N」という文字列を挿入できます。各ページ。 2つのパスを行いました。最初のパスはページをカウントするため（Nはゼロに設定されています）、2番目は最初のパスから取得したNを使用して実際にページを生成します。

最初のパスでNが計算され、2番目のパスで異なるページ数が生成される場合があります（非ゼロのNによりレポートの処理が変更されるため）。 Nが落ち着くまで、パスを繰り返してみました。落ち着かないとどうなるのでしょうか？

次に、「レポートが生成するページ数の反復値が安定した値に落ち着かない場合、少なくともユーザーを検出して警告できますか？」という質問が表示されます。幸いなことに、私はチューリング、ゲーデル、計算可能性などについて読むことに興味を持ち、つながりを作りました。

数年後、私はMS Accessが時々「Page 6 of 5」を印刷することに気付きました。これは本当に素晴らしいことです。

例2：C ++コンパイラ

コンパイルプロセスには、テンプレートの展開が含まれます。テンプレート定義は、複数の専門分野（「条件」として機能するのに十分なもの）から選択でき、再帰的でもあります。したがって、テンプレート定義が言語であり、型が値であり、コンパイラーが実際にインタープリターである、チューリング完全な（純粋に機能的な）メタシステムです。これは事故でした。

その結果、特定のC ++プログラムを調べて、プログラムの正常なコンパイルでコンパイラが原則として終了できるかどうかを判断することはできません。

コンパイラベンダーは、テンプレートの再帰のスタックの深さを制限することでこれを回避します。深さはg ++で調整できます。

多くの月前、私は金属部品のバスケットを1500度の高炉に出し入れする非常に複雑なレールシステムを実装していた会社のコンサルタントを支援していました。線路自体は、製造現場のかなり複雑な「ミニレールヤード」であり、いくつかの場所で交差していました。いくつかの電動パレットが、スケジュールに従って部品のバスケットを往復させます。炉のドアができるだけ短時間開いていることが非常に重要でした。

工場がフル稼働していたため、コンサルタントは自分のソフトウェアを「リアルタイム」で実行してスケジューリングアルゴリズムをテストすることができませんでした。代わりに、彼はきれいなグラフィックyシミュレータを作成しました。仮想パレットが画面上のトラックレイアウト上を移動するのを見て、「スケジュールの競合があるかどうかをどのように知ることができますか」

彼の簡単な答え、「簡単-シミュレーションは停止しません。」

洗練された静的コード分析は、停止問題に遭遇する可能性があります。

たとえば、Java仮想マシンがコードの一部が範囲外の配列インデックスに決してアクセスしないことを証明できる場合、そのチェックを省略してより高速に実行できます。一部のコードではこれが可能です。より複雑になると、それは停止する問題になります。

これは、GPUアプリケーションのシェーダーの問題です。シェーダーに無限ループ（または非常に長い計算）がある場合、ドライバーは（ある時間制限の後）それを停止するか、フラグメントを強制終了するか、単に実行させますか？ゲームやその他の商用のものについては、おそらく前者が望みのものですが、科学/ GPUコンピューティングについては、後者が望みのものです。さらに悪いことに、Windowsの一部のバージョンは、グラフィックスドライバーがしばらく応答しないため、それを強制終了することを前提としています。

ドライバーがどのように動作するか、タイムアウトなどを設定するかを制御するアプリケーション用のAPIはありません。また、シェーダーが終了するかどうかをドライバーが確認する方法は確かにありません。

この状況が最近改善されたかどうかはわかりませんが、知りたいです。

これの別の一般的なバージョンは、「マルチスレッドコードのデッドロックを排除する必要がある」です。管理の観点からは完全に合理的な要求ですが、一般的なケースでデッドロックを防ぐには、ソフトウェアが侵入する可能性のあるすべてのロック状態を分析する必要があります。これは、停止問題に相当することです。 / p>

部分的に「解決」する方法があります。複雑なシステムでは、ロックの上に別の層を課すことでデッドロックが発生します（定義された取得順序など）。これらの方法は常に適用できるわけではありません。

これが停止の問題と同等である理由：

AとBの2つのロックとXとYの2つのスレッドがあるとします。スレッドXにロックAがあり、ロックBも必要であり、スレッドYにロックBがあり、Aも必要な場合、デッドロックが発生します。

XとYの両方がAとBの両方にアクセスできる場合、悪い状態に陥らないようにする唯一の方法は、各スレッドがコードを通過できるすべての可能なパスと順序を決定することですこれらのすべての場合にロックを取得して保持することができます。次に、2つのスレッドが異なる順序で複数のロックを取得できるかどうかを判断します。

しかし、各スレッドがコードを通過できるすべての可能なパスを決定することは、（一般的な場合）停止の問題と同等です。

Perlのテストシステムは、テストカウンターを保持しています。実行するテストの数をプログラムの先頭に置くか、追跡しないことを宣言します。テストが途中で終了するのを防ぐためのガードですが、他にもガードがあるため、それほど重要ではありません。

たまに誰かがあなたのためにテストの数を数えるプログラムを書き込もうとします。もちろん、これは単純なループによって打ち負かされます。彼らはとにかく先を進んで、ループを検出して試行回数を推測し、停止する問題を解決するために、ますます手の込んだトリックを実行します。通常、彼らはそれが「十分」である必要があることを宣言します。

これは特に手の込んだ例です

かつて、ATM（Automated Teller Machines）ドメインで統合プロジェクトに取り組んでいました。クライアントは、システムから受信されなかった国別スイッチによって送信されたトランザクションについて、システムからレポートを生成するように要求しました!!

バークレーの論文を見つけました：ルーパー：実行時の無限ループの軽量検出 http://www.eecs.berkeley.edu/~jburnim/pubs /BurnimJalbertStergiouSen-ASE09.pdf

LOOPERは、ほとんどの無限ループが些細なエラーであるため便利です。ただし、この論文では、停止の問題についても言及していません！

制限について彼らは何と言いますか？

  

[LOOPER]は通常、非終了のループについて推論できません。   すべてのループ反復でのヒープ変異の詳細に依存します。   これは、シンボリック実行が保守的であるためです。   ポインタを具体化し、シンボリックな推論が不十分   パワフル。 当社の技術と形状分析を組み合わせることを信じています   より強力な不変式の生成と証明が価値がある   将来の作業。

つまり、「問題は次のリリースで修正される」という。

（Eclipse）Visual Editorの機能概要から：

  

Eclipse Visual Editor（VE）は    任意の .javaファイルを開くために使用されます。それから   Javaソースコードを解析します   ビジュアルBean用。 ...

     

一部のビジュアル編集ツールは   コードの視覚モデルを提供します   その特定の視覚ツール自体が持っている   生成されました。その後の直接編集   ソースコードの   コードの解析から視覚的なツールと   モデルの構築。

     

Eclipse VE、しかし...   GUIをゼロから編集するために使用される、または   されているJavaファイルから   「ハードコード」または別の   視覚ツール。ソースファイルは   グラフィカルを使用して更新するか、   ビューア、JavaBeansツリーまたはプロパティ   表示するか、直接編集することができます   ソースエディタ。

たぶん今はマティスに固執すべきでしょう。

無関係、ここに誰かを求める Eclipse内の停止問題。

公平を期すために、VEのドメインは非常に限定されており、おそらくリフレクションのようなトリッキーなことに夢中になることはないでしょう。それでも、 任意の javaファイルからGUIを構築するという主張は、まるで停止しているように見えます。

＆quot;コードにバグがないことをどのように保証できますか？＆quot;

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top