再帰的に決定可能な言語、無限の言語の受け入れ

Question

再帰的に決定可能な言語は、その言語の入力wが与えられたときにチューリングマシンを構築できる言語であり、チューリングマシンは常に受け入れ、停止または拒否する停止します。私が混乱しているのは無限に成長する言語です。たとえば、L = {0^p | pは素数です}。したがって、数が線形空間で素数であるかどうかを決定するアルゴリズムを書くことができます。だから私の理解は、このアルゴリズムは素数であるか、素数ではないことを知らせるので、Lは再帰的に決定可能でなければなりません。しかし、pは固定数に束縛されていないので、無限大に行くことができますか？だから私のアルゴリズムは、入力を受け入れたり拒否したりせずに、技術的に永遠に実行できると仮定するのは正しいですか？その場合、私たちのLは再帰的に決定可能でなく、再帰的に列挙できますか？

Answer 1

1. はい、素数の単語の言語は決定可能です。あなたが述べたように、これは入力の大きさに応じて線形空間で行うことさえできます。
2. はい、言語には任意の長さの単語が含まれています。しかし、pが無限に行くということは誤解を招きます。可能なすべての整数値を取りますが、順序はありません。無限大は整数ではなく、設定された定義に順序がないので、無限に近づく傾向はありません。
3. いいえ、アルゴリズムが永遠に実行されるとは想定できません。すべての文字列を入力として受け取るのではなく、1つだけを入力します。そして、すべての単一の文字列は有限の長さを持つので、アルゴリズムはそれらの文字列のたびに終了します。無限に多くの可能な入力があるという事実は、ここでは関係ありません。