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

Question

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

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

Answer 1

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

実際には、プリミティブな再帰関数を理解するのは非常に簡単です。これらは、真の再帰のないプログラミング言語で取得できる関数です（そのため、関数fは、直接、またはfを呼び出す別の関数gを呼び出しても、それ自体を呼び出すことはできません）、whileループはありません。代わりに、forループの境界があります。有界forループは、<！> quot; for i from 1 to r <！> quot;のようなものです。ここで、rはプログラム内ですでに計算されている変数です。また、forループ内でiを変更することはできません。このようなプログラミング言語のポイントは、すべてのプログラムが停止することです。

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

Answer 2

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

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

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

通常、無限のリソース（たとえば、無制限のTMおよびPDA）を持つモデル、 停止チェックはできませんが、モデルを調査し、 個々の未解決の問題。

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

Answer 3

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

LtUで数ヶ月前にそれについての議論がありました： http://lambda-the-ultimate.org/node/2846