帰納的集合
 | この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年8月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
指示関数が帰納的関数となるような集合を帰納的集合（きのうてきしゅうごう）という。
端的に言えば、決定可能な集合であり、チャーチのテーゼを認めるならば、計算可能な集合である。
たとえば、素数の集合は、帰納的集合である。一方で停止性問題（実行すると停止するプログラムと入力の組の集合）は帰納的でない。
| この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年8月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
指示関数が帰納的関数となるような集合を帰納的集合（きのうてきしゅうごう）という。
端的に言えば、決定可能な集合であり、チャーチのテーゼを認めるならば、計算可能な集合である。
たとえば、素数の集合は、帰納的集合である。一方で停止性問題（実行すると停止するプログラムと入力の組の集合）は帰納的でない。