recursion - 再帰的に列挙可能なセットとは

Question

このトピックに関するウィキペディアの記事に関しては、多くの議論(および混乱) があるようです。Google がスローするその他の結果は、無料で一般に使用することはできません。

皆さんの意見に興味があります。

Answer 1

1 つの定義を次に示します。再帰的に列挙可能なセットとは、セット内の各要素を出力するプログラムを記述できるセットです: E1、E2、E3... このプログラムが停止しなくても問題ありません。

人々は通常、これについて言語の文脈で話します。再帰的に列挙可能な言語は、その言語のすべての有効な文字列を書き出すプログラムを作成できる言語です。言語は文字列の集合にすぎないため、「基数 10 のすべての素数の集合」は有効な言語です。

ただし、言語内のすべての文字列やセット内のすべての要素を生成したくない場合を想像してください。特定の文字列が言語に含まれているかどうかを確認したいだけです。問題は、文字列が自分の言語ではないことを確実に知ることができないことです。この言語用のコンパイラを作成する必要がある場合、コンパイラは有効な入力に対しては問題なく動作しますが、入力が無効な場合、存在しないものを無限リストから検索するため、コンパイラが永久にハングアップします。

「再帰言語」または「再帰セット」のセットは、指定された入力がセット内にあるかどうかを通知するプログラムを作成できるセットです。すべての文字列を列挙し、それがセット内にある場合はそれを出力できるため、すべての再帰言語も再帰的に列挙可能です。再帰言語は、要素が含まれているかどうかを確実に判断できるため、決定可能とも呼ばれます。これは、より一般的な再帰的に列挙可能なセットには当てはまりません。

一般に、セットまたは言語が再帰的に列挙可能であるか再帰的であることを証明するのは簡単ですが、再帰的ではなく再帰的に列挙可能であることを証明するのは困難です。

Answer 2

再帰的に列挙可能なセットは、要素がセットに含まれているかどうかを決定するための部分的に計算可能なアルゴリズムがあるセットです (計算は可能ですが、必ずしも終了するわけではありません)。

たとえば、アイテムが mandlebrot セットにないかどうかの判断は、再帰的に列挙可能です。