愛(ài)華網(wǎng)
圖靈機(jī)（TuringMachine）有有限個(gè)狀態(tài)。其中一個(gè)狀態(tài)是開(kāi)始狀態(tài)。這些狀態(tài)的一個(gè)子集是接受狀態(tài)，還有一個(gè)子集是拒絕狀態(tài)。接受狀態(tài)子集和拒絕狀態(tài)子集不相交（不能有一個(gè)狀態(tài)既是接受狀態(tài)，也是拒絕狀態(tài)）。
有一個(gè)字符集Σ，圖靈機(jī)以Σ上的字符串ω作為輸入（ω∈Σ*，Σ*是一個(gè)集合，它的元素是：由0個(gè)或多個(gè)Σ上的字符組成的有限長(zhǎng)度的字符串）。圖靈機(jī)還有一個(gè)字符集Γ，是”帶“（tape）字符集。Γ包含Σ中的所有字符，還必須有一個(gè)Σ中沒(méi)有的字符，就是空白字符。圖靈機(jī)的帶（tape）上一開(kāi)始默認(rèn)都是空白字符。圖靈機(jī)的帶，是一個(gè)無(wú)限長(zhǎng)的帶子，分成一個(gè)個(gè)的單元格，每一個(gè)單元格上寫(xiě)一個(gè)字符（初始都是空白符）。圖靈機(jī)有一個(gè)讀寫(xiě)頭，總是位于帶的某一個(gè)單元格之上。讀寫(xiě)頭對(duì)當(dāng)前的單元格進(jìn)行讀寫(xiě)。讀寫(xiě)頭可以順著帶子左右移動(dòng)，但一次只能移動(dòng)一個(gè)單元格。Γ就是圖靈機(jī)可以向帶子上寫(xiě)的字符的集合。
圖靈機(jī)的動(dòng)作是這樣的：根據(jù)當(dāng)前所處的狀態(tài)和當(dāng)前讀到的字符，在當(dāng)前單元格上寫(xiě)下一個(gè)字符，向左或右移動(dòng)一個(gè)單元格，進(jìn)入另一個(gè)狀態(tài)（對(duì)于這些動(dòng)作的規(guī)定，就是圖靈機(jī)的轉(zhuǎn)移函數(shù)δ）。一開(kāi)始，將輸入字符串ω（ω∈Σ*）放在帶子上，把圖靈機(jī)的讀寫(xiě)頭對(duì)準(zhǔn)ω的第一個(gè)字符，并讓圖靈機(jī)處于開(kāi)始狀態(tài)。然后圖靈機(jī)就開(kāi)始一步一步地運(yùn)行：讀字符、寫(xiě)字符、移動(dòng)讀寫(xiě)頭、進(jìn)入新?tīng)顟B(tài)，然后再重復(fù)......直到圖靈機(jī)進(jìn)入某一個(gè)接受狀態(tài)，這時(shí)圖靈機(jī)停機(jī)并接受ω。圖靈機(jī)也有可能進(jìn)入一個(gè)拒絕狀態(tài)而停機(jī)，這種情況下圖靈機(jī)拒絕ω。除了這兩種情況，還有第三種情況：那就是圖靈機(jī)永遠(yuǎn)不會(huì)停機(jī)。圖靈機(jī)既不進(jìn)入接受狀態(tài)，也不進(jìn)入拒接狀態(tài)，而是一直運(yùn)行下去。后兩種情況，合稱圖靈機(jī)不接受ω。
所以，對(duì)于Σ*中的一個(gè)字符串ω，這個(gè)圖靈機(jī)要么接受它，要么不接受它。圖靈機(jī)不接受ω，有可能是圖靈機(jī)拒絕ω，也有可能圖靈機(jī)不停機(jī)。一個(gè)圖靈機(jī)接受的所有字符串構(gòu)成的集合（是Σ*的一個(gè)子集）作為一個(gè)語(yǔ)言（字符串集合即為”語(yǔ)言“），就是這個(gè)圖靈機(jī)”識(shí)別“的語(yǔ)言。
有一類(lèi)圖靈機(jī)，它們對(duì)于任何輸入字符串ω都停機(jī)（要么接受，要么拒絕。兩者必居其一）。這類(lèi)圖靈機(jī)被稱為判定器。被判定器識(shí)別的語(yǔ) 言稱作被這個(gè)判定器”判定“（這類(lèi)語(yǔ)言稱作”可判定語(yǔ)言“）。如果把識(shí)別一個(gè)語(yǔ)言作為”計(jì)算“的通用模型（這點(diǎn)以后說(shuō)明），那么判定器就是可以明確地給出計(jì)算結(jié)果的圖靈機(jī)。要么”是“，要么”不是“。
一個(gè)圖靈機(jī)的“程序”，就是固化在它的狀態(tài)集以及轉(zhuǎn)移函數(shù)δ中的“動(dòng)作”。但也可以構(gòu)建一個(gè)”通用圖靈機(jī)“，它的輸入字符串是一個(gè)”序列化“了的圖靈機(jī)M和一個(gè)字符串ω?！蓖ㄓ脠D靈機(jī)“在字符串ω上模擬圖靈機(jī)M的行為，產(chǎn)生和M一樣的結(jié)果（接受、拒絕或不停機(jī)）。一個(gè)圖靈機(jī)只有有限個(gè)狀態(tài)、有窮字符集Σ和帶字符集Γ，以及定義域和值域都是有窮離散集合的轉(zhuǎn)移函數(shù)δ，所以只要約定好了格式，一個(gè)圖靈機(jī)就可以用一個(gè)字符串來(lái)描述（序列化成了一個(gè)字符串）?！蓖ㄓ脠D靈機(jī)“有點(diǎn)像可存儲(chǔ)程序的馮.諾依曼計(jì)算機(jī)。
二. 計(jì)算、算法與圖靈-邱奇論題
你也許會(huì)覺(jué)得：圖靈機(jī)是干嗎使的？答案：計(jì)算。那什么是計(jì)算？圖靈機(jī)干的事情就是計(jì)算。那2×3＝6圖靈機(jī)能算么？如果你把"aa|aaa"作為輸入字符串ω提供給某個(gè)圖靈機(jī)，這個(gè)圖靈機(jī)停機(jī)，并在帶子上留下aaaaaa。你給了它2個(gè)a和3個(gè)a，它給了你6個(gè)a，它不就是計(jì)算了2×3＝6么。
這里對(duì)”圖靈機(jī)編程“不做詳細(xì)介紹了。總之圖靈和邱奇證明，任何有步驟的、確定的計(jì)算過(guò)程，都可以由圖靈機(jī)實(shí)現(xiàn)。任何可執(zhí)行計(jì)算的裝置：算盤(pán)、珍尼紡紗機(jī)、超級(jí)計(jì)算機(jī)等等，都可以由一臺(tái)圖靈機(jī)模擬。也就是說(shuō)：任何計(jì)算裝置，都無(wú)法超過(guò)圖靈機(jī)的能力。圖靈機(jī)也就定義了計(jì)算和算法。
一切計(jì)算問(wèn)題都可以等價(jià)于字符串接受/不接受問(wèn)題，也就是語(yǔ)言的識(shí)別（也許是判定）問(wèn)題。也就是說(shuō)一切”計(jì)算“，都可由圖靈機(jī)進(jìn)行。
三. 圖靈機(jī)不可判定問(wèn)題
上面說(shuō)，有些語(yǔ)言（字符串集合）可被一個(gè)判定器（總會(huì)停機(jī)的圖靈機(jī)）判定（識(shí)別）。給一個(gè)字符串ω，這個(gè)判定器得出結(jié)論：ω是否屬于這個(gè)語(yǔ)言。這些語(yǔ)言是”可判定“語(yǔ)言。那么是否存在不可判定語(yǔ)言？也就是是否存在一個(gè)語(yǔ)言，不存在一個(gè)判定器可以判定它？答案是”是“。設(shè)想下面的語(yǔ)言：
A = {(<M>,ω) |<M>是表示圖靈機(jī)M的字符串，ω是一個(gè)字符串。M接受ω}
也就是，語(yǔ)言A中的字符串都有兩部分組成：第一部分是一個(gè)圖靈機(jī)M的字符串表示<M>；第二部分是一個(gè)字符串ω。且M接受ω。
假設(shè)語(yǔ)言A是可判定的，也就是存在一個(gè)判定器H。當(dāng)M接受ω時(shí)，H接受(<M>,ω)；當(dāng)M不接受ω時(shí)，H拒絕(<M>,ω)。（注意H是一個(gè)判定器，它總會(huì)停機(jī)，接受或拒絕(<M>,ω)）。那么我們對(duì)H稍加改造，將它的結(jié)果取一下反：當(dāng)M接受ω時(shí)，H拒絕(<M>,ω)；當(dāng)M不接受ω時(shí)，H接受(<M>,ω)。這很容易，只要把H的接收狀態(tài)和拒絕狀態(tài)互換一下身份即可。
然后我們可以再對(duì)H做一個(gè)變化，它的輸入字符串僅僅是一個(gè)圖靈機(jī)M的序列化字符串<M>，喂給這個(gè)M的輸入不再是某個(gè)字符串ω，而就是字符串<M>本身。那么H的行為就變成了：輸入給它一個(gè)表示某個(gè)圖靈機(jī)的字符串<M>。把<M>當(dāng)做給圖靈機(jī)M的輸入，若M接受<M>，則H拒絕<M>；若M不接受<M>，則H接受<M>。
精彩之處到了：若把H自己的序列化字符串<H>提供給H會(huì)發(fā)生什么？當(dāng)H接受<H>時(shí)，H拒絕<H>；當(dāng)H不接受<H>時(shí)，H接受<H>。理發(fā)師悖論。唯一的結(jié)論只能是，H不可能存在。就是說(shuō)對(duì)于語(yǔ)言A，不可能構(gòu)造一個(gè)判定器去判定它。A是不可判定語(yǔ)言。不可判定語(yǔ)言是存在的。
再換一種方式說(shuō)一遍（不帶任何符號(hào)，爭(zhēng)取用話說(shuō)明白）：假如存在一個(gè)判定器（還記得判定器么?就是總會(huì)停機(jī)的圖靈機(jī)，要么接受，要么拒絕，反正不會(huì)不停機(jī)），以一個(gè)圖靈機(jī)的描述（也是一個(gè)字符串）和一個(gè)字符串作為輸入。它可以判定這個(gè)圖靈機(jī)是否接受這個(gè)字符串，也就是：這個(gè)圖靈機(jī)接受這個(gè)字符串，我這個(gè)判定器就停機(jī)接受；這個(gè)圖靈機(jī)不接受這個(gè)字符串，我這個(gè)判定器就停機(jī)拒絕。（注意我這個(gè)既然是判定器，它就能做到上邊說(shuō)的）。那么以這個(gè)判定器為基礎(chǔ)，就可以構(gòu)造另一個(gè)判定器，這個(gè)判定器只拿一個(gè)圖靈機(jī)的描述（一個(gè)字符串）當(dāng)輸入，然后把這個(gè)描述本身當(dāng)做給這個(gè)圖靈機(jī)的輸入，判斷這個(gè)圖靈機(jī)是否接受它自己的描述：它接受，我判定器就停機(jī)并接受；它不接受，我判定器就停機(jī)并拒絕。然后以這個(gè)判定器為基礎(chǔ)，再改造一下。這次改造簡(jiǎn)單，只是把接受和拒絕反一下：判定器的輸入是一個(gè)圖靈機(jī)的描述（一個(gè)字符串），然后判定這個(gè)圖靈機(jī)是否接受它自己的描述：它接受，我判定器就停機(jī)且接受；它不接受，我判定器就停機(jī)且拒絕。沒(méi)問(wèn)題吧。好！現(xiàn)在把我這個(gè)判定器自己的描述輸入給它，它將如何？它將在自己接受自己的描述時(shí)拒絕自己的描述；在自己不接受自己的描述時(shí)接受自己的描述。悖論了！
如果存在不可判定語(yǔ)言，那么必然存在不可識(shí)別語(yǔ)言。就是無(wú)法構(gòu)造一個(gè)圖靈機(jī)，接受這個(gè)語(yǔ)言的每一個(gè)字符串（用不著拒絕每一個(gè)不屬于這個(gè)語(yǔ)言的字符串，因?yàn)檫@里說(shuō)的是識(shí)別，而不是判定）。因?yàn)椋喝绻粋€(gè)語(yǔ)言L和它的補(bǔ)^L都是圖靈機(jī)可識(shí)別的，那么L是可判定的。證明：設(shè)識(shí)別L的圖靈機(jī)是M1，識(shí)別^L的圖靈機(jī)是M2。構(gòu)造圖靈機(jī)M，它在字符串ω上交替地一步一步地模擬M1和M2。因?yàn)橐粋€(gè)字符串要么屬于L，要么屬于^L，也就是對(duì)于一個(gè)字符串ω，要么M1進(jìn)入接受狀態(tài)，要么M2進(jìn)入接受狀態(tài)。于是M總會(huì)看到M1或M2（之一）進(jìn)入接受狀態(tài)。如M1進(jìn)入接受狀態(tài)，則M停機(jī)并接受ω；若M2進(jìn)入接受狀態(tài)，則M停機(jī)拒絕ω。那么M就成了語(yǔ)言L的一個(gè)判定器。所以如果一個(gè)語(yǔ)言不可判定，必然它或者它的補(bǔ)是不可識(shí)別的。不可識(shí)別語(yǔ)言是存在的。
一個(gè)不可判定的語(yǔ)言，就是一個(gè)不可計(jì)算的問(wèn)題。那是一個(gè)超出了計(jì)算機(jī)能力的問(wèn)題，一個(gè)不能被任何有步驟的、確定性的算法所能解決的問(wèn)題。那是什么樣的問(wèn)題？也許是女人心吧。
愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/25101015/245482.html
