問題理論の停止対練習

Question

停止問題が解決できないことが多い。そしてそれは確かに些細なことを証明します。

しかし、それは任意のプログラムにのみ適用されます。

プログラムのクラスに関する研究がありましたか人間は通常？

プログラムを分析し、その自由度をすべて列挙し、停止すると結論付けることができます。

たとえば、停止を保証するプログラミング言語（本当にスクリプティング）を作成するための努力がありましたか？それは広く適用されることはありませんが、ミッションクリティカルモジュールにはまだ役に立つかもしれません。

Answer 1

停止することが保証されている言語は広いスプレッド使用を見ました。 COQ / AGDA / IDRIのような言語はすべてこのカテゴリにあります。多くの種類のシステムは、実際にはシステムFやその変種のいずれかなどの停止を保証することができます。すべてのプログラムが正規化することを証明するために煮るタイプシステムの健全性が一般的です。強い正規化は、プログラミング言語研究において一般的に非常に望ましい財産です。

私は実際には無限ループを捕まえることで多くの成功を見ていません。 Euclidのアルゴリズムは、原始的な再帰的であることがわかりやすくないプリミティブ再帰関数の有名な例です。それは単に減少したパラメータ（または胎児終端チェッカーのようないくつかの簡単なパラメータ）を見るために単にチェッカーに失敗します。これを実装するには、本質的に関数内のパラメータとしてアルゴリズムの終了の証明をエンコードする必要があります。

私は私の頭の上から手続き言語の結果を考えることはできません、そして、機能言語のほとんどの結果は、より多くのことを確実にするためにある種の複雑な分析を実行しようとするのではなく、明らかに終了するいくつかの種類の制限を使用しています。自然プログラムは終了します。

Answer 2

これについて過去と現在の研究があります。そのような問題は、終了分析、およびグーグルのクイックルック（Scholar）がいくつか古いものを提供しています。これに関する新しい出版物と同じように：

1. 2005年、 の高次関数プログラムの終了分析の;
2. 2006、 Haskell の自動停止分析/ a>;
3. 2008、 依存関係に基づく論理プログラムの終了解析グラフ ;
4. 2010、 ループの要約と終了分析 ;
5. 2014、 終端プログラムによる終了解析 ;
6. 2015、 refollow noreferrer"> 終端解析 ;
7. 2019、 nofollow noreferrer">イベント駆動型分散アルゴリズムの静的終端解析 < / a>;
8. 2019、 量子プログラミングに関する終端分析の実装 ;
のような内蔵メカニズムを持つ既存の言語を含む
• mercury ;
• IDRIS、COQ、AGDA;

Answer 3

Microsoft has developed a practical code checker (whose name escapes me at the moment) which performs halt-testing. It exploits the fact that the code it checks is human-written and not arbitrary, just as you suggest. More importantly, it bypasses the impossibility proof by being allowed to return the answer 'Cannot decide' if it runs into code too difficult to check.

Answer 4

There are only 2 types of infinite programs:

1. Those that repeat their own state after a point (cyclical)
2. Those that grow indefinitely in used memory

Those in 1st type, follow this pattern:

Where there is a pair of distinct indices i and j such that xi = xj, and after which the cycle repeats itself again (thanks to the deterministic nature of programs). In this case the inputs x, contain the whole memory and variables used by the algorithm, plus the current instruction pointer.

Cycle detection algorithms work very well in practice for this type and can prove that a given cyclical program will never finish, usually after a small number of steps, for most random programs.

Proving those in the 2nd type is where the challenge is. One could argue that type 2 can never exist in reality (as all computers have finite memory) but that is not very useful in practice because the memory used may grow very slowly for a regular computer to ever be full. A simple example of that is a binary counter that never stops and never repeats its full state completely.

Answer 5

There is a huge class of functions that are trivially guaranteed to halt: Everything with a finite number of loops, with an upper limit for the number of iterations for each loop determined before the loop is started.

If you have a random program, it can be difficult to prove whether or not it halts. Programs that are written for a purpose are usually much easier.

Answer 6

The smart contracts functions in the Ethereum blockchain are an example of a system that needs the guarantee of halting, not to stall the whole chain.

Every function has a gas cost, and the gas cost translates into real Ethereum coins. A transaction fee must be paid to call the contract. If the gas used in the contract exceed the gas paid with the transaction fee, the computation terminates immediately.