首先，什麽叫做圖靈機識別語言？並不是把壹個文件輸入到圖靈機裏就叫做圖靈機識別這種語言。大家都知道圖靈機是壹種計算機器，輸入壹個字符串，可能進入接受狀態、拒絕狀態或者永不停機。 設M是壹臺圖靈機 ，若在輸入串S 上 M 運行後可進入接受狀態並停機，則稱 M 接受串S。M 所接受的所有字符串的集合稱為M所識別的語言，簡稱M的語言，記作 L(M)。 請註意，語言L如果是圖靈機M所識別的語言，則L中的字符串輸入M，M將停機並進入接受狀態。如果不是L中的字符串輸入M，會是什麽結果？只能有兩種情況：M停機並進入拒絕狀態，或者M不停機。 用圖靈機解決的問題都是計算問題，就是壹個有已知求未知的問題。妳覺得數學中什麽東西正是這個作用？是函數，簡單的說就是y=f(x)。圖靈機正好與可計算函數等價。現在就用這個例子說明求解y=f(x)是如何等價於壹種圖靈機識別的語言的： 壹種語言L={<x,y>|y=f(x)}，如果圖靈機識別這種語言，就必須計算f(x)，如果y與f(x)相等，就停機進入接受狀態。看見了吧，實際上識別語言L與計算f(x)是壹回事。 對於排序問題b=sort(a)，求解這個問題相當於圖靈機識別這種語言： L={<x,y>|y=sort(x) and x是數組 and y是數組}。
參考資料：
/科技文獻資料/圖靈機/圖靈可識別語言.htm