帰納的可算言語
帰納的可算言語には以下の3つの等価な定義がある。
帰納的可算言語は、形式言語のアルファベットから生成可能な全ての単語の集合のうち、帰納的可算な部分集合である。
帰納的可算言語は、その言語に含まれる全文字列を数え上げるチューリング機械(または計算可能関数)が存在する形式言語である。言語が無限である場合、同じ文字列が現れないようなアルゴリズムが必要である。すなわち、n 番目の文字列が以前に出現しているかどうかを判定し、もし既出であったら n+1 番目の文字列を代わりに出力する。ただし、その n+1 番目の文字列も既出でないか確認が必要である。
帰納的可算言語は、入力された文字列がその言語に含まれる場合にそれを受理して停止するチューリング機械(または計算可能関数)が存在する形式言語である。ただし、入力された文字列がその言語に含まれない場合、停止して拒絶するかもしれないし、無限ループするかもしれない。帰納言語は常にチューリング機械が停止する点が異なる。
全ての正規言語、文脈自由言語、文脈依存言語、帰納言語は帰納的可算言語である。
RE とその補問題 co-RE は算術的階層の基盤となっている。