帰納的可算言語

ウィキペディア

帰納的可算言語

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/04/29 04:58 UTC 版)

帰納的可算言語（きのうてきかさんげんご、英: Recursively enumerable language）は、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。