回到正題:圖靈機(jī)。圖靈機(jī)能夠識(shí)別語(yǔ)言,而圖靈機(jī)本身當(dāng)然也可以由語(yǔ)言描述。什么是語(yǔ)言?給定一個(gè)字母表∑,一個(gè){[由∑中的字母組成的序列]的集合}就是∑上的一個(gè)語(yǔ)言(為了消除歧義,算式可以加括號(hào),語(yǔ)言當(dāng)然也可以)。必須清楚這些概念中哪些是有限的,哪些是無限的:一個(gè)語(yǔ)言包含的字符串?dāng)?shù)可以是有限的也可以是無限的,但一個(gè)字母表上的所有語(yǔ)言的數(shù)目是無限的,而語(yǔ)言中任意一個(gè)字符串的長(zhǎng)度是有限的。
首先要證明的是:一個(gè)字母表上所有語(yǔ)言構(gòu)成的集合不僅是無限的,而且是不可數(shù)的。 這里需要借助無限二進(jìn)制序列的集合來幫助證明。一個(gè)無限二進(jìn)制序列(即{0,1}組成的無限序列)是一階無限,那么這些序列組成的集合就是“無限×無限”,可以通過對(duì)角線方法證明無限二進(jìn)制序列是不可數(shù)的,也可以將實(shí)數(shù)集的元素唯一地映射到無限二進(jìn)制序列集合。
用后者的方法,可以這樣建立二者之間的映射:二進(jìn)制序列每4個(gè)為一組,用8421BCD碼編碼,4位對(duì)應(yīng)實(shí)數(shù)中的一位,再用1111表示小數(shù)點(diǎn),這樣每個(gè)實(shí)數(shù)總能映射到一個(gè)唯一的二進(jìn)制序列,既然實(shí)數(shù)集不可數(shù),那么無限二進(jìn)制序列也不可數(shù)。 接下來證明,{無限二進(jìn)制序列的集合B}與(任意字母表){∑上的所有語(yǔ)言組成的集合L}是同樣規(guī)模的,仍然通過建立映射的方法。設(shè)∑上所有字符串的集合按字典序排序成∑*={s1, s2, s3, 。..},L中的每個(gè)語(yǔ)言A都對(duì)應(yīng)一個(gè)二進(jìn)制序列b:如果si∈A,bi=1;否則bi=0,這樣的序列稱作A的特征序列。舉個(gè)例子,如果∑={a,b},A是所有包含b的串構(gòu)成的語(yǔ)言,則A的特征序列b如下:
∑*={a, b, aa, ab, ba, bb, aaa, aab,。..} A ={ b, ab, ba, bb, aab,。..} b = 0 1 0 1 1 1 0 1 ,。..
反之,每個(gè)二進(jìn)制序列b也能對(duì)應(yīng)一個(gè)唯一的語(yǔ)言,所以L與B等勢(shì),又因?yàn)锽是不可數(shù)集,所以{∑上的所有語(yǔ)言組成的集合L}也是不可數(shù)的。
好,明確了所有語(yǔ)言構(gòu)成的集合是不可數(shù)的之后,我要回答下面這個(gè)問題:為什么圖靈機(jī)集合是可數(shù)的?(reserve:哥德爾配數(shù)法)
從圖靈機(jī)的定義入手,圖靈機(jī)是1個(gè)7元組(Q,∑,Γ,δ,q0,qaccept,qreject)。每一臺(tái)圖靈機(jī)總是由有限個(gè)字符編碼而成: 1) 有限的狀態(tài)集Q。 2) 有限的輸入字母表∑。 3) 有限的帶字母表Γ。 4) 有限的轉(zhuǎn)換函數(shù)δ。 5) 1個(gè)起始狀態(tài)q0。 6) 有限個(gè)接受狀態(tài)qaccept。 7) 有限個(gè)拒絕狀態(tài)qreject。 若上述每個(gè)元素都用二進(jìn)制編碼表示,任意一臺(tái)圖靈機(jī)都只需要有限個(gè)二進(jìn)制位。再將這些二進(jìn)制串按照字典序排列,就可以得到一個(gè){圖靈機(jī)集合}-》自然數(shù)集的一一對(duì)應(yīng)。
好,給定一個(gè)字母表∑: [∑上的所有語(yǔ)言]的集合《=》[二進(jìn)制無限序列]的集合《=》實(shí)數(shù)集《=》不可數(shù)集 [所有圖靈機(jī)]的集合《=》自然數(shù)集《=》可數(shù)集
有不可數(shù)個(gè)語(yǔ)言,卻只有可數(shù)個(gè)圖靈機(jī),語(yǔ)言的集合“大于”圖靈機(jī)的集合,所以從本質(zhì)上證明了必然存在圖靈機(jī)不能識(shí)別的語(yǔ)言。 推論:必然存在圖靈機(jī)不能判定的語(yǔ)言。理由是圖靈可判定語(yǔ)言的集合不會(huì)大于圖靈可識(shí)別語(yǔ)言。 圖靈可判定語(yǔ)言要求更嚴(yán)格,所以應(yīng)該存在這樣的語(yǔ)言:它是圖靈可識(shí)別的,但同時(shí)不是圖靈可判定的。事實(shí)確實(shí)如此,圖靈自己就給出了一個(gè): A={《M, ω》 | M描述一臺(tái)圖靈機(jī),且M描述的機(jī)器接受ω} 首先證明A是圖靈可識(shí)別的(形式化證明太過繁瑣,這里只給出很高層次的證明)。設(shè)通用圖靈機(jī)U這樣運(yùn)行:U接受參數(shù)《M, ω》,它可根據(jù)圖靈機(jī)M的描述模擬M的行為,并在虛擬的M上計(jì)算ω。如果M接受ω,那么U進(jìn)入接受狀態(tài);否則拒絕。
依據(jù)定義以及通用圖靈機(jī)的存在性,U能識(shí)別A,所以A是圖靈可識(shí)別的,證畢。
順著這個(gè)證明走下去,如果M本身遇到輸入ω時(shí)會(huì)陷入循環(huán),那么模擬M的U也會(huì)陷入循環(huán),所以U不是判定器。如果U知道M在ω上不停機(jī),那么它可以進(jìn)入拒絕狀態(tài),問題是它不知道。那么能判定A的圖靈機(jī)存在嗎?我們就假設(shè)存在H,使得: 1)若M接受ω,則H(《M,ω》) =接受 2)若M不接受ω,則H(《M,ω》) =拒絕 根據(jù)H的定義,無論M接不接受ω,H總能停機(jī)。進(jìn)一步再假設(shè)有圖靈機(jī)D,以H為子程序,接受一個(gè)描述圖靈機(jī)的串《M》,在H上運(yùn)行H(《M,《M》》),并返回相反的結(jié)果: 1)若H(《M,《M》》)=接受,則D(《M》)=拒絕 2)若H(《M,《M》》) =拒絕,則D(《M》)=接受 也就是說,如果一臺(tái)圖靈機(jī)M接受描述它自身的串《M》,那么D(《M》)進(jìn)入拒絕狀態(tài)。構(gòu)造這樣一臺(tái)奇怪的D是為了讓它做下面這件事情,現(xiàn)在對(duì)D輸入描述它自己的串《D》,看看會(huì)發(fā)生什么: 1)若D接受《D》,即H(《D,《D》》)=接受,則D(《D》)=拒絕 2)若D拒絕《D》,即H(《D,《D》》) =拒絕,則D(《D》)=接受 到底是接受還是拒絕呢?兜了一個(gè)圈子,D繞回原地,產(chǎn)生了矛盾。所以D是不存在的,所以H也是不存在的,語(yǔ)言A不可判定,證畢。
上述證明比較繞,我用一階邏輯再改寫一遍
命題: 1)P:存在語(yǔ)言A的判定器H 2)Q:存在以H為子程序的圖靈機(jī)D(描述見上) 已知條件: 1)P→Q:如果有H,總能設(shè)計(jì)出D 2)┐Q:D是不存在的(證明見上) 證明: 1 P 假設(shè) 2 P→Q 已知條件 3 Q 1,2 4 ┐Q 已知條件 5 ┴ 推出矛盾 6 ┐P 假設(shè)不成立 上面的證明中,圖靈機(jī)D的構(gòu)造簡(jiǎn)直是神來之筆,圖靈怎么想到的?雖然之前的證明沒有直接給出不可判定的語(yǔ)言,但已經(jīng)從數(shù)量上證明有圖靈機(jī)不能判定的語(yǔ)言,由于判定器的要求更嚴(yán)格,所以可以推斷所有判定器構(gòu)成的集合小于所有語(yǔ)言構(gòu)成的集合。這是個(gè)與“實(shí)數(shù)集的勢(shì)大于自然數(shù)集”類似的命題,所以應(yīng)該能用類似的方法——對(duì)角線方法證明。好,嘗試一下。 康托構(gòu)造映射表格時(shí),表格的每一行由一個(gè)自然數(shù)表示這是第幾行,每一列也由一個(gè)自然數(shù)標(biāo)識(shí)列數(shù),對(duì)角線法構(gòu)造出來的實(shí)數(shù)實(shí)際上是一行,然而這一行卻和每一行都不一樣。剛才的證明我們看到,圖靈機(jī)集合是可數(shù)集,可將其對(duì)應(yīng)自然數(shù),標(biāo)識(shí)表格的每一行,那么每一列用什么標(biāo)識(shí)呢?怎樣讓列數(shù)與行數(shù)相等呢?行和列的交叉處是什么呢?自然數(shù)/實(shí)數(shù)的例子中,每一行由一個(gè)自然數(shù)對(duì)應(yīng)一個(gè)實(shí)數(shù),在這個(gè)問題中,行由圖靈機(jī)標(biāo)識(shí)了,那么不難想到,每一行應(yīng)該是一個(gè)語(yǔ)言。語(yǔ)言又該如何表示?下面依次回答這些問題。 列應(yīng)該用什么來標(biāo)識(shí)?在對(duì)角線方法中,表格的行列數(shù)一致,行和列都用自然數(shù)集標(biāo)識(shí)。那么首先可以想到既然行用圖靈機(jī)標(biāo)識(shí),那么列也可以用圖靈機(jī)標(biāo)識(shí)。但是這樣的話行列交匯處就沒什么意義了,試問隨意挑選的兩臺(tái)圖靈機(jī)之間能擦出什么火花? 腦子再轉(zhuǎn)一下,圖靈機(jī)與圖靈機(jī)之間沒有什么一般化的關(guān)系,圖靈機(jī)識(shí)別的是語(yǔ)言,是字符串,那么將標(biāo)識(shí)列的圖靈機(jī)換成描述圖靈機(jī)的串,既保持了行列數(shù)一致性,又讓行列交匯處有了非平凡的意義!即,用M1, M2, M3.。.標(biāo)識(shí)第1行、第2行、第3行??再用描述圖靈機(jī)的字符串《M1》, 《M2》, 《M3》。..標(biāo)識(shí)第1列、第2列、第3列??行列交匯處就填入accept或reject,表示一臺(tái)圖靈機(jī)是否接受描述某一臺(tái)圖靈機(jī)的串!這樣,每一行剛好也就是一個(gè)語(yǔ)言,每一個(gè)部分的意義都正好是我們想要的。
《M1》
《M2》
《M3》
《M4》
??
M1
accept
reject
reject
reject
M2
reject
reject
accept
M3
accept
accept
reject
accept
M4
reject
Accept
reject
accept
??
為構(gòu)造對(duì)角線準(zhǔn)備的表格 走到這一步,離結(jié)果就很近了。 若將所有圖靈機(jī)和描述它們的串排成表,行列交叉處就是H(Mi,《Mj》)的運(yùn)行結(jié)果。構(gòu)造圖靈機(jī)D,實(shí)際上就是用對(duì)角線方法選出一行,這一行的第1列與M1相反,第2列與M2相反,第3列與M3相反??所以構(gòu)造出來的這一行肯定不在這個(gè)表中。如果在,這么D所在的行與對(duì)角線相交處會(huì)出現(xiàn)矛盾!
《M1》
《M2》
《M3》
《M4》
??
D
??
M1
accept
reject
reject
reject
accept
M2
reject
Reject
accept
reject
reject
M3
accept
Accept
Reject
accept
accept
M4
reject
accept
reject
accept
reject
??
D
reject
accept
accept
reject
??
D的每一列都與對(duì)角線相反,到它自己與對(duì)角線的交匯處產(chǎn)生矛盾 想必圖靈深知語(yǔ)言集比圖靈機(jī)集要“大”,一臺(tái)圖靈機(jī)只能對(duì)應(yīng)一個(gè)語(yǔ)言,所以用對(duì)角線方法必定能構(gòu)造出一個(gè)所有圖靈機(jī)都不能識(shí)別的語(yǔ)言。這個(gè)語(yǔ)言就是D“識(shí)別”的語(yǔ)言,則D的語(yǔ)言肯定不會(huì)出現(xiàn)在那個(gè)圖靈機(jī)和對(duì)應(yīng)語(yǔ)言的表格中。如果強(qiáng)行將這臺(tái)“不存在的圖靈機(jī)”安插進(jìn)表格中,必然產(chǎn)生矛盾,矛盾就發(fā)生在D所在行與對(duì)角線的相交處。就像康托用對(duì)角線方法構(gòu)造出來的那個(gè)實(shí)數(shù)無法插入到[自然數(shù)-》實(shí)數(shù)]的映射表格中,否則構(gòu)造出來的那個(gè)實(shí)數(shù)就與它自己矛盾了,神奇的“圖靈機(jī)D”就是這么來的。 圖靈是用圖靈機(jī)的術(shù)語(yǔ)改寫了對(duì)角線方法,在圖靈機(jī)上重現(xiàn)康托的思想。
至此,回答了第一個(gè)問題:為什么圖靈機(jī)也有不可判定的語(yǔ)言,并且還構(gòu)造了一個(gè)這樣的語(yǔ)言,即A={《M, ω》 | M描述一臺(tái)圖靈機(jī),且M描述的機(jī)器接受ω},A又被稱為接受問題。
語(yǔ)言A是超越圖靈機(jī)極限的必然產(chǎn)物,因?yàn)閳D靈機(jī)和語(yǔ)言的內(nèi)在關(guān)系決定了A這樣不能被任何圖靈機(jī)判定的語(yǔ)言是存在的。這是本質(zhì)上的原因,但關(guān)于A本身還有一個(gè)表象上的原因(之前提到過):之所以不能用圖靈機(jī)斷定其它圖靈機(jī)是否接受一個(gè)串,是因?yàn)閳D靈機(jī)不能斷定其它圖靈機(jī)在某個(gè)輸入串上計(jì)算時(shí)是否會(huì)停機(jī),這個(gè)問題同樣是不可判定的,這就是著名的停機(jī)問題(Halting problem)。莊子曰,“吾生也有涯,而知也無涯,以有涯隨無涯,殆已”。以有限的步驟去判定可能無限的計(jì)算,殆已。 但由此我產(chǎn)生了一個(gè)很大的疑問:為什么圖靈機(jī)會(huì)不停機(jī)?這也是我試圖回答的第二個(gè)問題。
評(píng)論
查看更多