theory - チューリング完全でない言語での停止

Question

停止問題はチューリング完全言語では解決できず、正規表現のように常に停止する一部の非TC言語では簡単に解決できます。

停止する機能と停止しない機能の両方を備えているが、停止するかどうかを判断できるアルゴリズムを認めている言語があるかどうか疑問に思いました。

Answer 1

停止性問題は言語には作用しません。むしろ、マシン（つまりプログラム）に作用します。つまり、特定のプログラムが特定の入力で停止するかどうかを尋ねます。

おそらく、他の計算モデル（あなたが言及している正規表現のように、 プッシュダウンオートマトンのように）でそれを解決できるかどうかを尋ねるつもりでした。

一般に、停止は、有限のリソース（正規表現、または同等に、固定数の状態があり、外部ストレージがない有限オートマトンなど）を持つモデルで検出できます。これは、考えられるすべての構成を列挙し、マシンが同じ構成に2回入るかどうかを確認することで簡単に実現できます（無限ループを示します）。リソースが有限である場合、マシンが停止しない場合に繰り返し構成を確認する必要があるまでの時間に上限を設けることができます。

通常、リソースが無限のモデル（たとえば、無制限のTMやPDA）は停止チェックできませんが、モデルとその未解決の問題を個別に調査するのが最善です。

（すべてのウィキペディアのリンクについては申し訳ありませんが、実際にはこの種の質問には非常に優れたリソースです。）

Answer 2

はい。この種の重要なクラスの 1 つは、プリミティブ再帰関数です。このクラスには、数値で実行できると予想されるすべての基本的なこと (加算、乗算など) と、@adrian が言及したようないくつかの複雑なクラス (正規表現/有限オートマトン、文脈自由文法/プッシュダウン) が含まれています。オートマトン）。ただし、アッカーマン関数など、原始再帰的ではない関数が存在します。

原始的な再帰関数を理解するのは実際にはかなり簡単です。これらは、真の再帰を持たないプログラミング言語で取得できる関数であり (したがって、関数 f は、直接または別の関数 g を呼び出して f などを呼び出すことによって、それ自体を呼び出すことができません)、while ループを持たない関数です。代わりに for ループを制限します。制限付き for ループは、"for i from 1 to r" のようなものです。ここで、r は、プログラムの前半で既に計算されている変数です。また、i は for ループ内で変更できません。このようなプログラミング言語のポイントは、すべてのプログラムが停止することです。

私たちが書くほとんどのプログラムは、実際には原始再帰的です (つまり、そのような言語に翻訳できます)。

Answer 3

簡単に言えば、イエスです。そのような言語は非常に便利です。

数か月前に LtU で議論がありました: http://lambda-the-ultimate.org/node/2846