什麽是語言？語言是壹組字符串，屬於這組字符串的字符串就是這種語言的例子。比如“我今天喝了”是壹串，肯定屬於漢語的集合，所以“我今天喝了”是漢語。字符串“今天喝我”肯定不屬於漢語的集合，因為它不符合漢語語法。
圖靈機對語言的識別意味著給定壹個字符串，圖靈機必須決定這個字符串是否屬於壹組特定的語言。例如，識別中文的圖靈機（如果存在的話）必須能夠判斷“我今天喝酒了”和“我今天喝酒了”是否是中文。
因此，圖靈機可以識別某種語言，即圖靈機可以確定某個字符串是否屬於該語言。
最常見的上下文無關語法語言實際上可以被自動機識別，當然圖靈機也可以識別。使用喬姆斯基語法給出的語言，很容易構建壹個解析器來識別這種語言。這裏有壹種自動機無法識別但圖靈機可以識別的語言:
"00 ...011 ...1”，其中零的數量與1的數量相同。
這種語言自動機無法識別，但圖靈機可以。為什麽？妳可以很容易地構造壹個遞歸函數來識別語言。眾所周知，壹般遞歸函數相當於圖靈機。