計(jì)算機(jī)的缺陷

英文網(wǎng)址：https://plus.maths.org/content/os/issue5/turing/index

　　阿蘭-圖靈被《圖靈作品集》[1]的總編輯P.N. Furbank教授描述為 "科學(xué)的領(lǐng)軍人物之一"。

 

 

圖1：阿蘭-圖靈

　　60年前，圖靈最著名的論文發(fā)表了，他在第一臺存儲程序的數(shù)字計(jì)算機(jī)開始運(yùn)行的十年前就提出了通用計(jì)算機(jī)的概念。

　　這只是圖靈眾多成就中的一項(xiàng)?，F(xiàn)在人們知道，二戰(zhàn)期間在布萊切利公園圖靈破譯德國恩尼格瑪密碼的工作為這場戰(zhàn)爭的勝利作出了重大貢獻(xiàn)——盡管他最親密的朋友直到圖靈在1954年因服用氰化鉀而不幸去世都一直不知道這一點(diǎn)。

圖2a。英格瑪機(jī)器。(圖片來源：[ http://agn-www.informatik.uni-hamburg.de/ ]AGN，漢堡大學(xué)，版權(quán)所有，1995年，Morton Swimmer)

 

　　圖靈的戰(zhàn)時工作表明計(jì)算機(jī)的重要性。盡管大部分黑客工作是以機(jī)械方式完成的，但這也離不開巨大的人類計(jì)算機(jī)團(tuán)隊(duì)。

 

 

圖2b: 編碼轉(zhuǎn)子的特寫。

 

　　他戰(zhàn)時工作的另一個特點(diǎn)是使用了概率論。圖靈在這一領(lǐng)域的很多工作也是高度創(chuàng)新的。戰(zhàn)后，通過他當(dāng)時的助手（后來的教授）杰克-古德發(fā)表的工作，人們認(rèn)識到了這一點(diǎn)，而沒有提到它在戰(zhàn)時的用途。

戰(zhàn)后圖靈對計(jì)算機(jī)仍然興趣盎然，當(dāng)時他在NPL（國家物理實(shí)驗(yàn)室）從事存儲程序計(jì)算機(jī)（ACE或自動計(jì)算引擎）的開發(fā)工作。1948年，他搬到了曼徹斯特，當(dāng)年第一臺存儲程序數(shù)字計(jì)算機(jī)就是在那里運(yùn)行的。


　　盡管圖靈與真正的計(jì)算機(jī)之間的聯(lián)系極其微弱，但他對計(jì)算理論，特別是人工智能（圖靈測試）、計(jì)算機(jī)結(jié)構(gòu)（ACE）和軟件工程做出了重大貢獻(xiàn)。計(jì)算科學(xué)領(lǐng)域著名的圖靈獎就是以他的名字命名的，這在一定程度上說明了他的貢獻(xiàn)。

 

在機(jī)器智能性的圖靈測試中，觀察者必須通過提出一系列的問題來區(qū)分機(jī)器和人類。

 

終止問題

　　一般來說，一旦計(jì)算機(jī)開始計(jì)算，就沒有辦法知道該計(jì)算是否會得出明確的答案。這個問題被稱為 “圖靈機(jī)的終止問題”，并在1937年他對制造的機(jī)器的介紹[2]中被首次證明。 這個證明充分彰顯了圖靈的智慧。

　　為了引出這個證明，有必要引進(jìn)一些關(guān)于數(shù)列或序列的內(nèi)容。如果一個集合的元素可以被列在一個單一的序列中，那么就稱他們可列。

例如自然數(shù)的集合可以列為0、1、2、3、...，無窮無盡。要把所有的整數(shù)，即正數(shù)和負(fù)數(shù)列成一個序列，你可以寫成0、1、-1、2、-2、3、-3、...，同樣沒有問題。

分?jǐn)?shù)的計(jì)算需要更多的工作。通常需要在平面中使用表格或矩陣來完成。我們只需要看正數(shù)——它可以擴(kuò)展到負(fù)數(shù)，也就是拓展到整數(shù)。

 

圖3：分?jǐn)?shù)表。分?jǐn)?shù)可以通過表格來計(jì)算，然后沿對角線計(jì)算，以藍(lán)色顯示。

 

　　這里做了很多重復(fù)的工作——首先所有的對角線元素都是相等的——所以這個算法有點(diǎn)浪費(fèi)資源，但好在它能完成工作。繼續(xù)下去，每個分?jǐn)?shù)都會出現(xiàn)在二維矩陣的某個地方。要把矩陣寫成一個單一的序列，在西南到東北的對角線上上下下工作，得到。

1, 1/2, 2, 1/3, 2/2, 3, 1/4, 2/3, 3/2, 4,...

　　接下來，我們會看到一個非常著名的定理——康托爾定理。根據(jù)這個定理，實(shí)數(shù)是不能以這種方式計(jì)算的。實(shí)數(shù)的集合包括像Pi（3.14159……）這樣的無理數(shù)，它們不能被表示成一個最簡分?jǐn)?shù)。

康托爾定理的證明

　　要證明康托爾定理，只需證明，我們無法計(jì)算所有的二進(jìn)制序列，換句話說，我們無法計(jì)算無限的0和1的序列。

我們可以用反證法來完成這個證明。假設(shè)我們可以計(jì)算上述序列，我們可以給每個二進(jìn)制序列貼上B1，B2，B3，……無限的標(biāo)簽。讓我們先來像以前一樣把每個序列的元素列在一個表格或矩陣中。

圖4：二進(jìn)制序列表。一個可能的二進(jìn)制序列列表，序列D是通過倒置對角線上的元素構(gòu)建的，以藍(lán)色顯示。

 

　　現(xiàn)在定義一個二進(jìn)制序列D，如果B1在該列中有1，則在第一列中選擇0，如果B1在該列中有0，則選擇1。然后我們在第二列中選擇一個0，如果B2在該列中有一個1，如果它有一個0，則選擇1，以此類推。由此產(chǎn)生的二進(jìn)制序列，D，不可能在列表中，因?yàn)槿绻诹斜碇校捅仨毰cB序列之一相匹配，比如說Bn，對于某個n，但是我們剛剛故意確保D的第n列與Bn不同。故矛盾。

　　也就是說，無論我們?nèi)绾瘟卸M(jìn)制序列，我們總能找到一個不在列表中的序列D。

　　這個過程被稱為對角化。正如你所看到的，我們已經(jīng)給出了一個簡單的規(guī)則，因此，給定一個計(jì)算二進(jìn)制數(shù)列表的規(guī)則，那么我們就會有一個計(jì)算這個對角線二進(jìn)制數(shù)的規(guī)則，而它恰好不在列表中。

圖靈的觀點(diǎn)

　　最后，讓我們勾勒一下圖靈的觀點(diǎn)（與庫爾特-哥德爾在1931年的一個更著名的推理有關(guān)）是如何將這個論證推向一個大階段的。

　　這里的證明不是圖靈的原始證明，但與此相關(guān)。圖靈的這篇經(jīng)典論文的大部分內(nèi)容都是在描述他的計(jì)算機(jī)概念，以及為什么它是通用的。即任何可以根據(jù)有限的規(guī)則列表進(jìn)行計(jì)算的東西，都可以由他的一臺機(jī)器進(jìn)行計(jì)算。

　　簡而言之，圖靈機(jī)可以被認(rèn)為是一個黑盒子，它對輸入的一個數(shù)進(jìn)行某種計(jì)算。如果計(jì)算得出結(jié)論，或終止計(jì)算，就會返回一個輸出數(shù)字。否則，理論上機(jī)器就會永遠(yuǎn)運(yùn)行下去。圖靈機(jī)的數(shù)量是無限的，因?yàn)榭梢杂糜邢薜囊?guī)則列表完成無限多的計(jì)算。

　　圖靈理論的結(jié)論之一是，存在一個可以模擬所有可能的圖靈機(jī)的機(jī)器。這意味著我們可以認(rèn)為圖靈機(jī)是可數(shù)的，并通過一種按字母順序排列的方式，由一臺通用機(jī)列出T1、T2…。圖靈用它來描述圖靈版本的哥德爾定理，即終止問題——沒有程序可以告訴圖靈機(jī)是否會在給定的輸入上進(jìn)行有限步后終止。

終止問題的不可解性

　　我們把使用第n臺圖靈機(jī)Tn對輸入i的結(jié)果表示為Tn(i)。假設(shè)有一個規(guī)則或程序來決定Tn(i)在所有n和i的值上是否終止。

 

圖5：可以用一個終止規(guī)則來制作一個輸出Tn(i)的表格，用問號來表示永不終止的計(jì)算。這個表格只是說明性的，其內(nèi)容的選擇并沒有考慮到圖靈機(jī)的任何特定排序。

 

　　但是，通過與上面類似的對角化程序，我們可以定義一個新的圖靈機(jī)，比如說D，它對所有的輸入都會終止，并對輸入i返回以下輸出：

 

　　　　　　0       如果 Ti(i) 不終止；

　　　　　　Ti(i)+1   如果 Ti(i) 終止；

 

　　但這個機(jī)器D一定是這些機(jī)器中的一個，換句話說，它一定是某些d對應(yīng)的Td。然而，我們剛剛定義它在輸入d的情況下給出了與Td不同的答案。 所以矛盾就出現(xiàn)了。

　　與原來的對角線論證相比，這里的復(fù)雜性在于：

　　　　(1)所做的所有列舉本身是可計(jì)算的；

　　　　(2)任何機(jī)器Tn在進(jìn)行計(jì)算時可能會或可能不會終止。

　　這些都沒有進(jìn)入康托爾的原始對角線論證。這種可計(jì)算的對角化最早是由哥德爾、圖靈等人在二戰(zhàn)前十年所做的開創(chuàng)性工作中使用的，并且一直是一種重要技術(shù)。真正困難的工作在于制定可計(jì)算性的各種定義，但那是另一個故事了

什么是生命?

 

 

 

 

圖6a:圖靈精心手繪的太陽花。

 

　　在他去世前的最后幾年，圖靈正在研究一些完全不同的東西，這些東西從他的學(xué)生時代起就一直在他的心里，即生物形態(tài)的起源--形態(tài)發(fā)生學(xué)。

 

 

圖6b：一個特寫部分。

　　簡單的細(xì)胞怎么可能知道如何成長為相對巨大的結(jié)構(gòu)形式？在薛定諤1943年的演講《生命是什么》中，引出了遺傳信息可以儲存在分子水平上的關(guān)鍵想法，而克里克和沃森此時正忙于通過DNA的結(jié)構(gòu)來揭開這個秘密。鑒于分子是由基因產(chǎn)生的，圖靈正在尋找一種解釋，來說明化學(xué)溶液可能產(chǎn)生生物的模式。

　　他的理論的第一個主要目標(biāo)是嘗試解決Phyllotaxis的經(jīng)典問題，即植物上的葉片排列。這個問題的特點(diǎn)之一是斐波那契數(shù)列1、2、3、5、8、13、21的自然出現(xiàn)，這在開普勒時代就已為人所知。因此，已經(jīng)確定了數(shù)學(xué)可以發(fā)揮的作用. (更多關(guān)于斐波那契數(shù)列的信息可見"生活中的斐波那契數(shù)列" 里的條目3)

　　圖靈還提出，由于化學(xué)信號，動物身上的標(biāo)記模式遵循數(shù)學(xué)規(guī)則。盡管最近生物學(xué)家的興趣被重新喚起，這一觀點(diǎn)爭議仍然很大。利用他的理論，日本的研究人員在斑馬魚的圖案中觀察到了圖靈所預(yù)測的變化。