圖靈可識別語言

圖靈可識別語言，又可被稱為遞歸可枚舉語言或遞迴可枚舉語言。一個語言是圖靈可識別語言若且唯若它是遞歸可枚舉語言。

定義

圖靈可識別語言又可被稱為遞歸可枚舉語言或遞迴可枚舉語言。設 M 是一台圖靈機，若在輸入串 ω 上 M 運行後可進入接受狀態並停機，則稱 M 接受串 ω。M 所接受的所有字元串的集合稱為 M 所識別的語言，簡稱 M 的語言，記作 L(M)。
設S是一個語言，若存在圖靈機 M 使得 L(M) = S，則稱圖靈機 M 識別 S，且 S 稱為圖靈可識別語言。
一個語言是圖靈可識別語言若且唯若它是遞歸可枚舉語言。

相關條目

語言 文學圖靈機