帰納的可算言語（きのうてきかさんげんご、）は、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。帰納的可算言語には以下の3つの等価な定義がある。全ての正規言語、文脈自由言語、文脈依存言語、帰納言語は帰納的可算言語である。RE とその補問題 co-RE は算術的階層の基盤となっている。帰納的可算言語は以下の操作について閉じている。すなわち、"L" と "P" を2つの帰納的可算言語としたとき、以下の言語も同様に帰納的可算言語である。帰納的可算言語は差集合や補集合の操作については閉じていない。差集合 "L""P" や "L" の補集合は帰納的可算言語となる場合もあるし、ならない場合もある。

出典:wikipedia