圖靈機與計算問題(轉載)

2013年11月27日?? 綜合?? 共 21646字 ? 字號?小?中?大???評論關閉

張江(email:?jakezj@163.com)

自從20世紀30年代以來，圖靈機、計算這些重要的概念在科學的天空中就一直閃爍著無限的光彩。尤其是近年來量子計算機、生物計算機、DNA計算等領域的創(chuàng)新工作引起了世人的廣泛關注。我們不禁問這樣的問題，國外究竟為什么能發(fā)明出這些各式各樣的計算機呢？這些意味著什么呢？其實這一切的源頭都來源于計算理論。國內(nèi)在介紹計算理論方面的教材雖然有不少，但一般都比較深奧難懂。所以我覺得很有必要對這些內(nèi)容進行科普。于是嘗試寫下這么一篇文章，希望我的文章能夠讓你更加清楚、透徹的理解圖靈機、計算等等一些基本而重要的概念，并洞悉到這些概念的本質(zhì)和深遠涵義。?
本篇文章大體上可以分成四部分：首先給大家講一講關于圖靈、哥德爾等科學家的故事；然后正式引入圖靈機的概念，為了對這個概念有比較直觀的理解，我采用了一個人工生命：“小蟲”的比喻來敘述。接下來，文章介紹了跟圖靈機有關的概念：什么是模擬，什么是“萬能計算機”等等；最后是關于圖靈停機問題的探討，我個人認為很有可能未來對科學的重大突破都來源于對圖靈停機問題的深入理解。在行文過程中，我除了用自己的方式介紹一些現(xiàn)有的基本概念之外（為了盡量表達得清楚明白，我不得不放棄理論論證的嚴格性），還探討了很多我認為別人沒有探討的問題，這些問題多是我自己的思考結果，而它們沒有經(jīng)過科學的驗證。在這部分內(nèi)容上我都標上了*號，希望你能有選擇的看待這些問題和觀點。?
一、故事?
任何科學思想、科學概念的誕生都有它的背景，在背景中往往有很多迷人的故事。

計算理論可以追溯到1900年，當時著名的大數(shù)學家希爾伯特在世紀之交的數(shù)學家大會上給國際數(shù)學界提出了著名的23個數(shù)學問題。其中第十問題是這樣的：存在不存在一種有限的、?機械的步驟能夠判斷“丟番圖方程”是否存在解？這里就提出來了有限的、機械的證明步驟的問題，用今天的話說就是算法。但在當時，人們還不知道“算法”是什么。實際上，當時數(shù)學領域中已經(jīng)有很多問題都是跟“算法”密切相關的，因而，科學的?“算法”?定義呼之欲出。之后到了30年代的時候，終于有兩個人分別提出了精確定義算法的方法，一個人是圖靈，一個人是丘奇。而其中圖靈提出來的圖靈機模型直觀形象，于是很快得到了大家的普遍接受。??不知道你是否聽說過圖靈這個名字。可能有些人知道牛頓，知道愛因斯坦，甚至知道馮?諾依曼，但不知道圖靈。然而圖靈的貢獻絕對不亞于這些科學大師。圖靈最大的貢獻就是把?算法這樣一個基本的、深刻的概念用他的圖靈機模型講清楚了。正是因為圖靈奠定的理論基?礎，人們才有可能發(fā)明20世紀以來甚至是人類有史以來最偉大的發(fā)明：計算機。因此人們?稱圖靈為：計算機理論之父。??圖靈生活的年代經(jīng)歷了第二次世界大戰(zhàn)。在二戰(zhàn)期間他曾經(jīng)為英國政府效力成功破譯了德國的密碼，因而為英國做出了突出貢獻。其實也正是因為二戰(zhàn)，英國政府才肯掏錢讓圖靈?制造最原始的計算機，當然這種計算機是專門用來破譯密碼用的，而不是我們現(xiàn)在用的通用?計算機。（有一部片子叫《密碼迷情》英文名是《enigma》就是根據(jù)圖靈當時破譯德國密碼?的故事改編的，大家有興趣可以去找一找。）??圖靈這個人很古怪，只喜歡自己一個人悶頭研究，不喜歡與別人交流。并且據(jù)說他還是?一個同性戀者。要知道在當時的英國，同性戀行為可是大逆不道的。最后，在他事業(yè)剛剛達到頂風的時候，他自殺了。為了紀念這個偉大的學者，計算機界設立了最高榮譽獎：ACM?圖靈獎。??

圖靈機的產(chǎn)生一方面奠定了現(xiàn)代數(shù)字計算機的基礎（要知道后來馮諾依曼就是根據(jù)圖靈?的設想才設計出第一臺計算機的）。另一方面，根據(jù)圖靈機這一基本簡潔的概念，我們還可?以看到可計算的極限是什么。也就是說實際上計算機的本領從原則上講是有限制的。請注意，這里說到計算機的極限并不是說它不能吃飯、掃地等硬件方面的極限，而是僅僅就從信息處?理這個角度，計算機也仍然存在著極限。這就是圖靈機的停機問題。這個問題在圖靈看來更?加重要，在他當年的論文中，其實他是為了論證圖靈停機問題才“捎帶手”提出了圖靈機模?型的。??
提到了圖靈停機問題，我不禁又要提一提哥德爾定理、羅素悖論、康托爾的集合論等?等一系列大事兒。早在19世紀末的時候，康托爾為集合論做了奠基性的研究。要知道，數(shù)?學雖然五花八門，但是人們發(fā)現(xiàn)，運用集合這個概念可以概括所有的數(shù)學，也就是說集合是一切數(shù)學的基礎。因而如果為集合論奠定了公理化的基礎，也就等于為數(shù)學奠定了基礎。康?托爾就是做了這方面的貢獻。另外，他為了證明實數(shù)的個數(shù)比自然數(shù)多這個結論，發(fā)明了一?種被稱為“對角線刪除”的證明方法。沒想到的是，這個方法影響非常深廣，直到后來的圖?靈停機問題、哥德爾定理其實都是該方法的不同延伸。??

19世紀末的人們忙于為基于集合論的數(shù)學建立公理體系大廈。然而就當這座大廈即將?完工的時候，一件可怕的事情發(fā)生了，羅素提出來的羅素悖論粉碎了數(shù)學家的夢想。關于羅?素悖論的一個通俗化版本是：“村子里有一個理發(fā)師，他給自己定了一條規(guī)矩：‘不給那些所有給自己理發(fā)的人理發(fā)’。現(xiàn)在就要問，這個理發(fā)師該不該給自己理發(fā)？”。如果你嘗試回答?這個問題就會發(fā)現(xiàn)奇怪的事情：這個問題本身似乎是不可能的！正是因為這種奇怪的邏輯，?哲學家羅素才顛覆了整個數(shù)學大廈的基礎！??
因為集合論中存在著矛盾，所以整個數(shù)學體系存在著根本性的矛盾，然而具有諷刺意 味的是，數(shù)學一直以嚴格著稱！這種感覺就好像正當你得意洋洋的時候有人突然閃了你一個?耳光！人們在一陣慌亂之后開始逐漸穩(wěn)下陣角尋找避免羅素悖論產(chǎn)生的方法，并總希望通過細心的選擇數(shù)學公理能夠?qū)㈩愃屏_素悖論這樣的怪物一勞永逸的排除精確數(shù)學體系之外。這?就是后來希爾伯特提出來一套數(shù)學綱領的原因，他希望找到一套公理體系能夠排除悖論，并?挽救純粹而美麗無暇的數(shù)學。雖然希爾伯特沒能完成他的夢想，但他堅信夢想是對的。??
然而，沒過多少年，一個名不見經(jīng)傳的年輕邏輯學家哥德爾提出來的定理卻徹底粉碎?了希爾伯特的夢。這就是后來著名的哥德爾定理！該定理大致上說：任何一個數(shù)學的公理化?體系都不是“完美的”。換個角度說，任何數(shù)學公理化系統(tǒng)都是死的，它總需要人為地從外界注入新的公理進去才能讓它日趨完善，而它自己并不能完全自動避免矛盾產(chǎn)生。哥德爾定?理可以說整個扭轉了人們的世界觀。因為被認為最“完美”最“純粹”的數(shù)學都是不完全的，?那么純粹完美的世界也應該不存在。哥德爾定理還指出了“理性”和“分析”方法的極限。?這才是后來人們步入到了“綜合”時代的部分原因。更有趣的是，哥德爾用來證明他定理的?方法正和康托爾證明實數(shù)比自然數(shù)多、圖靈停機問題以及羅素悖論的方法是一脈相承的。??所有這些都是20世紀上半個世紀發(fā)生的大事，后來發(fā)生了什么？計算機出現(xiàn)了、信息?時代來臨了，似乎科學技術是萬能的，它們總會改善我們的生活，滿足我們的欲望。漸漸的，?人們似乎淡忘了圖靈、歌德爾、康托爾等等大師們的思想了。然而近年來隨著復雜性科學的?研究，人們卻又有了重拾這些相對古老而根本問題的跡象了！??
二、圖靈機??
下面言歸正傳，我們開始講圖靈機的概念。我先把圖靈機的模型給你，雖然有些無趣，?不過請堅持看下去，我會在下面運用大家比較好理解的形式重新解釋的。在這里你僅僅需要?認識它的輪廓。一個圖靈機是形如下面的一個裝置：??

??

這個裝置由下面幾個部分組成：一個無限長的紙帶，一個讀寫頭。（中間那個大盒子），?內(nèi)部狀態(tài)（盒子上的方塊，比如A,B,E,H），另外，還有一個程序?qū)@個盒子進行控制。這?個裝置就是根據(jù)程序的命令以及它的內(nèi)部狀態(tài)進行磁帶的讀寫、移動。??
它工作的時候是這樣的：從讀寫頭在紙帶上讀出一個方格的信息，并且根據(jù)它當前的內(nèi)?部狀態(tài)開始對程序進行查表，然后得出一個輸出動作，也就是是否往紙帶上寫信息，還是移?動讀寫頭到下一個方格。程序也會告訴它下一時刻內(nèi)部狀態(tài)轉移到哪一個。??
具體的程序就是一個列表，也叫做規(guī)則表，是這樣的：??

?

因此，圖靈機只要根據(jù)每一時刻讀寫頭讀到的信息和當前的內(nèi)部狀態(tài)進行查表就可以確?定它下一時刻的內(nèi)部狀態(tài)和輸出動作了。??
圖靈機就是這么簡單！不可思議吧？而只要你變化它的程序（也就是上面的規(guī)則表），?那么它就可能為你做任何計算機能夠完成的工作。因此可以說，圖靈機就是一個最簡單的計?算機模型！??
也許，你會覺得圖靈機模型太簡單，怎么可能完成計算機的復雜任務呢？問題的關鍵是?如何理解這個模型。??

三、如何理解圖靈機？??

1、小蟲的比喻??

我們不妨考慮這樣一個問題。假設一個小蟲在地上爬，那么我們應該怎樣從小蟲信息?處理的角度來建立它的模型？??
首先，我們需要對小蟲所在的環(huán)境進行建模。我們不妨就假設小蟲所處的世界是一個無?限長的紙帶，這個紙帶上被分成了若干小的方格，而每個方格都僅僅只有黑和白兩種顏色。?
很顯然，這個小蟲要有眼睛或者鼻子或者耳朵等等感覺器官來獲得世界的信息，我們不妨把?模型簡化，假設它僅僅具有一個感覺器官：眼睛，而且它的視力短得可憐，也就是說它僅僅能夠感受到它所處的方格的顏色。因而這個方格所在的位置的黑色或者白色的信息就是小蟲?的輸入信息。??
另外，我們當然還需要為小蟲建立輸出裝置，也就是說它能夠動起來。我們?nèi)匀豢紤]最?簡單的情況：小蟲的輸出動作就是往紙帶上前爬一個方格或者后退一個方格。??
僅僅有了輸入裝置以及輸出裝置，小蟲還不能動起來，原因很簡單，它并不知道該怎樣?在各種情況下選擇它的輸出動作。于是我們就需要給它指定行動的規(guī)則，這就是程序！假設?我們記小蟲的輸入信息集合為I={黑色，白色}，它的輸出可能行動的集合就是：O={前移，后移}，那么程序就是要告訴它在給定了輸入比如黑色情況下，它應該選擇什么輸出。因而，?一個程序就是一個從I集合到O集合的映射。我們也可以用列表的方式來表示程序，比如：??
程序1：??
輸入?輸出??
黑色?前移??
白色?后移??
這個程序非常簡單，它告訴小蟲當讀到一個黑色方格的時候就往前走一個方格，當讀到?一個白色方格的時候就后退一個格。??
我們不妨假設，小蟲所處的世界的一個片斷是：黑黑黑白白黑白……，小蟲從左端開?始。??
那么小蟲讀到這個片斷會怎樣行動呢？它先讀到黑色，然后根據(jù)程序前移一個方格，?于是就會得到另外一個黑色信息，這個時候它會根據(jù)程序再次前移一個方格，仍然是黑色，?再前移，這個時候就讀到白色方格了，根據(jù)程序它應該后退一個格，這個時候輸入就是黑色了，前移，白色，后移……，可以預見小蟲會無限的循環(huán)下去。??
然而，現(xiàn)實世界中的小蟲肯定不會這樣傻的在那里無限循環(huán)下去。我們還需要改進這個?最簡單的模型。首先，我們知道小蟲除了可以機械地在世界上移動以外，還會對世界本身造?文本框:?……文本框:?開始?成影響，因而改變這個世界。比如蟲子看到旁邊有食物，它就會把那個東西吃掉了。在我們這個模型中，也就相當于我們必須假設小蟲可以改寫紙帶上的信息。因而，小蟲可能的輸出?動作集合就變成了：O={前移，后移，涂黑，涂白}。這個時候，我們可以把程序1改為比?如：??
程序2：??
輸入?輸出??
黑 ? ? 前移??
白 ? ? 涂黑??
紙帶是黑黑白白黑……，小蟲會怎樣行動呢？下面的圖表示出了這個例子中每一步小蟲?的位置（標有圓點的方格就是小蟲的當前位置），以及紙帶的狀況。??
開始：小蟲在最左邊的方格，根據(jù)程序的第一行，讀入黑色應該前移。??
第二步：仍然讀入黑，根據(jù)程序的第一行，前移。??
第三步：這個時候讀入的是白色，根據(jù)程序的第二行，應該把這個方格涂黑，而沒有其他的動作。假設這張圖上方格仍然沒有涂黑，而在下一時刻才把它表示出來。??
第四步：當前方格已經(jīng)是黑色的，因此小蟲讀入黑色方格，前移。??
第五步：讀入白色，涂黑方格，原地不動。??
第六步：當前的方格已經(jīng)被涂黑，繼續(xù)前移。??
第七步：讀入黑色，前移??
小蟲的動作還會持續(xù)下去……。我們看到，小蟲將會不停的重復上面的動作不斷往前走，?并會把所有的紙帶涂黑。??
顯然，你還可以設計出其他的程序來，然而無論你的程序怎么復雜，也無論紙帶子的情況如何，小蟲的行為都會要么停留在一個方格上，要么朝一個方向永遠運動下去，或者就是?在幾個方格上來回打轉。然而，無論怎樣，小蟲比起真實世界中的蟲子來說，還有一個致命?的弱點：那就是如果你給它固定的輸入信息，它都會給你固定的輸出信息！因為我們知道程?序是固死的，因此，每當黑色信息輸入的時候，無論如何它都僅僅前移一個方格，而不會做?出其他的反應。它似乎真的是機械的！ ?

如果我們進一步更改小蟲模型，那么它就會有所改進，至少在給定相同輸入的情況下，?小蟲會有不同的輸出情況。這就是加入小蟲的內(nèi)部狀態(tài)！我們可以作這樣的一個比喻：假設?黑色方格是食物，蟲子可以吃掉它，而當吃到一個食物后，小蟲子就會感覺到飽了。當讀入的信息是白色方格的時候，雖然沒有食物但它仍然吃飽了，只有當再次讀入黑色時候它才會?感覺到自己饑餓了。因而，我們說小蟲具有兩個內(nèi)部狀態(tài)，并把它內(nèi)部狀態(tài)的集合記為：?
S={饑餓，吃飽}。這樣小蟲行為的時候就會不僅根據(jù)它的輸入信息，而且也會根據(jù)它當前?的內(nèi)部狀態(tài)來決定它的輸出動作，并且還要更改它的內(nèi)部狀態(tài)。而它的這一行動仍然要用程?序控制，只不過跟上面的程序比起來，現(xiàn)在的程序就更復雜一些了，比如：??
程序3：??
輸入?當前內(nèi)部狀態(tài)?輸出?下時刻的內(nèi)部狀態(tài)??
黑 ? ? ? 饑餓 ? ? ? ? ? ? 涂白 ? ? ? ? 吃飽??
黑 ? ? ? ?吃飽 ? ? ? ? ? ?后移 ? ? ? ? 饑餓??
白 ? ? ? ?饑餓 ? ? ? ? ? ?涂黑 ? ? ? ? 饑餓??
白 ? ? ? ?吃飽 ? ? ? ? ? ?前移 ? ? ? ? ?吃飽??
這個程序復雜多了，有四行，原因是你不僅需要指定每一種輸入情況下小蟲應該采取?的動作，而且還要指定在每種輸入和內(nèi)部狀態(tài)的組合情況下小蟲應該怎樣行動。看看我們的?蟲子在讀入黑白白黑白……這樣的紙帶的時候，會怎樣？仍然用下面的一系列圖來表示，灰?
色的圓點表示饑餓的小蟲，白色的圓點表示它吃飽了。為了清晰，我們把小蟲將要變成的狀?態(tài)寫到了圖的下一行。??
假定它仍然從左端開始，而且開始的時候小蟲處于饑餓狀態(tài)。這樣讀入黑色，當前饑?餓狀態(tài)，根據(jù)程序第一行，把方格涂白，并變成吃飽（這相當于把那個食物吃了，注意吃完?后，小蟲并沒動）。??
第二步：當前的方格變成了白色，因而讀入白色，而當前的狀態(tài)是吃飽狀態(tài)，那么根?據(jù)程序中的第四條前移，仍然是吃飽狀態(tài)；

第三步：讀入白色，當前狀態(tài)是吃飽，因而會重復第二步的動作。??
涂白方格，變成吃飽:?前移，仍然吃飽:?前移，保持吃飽?

第四步：仍然重復上次的動作。??
第五步：讀入黑色，當前狀態(tài)是吃飽，這時候根據(jù)程序的第二行應該后移方格，并轉?入饑餓狀態(tài)；??
第六步：讀入白色，當前饑餓狀態(tài)，根據(jù)程序第三行應該涂黑，并保持饑餓狀態(tài)（各?位注意，這位小蟲似乎自己吐出了食物！）；??
第七步，讀入黑色，當前饑餓，于是把方格涂白，并轉入吃飽狀態(tài)（呵呵，小蟲把剛?剛自己吐出來的東西又吃掉了！）。??
第八步，讀入白色，當前吃飽，于是前移，保持吃保狀態(tài)。??
這時候跟第四步的情況完全一樣了，因而小蟲會完全重復5、6、7、8步的動作，并永?遠循環(huán)下去。似乎最后的黑色方格是一個門檻，小蟲無論如何也跨越不過去了。??
小蟲的行為比以前的程序復雜了一些。盡管從長期來看，它最后仍然會落入機械的循環(huán)?或者無休止的重復。然而這從本質(zhì)上已經(jīng)與前面的程序完全不同了，因為當你輸入給小蟲白?色信息的時候，它的反應是你不能預測的！它有可能涂黑方格也有可能前移一個。當然前提
是你不能打開小蟲看到它的內(nèi)部結構，也不能知道它的程序，那么你所看到的就是一個不能?預測的滿地亂爬的小蟲。如果小蟲的內(nèi)部狀態(tài)數(shù)再增多呢，那么它的行為會更加的不可預測！??
好了，如果你已經(jīng)徹底搞懂了我們的小蟲是怎么工作的，那么你已經(jīng)明白了圖靈機的工?作原理了！因為從本質(zhì)上講，最后的小蟲模型就是一個圖靈機！??

2、如何理解圖靈機模型*??
剛才用小蟲說明了圖靈機的工作原理，相信你的第一個反映就是，這樣的模型太簡單了！?
他根本說明不了現(xiàn)實世界中的任何問題！下面，我就要試圖說服你，圖靈機這個模型是偉大?的！??
首先，我想說的是，其實我們每一個會決策、會思考的人就可以被抽象的看成一個圖靈?機。??
?前移，保持吃飽:?涂白，轉入吃飽:?……:?前移，保持吃飽:?后移，變成饑餓:?涂黑，保持饑餓
為什么可以做這種抽象呢？首先我們可以考慮擴展剛才說的小蟲模型。因為小蟲模型是?
以一切都簡化的前提開始的，所以它的確是太太簡單了。然而，我們可以把小蟲的輸入集合、?輸出行動集合、內(nèi)部狀態(tài)集合進行擴大，這個模型就一下子實用多了。首先，小蟲完全可以處于一個三維的空間中而不是簡簡單單的紙帶。并且小蟲的視力很好，它一下子能讀到方圓?500米的信息，當然，小蟲也可以擁有其他的感覺器官，比如嗅覺、聽覺等等，而這些改變?都僅僅是擴大了輸入集合的維數(shù)和范圍，并沒有其他更本質(zhì)的改變。同樣道理，小蟲可能的?輸出集合也是異常的豐富，它不僅僅能移動自己，還可以盡情的改造它所在的自然界。進一?步的，小蟲的內(nèi)部狀態(tài)可能非常的多，而且控制它行為的程序可能異常復雜，那么小蟲會有?什么本事呢？這就很難說了，因為隨著小蟲內(nèi)部的狀態(tài)數(shù)的增加，隨著它所處環(huán)境的復雜度?的增加，我們正在逐漸失去對小蟲行為的預測能力。但是所有這些改變?nèi)匀粵]有逃出圖靈機?的模型：輸入集合、輸出集合、內(nèi)部狀態(tài)、固定的程序！就是這四樣東西抓住了小蟲信息處?理的根本。??
我們?nèi)四懿荒芤脖贿@樣的抽象呢？顯然，輸入狀態(tài)集合就是你所處的環(huán)境中能夠看到、?聽到、聞到、感覺到的所有一起，可能的輸出集合就是你的每一言每一行，以及你能夠表達?出來的所有表情動作。內(nèi)部狀態(tài)集合則要復雜得多。因為我們可以把任意一個神經(jīng)細胞的狀?態(tài)組合看作是一個內(nèi)部狀態(tài)，那么所有可能的神經(jīng)細胞的狀態(tài)組合將是天文數(shù)字！??
似乎你會說，這個模型根本不對，還有很多思維本質(zhì)的東西沒有概括進去。比如記憶?問題，人有記憶，圖靈機有么？其實，只要圖靈機具有了內(nèi)部狀態(tài)，它就相應的具有了記憶。?
比如上面講到的具有饑餓和吃飽兩種狀態(tài)的小蟲就會記住它所經(jīng)歷過的世界：如果吃到食物?就用吃飽狀態(tài)來“記住”吃過的食物。什么是記憶呢？假如你經(jīng)歷了一件事情并記住了它，?那么只要你下一次的行動在相同條件下和你記住這件事情之前的行動不一樣了，就說明該事?情對你造成了影響，也就說明你確實記住了它。??
學習的問題反映在模型中了么？學習是怎么回事兒呢？似乎圖靈機模型中不包括學習，因為學習就意味著對程序的改變，而圖靈機是不能在運行過程中改變它的程序的。然而，?我們不難假設，你實際上并不能打開一個人的腦袋來看，所以它的實際程序規(guī)則你是不知道?
的。很有可能一個圖靈機的規(guī)則沒有改變，只不過激活了它的某些內(nèi)部狀態(tài)，因而它的行為?發(fā)生了本質(zhì)上的變化，盡管給它相同的輸入，它給出了完全不同的輸出，因而在我們看來，?它似乎會學習了！而實際上，這個圖靈機的程序一點都沒變。??
還有很多很多現(xiàn)象似乎都能被圖靈機包括，什么是人類的情緒、情感？你完全可以把?它看作是某種內(nèi)部狀態(tài)，因而處于心情好的情緒下，你的輸入輸出是一套規(guī)則，而心情不好?的時候則完全是另一套。這仍然沒有逃出圖靈機的模型范圍。??
接下來的問題就是我們?nèi)说乃季S究竟是不是和圖靈機一樣遵循固定的程序呢？這個問?題似乎初看是不可能的，因為人的行為太不固定了！你不可預言它！然而我會爭辯道，無論?如何神經(jīng)元傳遞信息、變化狀態(tài)的規(guī)律都是固定的，可以被程序化的，那么作為神經(jīng)元的整?
體：腦的運作必然也要遵循固定的規(guī)則也就是程序了。那么，如果是這樣，正如圖靈相信的，?人腦也不會超越圖靈機這個模型，所以，人工智能也必然是可能的！然而，我認為針對這個?問題的答案很有可能沒有這么簡單，我們將在最后詳細討論這個問題。??
無論如何，我相信你已經(jīng)能夠體會到了，圖靈機模型實際上是非常強有力的！??
三、計算??
1、什么是計算??
說了這么多，雖然也許你已經(jīng)了解到了圖靈機的威力，也許還將信將疑，然而，你肯定?仍然看不出來圖靈機和計算有什么關系。而實際上，圖靈機是一個理論計算機模型，它最主?要的能耐還是在于計算上！所以，下面我們就來看看什么是計算！??
我可以先給出一個很摩登的對計算概念的理解：廣義上講，一個函數(shù)變化如把x變成了?f(x)就是一個計算！如果我們把一切都看作是信息，那么更精確的講，計算就是對信息的變?換！如果采用這種觀點，你會發(fā)現(xiàn)，其實自然界充滿了計算！如果我們把一個小球扔到地上小球又彈起來了，那么大地就完成了一次對小球的計算。因為你完全可以把小球的運動都抽?象成信息，它無非是一些比如位置、速度、形狀等等能用信息描述的東西嘛，而大地把小球?彈起來就無非是對小球的這些信息進行了某種變換，因而大地就完成了一次計算！你可以把?整個大地看作是一個系統(tǒng)，而扔下去的小球是對這個系統(tǒng)的輸入，那么彈回來的小球就是該?系統(tǒng)的輸出，因而也可以說，計算就是某個系統(tǒng)完成了一次從輸入到輸出的變換！??這樣理解不要緊，你會發(fā)現(xiàn)，現(xiàn)實世界到處都是計算了！因為我們完全可以把所有的自然界存在的過程都抽象成這樣的輸入輸出系統(tǒng)，所有的大自然存在的變量都看作是信息，因?而計算無處不在！也的確，正是采取了這樣的觀點，國外才有可能發(fā)明什么DNA計算機、?生物計算機、量子計算機這些新鮮玩藝！因為人家把DNA的化學反應、量子世界的波函數(shù)?變換都看作是計算了，自然就會人為地把這些計算組合起來構成計算機了。然而，似乎我們?的理論家們還在力圖證明關于圖靈機的某個定理呢，卻完全沒有意識到計算其實就是這樣簡?單！??
下面回到圖靈機！為什么說圖靈機是一個計算的裝置呢？很簡單，圖靈機也是一個會對?輸入信息進行變換給出輸出信息的系統(tǒng)。比如前面說的小蟲，紙帶上的一個方格一個方格的?顏色信息就是對小蟲的輸入，而小蟲所采取的行動就是它的輸出。不過這么看，你會發(fā)現(xiàn)，?似乎小蟲的輸出太簡單了。因為它僅僅就有那么幾種簡單的輸出動作。然而，不要忘了，復?雜性來源于組合！雖然每一次小蟲的輸出動作很簡單，然而當把所有這些輸出動作組合在一?起，就有可能非常復雜！比如我們可以把初始時刻的紙帶看作是輸入信息，那么經(jīng)過任意長?的時間比如說100年后，小蟲通過不斷的涂抹紙帶最后留下的信息就是輸出信息了。那么小?蟲完成的過程就是一次計算。事實上，在圖靈機的正規(guī)定義中，存在一個所謂的停機狀態(tài)，?當圖靈機一到停機狀態(tài)，我們就認為它計算完畢了，因而不用費勁的等上100年。??
2、計算的組合??
更有意思的是，我們可以把若干個計算系統(tǒng)進行合并構成更大的計算系統(tǒng)。比如還是那?個小球吧，如果往地上放了一個蹺蹺板，這樣小球掉到地上會彈起這個蹺蹺板的另一端，而?蹺蹺板的另一邊可能還是一個小球，于是這個彈起的小球又會砸向另一個蹺蹺板……。??
我們自然可以通過組合若干圖靈機完成更大更多的計算，如果把一個圖靈機對紙帶信息?變換的結果又輸入給另一臺圖靈機，然后再輸入給別的圖靈機……，這就是把計算進行了組?合！也許你還在為前面說的無限多的內(nèi)部狀態(tài)，無限復雜的程序而苦惱，那么到現(xiàn)在，你不?難明白，實際上我們并不需要寫出無限復雜的程序列表，而僅僅將這些圖靈機組合到一起就?可以產(chǎn)生復雜的行為了。??
有了圖靈機的組合，我們就能夠從最簡單的圖靈機開始構造復雜的圖靈機。那么最簡單?的圖靈機是什么呢？我們知道最簡單的信息就是0和1，而最簡單的計算就是對0或1進行?布爾運算。而布爾運算本質(zhì)上其實就三種：與、或、非。從最簡單的邏輯運算操作最簡單的?
二進制信息出發(fā)我們其實可以構造任意的圖靈機！這點不難理解：任何圖靈機都可以把輸入、?輸出信息進行01的編碼，而任何一個變換也可以最終分解為對01編碼的變換，而對01編?碼的所有計算都可分解成前面說的三種運算。也許，現(xiàn)在你明白了為什么研究計算機的人都?要去研究基本的布爾電路。奧秘就在于，用布爾電路可以組合出任意的圖靈機！??
3、征服無限的方法！??

回憶你小時候是如何學會加法運算的。剛開始的時候，你僅僅會死記硬背。比如你記住?了1+1=2，記住了2+4=6，……。然而無論你記住多少固定數(shù)字的運算，你都不叫學會了加法。原因很簡單，假如你記住了n對數(shù)的加法，那么我總會拿出第n+1對數(shù)是你沒有記住?的，因此你還是不會計算。原則上。自然數(shù)的個數(shù)是無窮的，所以任何兩個數(shù)的加法可能結果也是無窮的，而如果采用死記硬背的方法，我們頭腦怎么可能記住無窮數(shù)字的計算法則?呢？但是隨著年齡的增長，你畢竟還是最終學會了加法運算！說來奇怪，你肯定明白其實加?
法運算并不需要記住所有數(shù)字的運算結果，而僅僅需要記住10以內(nèi)的任意兩個數(shù)的和，并?且懂得了進位法則就可以了。??
你是怎么做到的呢？假設要計算32+69的加法結果，你會把32寫到一行，把69寫到?下一行，然后把他們對齊。于是你開始計算2+9=11，進一位，然后計算3+6=9，再計算9+1=10?再進一位，最后，再把計算的這些每一位的結果都拼起來就是最終的答案101。這個簡單例?
子給我們的啟發(fā)就是：作加法的過程就是一個機械的計算過程，這里輸入就是32和69這兩?個數(shù)字，輸出就是101。而你的程序規(guī)則就是具體的把任意兩個10以內(nèi)的數(shù)求和。這樣，?根據(jù)固定的加法運算程序你可以計算任兩個數(shù)的加法了。??
不知你發(fā)現(xiàn)了沒有，這個計算加法的方法能夠讓你找到運用有限的規(guī)則應對無限可能情?況的方法！我們剛才說了，實際上自然數(shù)是無限的，這樣，所有可能的加法結果也是無限的。?
然而運用剛才說的運算方法，無論輸入的數(shù)字是多少，只要你把要計算的數(shù)字寫下來了，就?一定能夠計算出最終的結果，而無需死記硬背所有的加法！??
因而，可以說計算這個簡單的概念，是一種用有限來應對無限的方法！我們再看一個?例子：假如給你一組數(shù)對：1,2?3,6?5,10?18,36，就這4對，這時問你102對應的數(shù)是多?少？很顯然，如果僅僅根據(jù)你掌握的已知數(shù)對的知識，是不可能知道答案的，因為你的知識庫里面沒有存放著102對應數(shù)字的知識。然而，如果你掌握了產(chǎn)生這組數(shù)對的程序法則，也?就是看到如果第一個數(shù)是x，那么第二個數(shù)就是2x的話，你肯定一下子就算出102對應的?是204了。也就是說，你實際上運用2x這兩個字符就記住了無限的諸如1,2?3,6?102,204?
所有這樣的數(shù)對。??
這看起來似乎很奇怪。我怎么可能運用有限的字符來應對無限種可能呢？實際上，當?沒有人問你問題的時候，你存儲的2x什么也沒有，而當我問你102對應的是多少？我就相?當于給你輸入了信息：102，而你僅僅是根據(jù)這個輸入信息102進行一系列的加工變換得到了輸出信息204。因而輸入信息就好比是原材料，而你的程序規(guī)則就是加工的方法，只有在?原材料上進行加工，你才能輸出最終產(chǎn)品。??
這讓我不禁想起了專家系統(tǒng)方法。其實專家系統(tǒng)就是一個大的規(guī)則庫。也就相當于存?儲了很多很多的1,2?3,6?5,10這樣特殊的規(guī)則對。而無論它存儲的東西再多，總歸會是有限?的，你只要找到一個它沒有存儲到的問題，它就無能為力了。因而專家系統(tǒng)就會在你問到?102對應是多少的時候失敗！如何解決問題？人們想出了很多方法，就比如元規(guī)則的方法，?其實元規(guī)則就相當于剛才所說的計算加法的程序，或者2x這樣的東西。運用元規(guī)則的確可?以應對無限種情況了。所以，這就是為什么你問計算機任何兩個數(shù)相加是多少，它總能給 你正確的答案的原因，雖然它不必記住所有這些加法對的信息。??然而僅僅是元規(guī)則就能解決所有問題么？??
假如給你三組數(shù)對，排列成一個表：??
1,2?3,6?4,8?100,200??
3,9?2,6?8,24?100,300??
1,4?2,8?3,12?100,400??
那么問你在第6行上，3這個數(shù)字對應的是多少？我們先要找出第一行的規(guī)律是2x沒?有疑問，第二行呢？是3x，第三行是4x，那么第6行就應該是7x了，因而在第6行上3?

應該對應的是21了！這里跟前面不太一樣的是，雖然我們得到了每一行的規(guī)則比如第一行?的2x，但是隨著行數(shù)的增加，這個規(guī)則本身也變化了，因而第2行是3x，第3行是4x等等，?因而我們又得到了一個規(guī)則本身的規(guī)則，即如果行數(shù)是n的話，那么這一行的規(guī)則就是?(n+1)x。我們顯然能夠根據(jù)輸入的n和x計算出數(shù)值。把這個道理放到專家系統(tǒng)里面，這種?原理就是元規(guī)則的規(guī)則，元規(guī)則的元規(guī)則……，應該是無窮的！然而專家系統(tǒng)本身并不會自動的歸納這些規(guī)則，人必須事先把這些元規(guī)則寫到程序里，這也就是專家系統(tǒng)最大的弊端。?
而我們?nèi)怂坪蹩偰茉谝恍﹤€別的事件中歸納出規(guī)則。進一步問，機器可以歸納么？這就相當?于說：可以為歸納方法編出程序么？這也是一個很有趣的問題，下面將要詳細討論！可以設?想，假如我們找到了真正歸納的方法，那么編寫出這樣的程序，它就會一勞永逸的自己進行?學習歸納了。我們完全再也不用給他編制程序和規(guī)則了。這正是人工智能的終極目標！??
4、歸納*??
記得金大俠在他的一本武俠小說：《倚天屠龍記》中曾講述了這樣一段故事：武林泰斗?張三豐在情急之下要把他新創(chuàng)的武功“太極拳”傳授給新起之秀張無忌。張無忌除了有一身?精湛的“內(nèi)功修為”以外還對武學具有極高的悟性。因而當張三豐給他打過一趟太極拳以后，?
他就把所有的招式全部記下來了并且當場把所學的太極拳重新再打給張三豐看。在張無忌練?拳的過程中，張三豐反復問他一個問題：“你已經(jīng)忘掉幾招了？”。他的回答令其他人異常不?解，因為他越在那里揣摩太極拳的奧秘，忘記的招數(shù)也越來越多。旁邊的人不明白，這樣的?學法忘的這么快，怎么可能學會武功呢？然而，沒過多長時間，張無忌說已經(jīng)忘掉了所有的?招式。張三豐笑著說：“不錯，你終于學會了‘太極拳’”。??
從這個例子中，我們看到了什么？張無忌之所以能學會太極拳，正是因為他已經(jīng)能夠從?具體的一招一式之中抽象出了更高一層次的武學規(guī)律，因而，當他把所有的有形的武功招數(shù)?都忘記的時候，已經(jīng)掌握了太極拳的精髓。而太極武功講究的就是借力打力，以柔克剛。說?白了就是事先并沒有固定招式存在，而等到敵人向我進攻的時候我再動態(tài)的生成破解的招?術。??
用到圖靈機模型中，我們不難發(fā)現(xiàn)，如果把具體的武功招術比喻成一些輸入，而應對招?術比喻成圖靈機的輸出，那么太極所講究的借力打力、以柔克剛的方法其實就是類似上節(jié)講?過的2x這樣的圖靈程序！因而張無忌學太極拳的過程就是從特殊的輸入輸出提升到了一般?
的算法的過程。也可以說，張無忌運用了歸納學習法！??
然而，仔細觀察上一節(jié)的敘述，我們會發(fā)現(xiàn)。雖然圖靈機能夠?qū)?x這樣的法則計算得?出結果，但是抽象出2x本身并不是機器自動產(chǎn)生的，而是需要我們外在的人編程進去。那?么，面對這樣的問題，究竟圖靈機能不能像張無忌一樣進行歸納思維呢？??
可以設想，如果計算機真有了張無忌那兩下子，我們?nèi)祟惪梢∈聝憾嗔?#xff01;我們甚至不?需要為計算機編程序，它就會自動的從若干個具體事例中歸納出一般的通用規(guī)律來。然而，?究竟計算機能不能具有真正的歸納能力呢？讓我們來仔細考慮一下這個問題。??
我們說如果計算機能自動歸納，也就意味著我們可以為歸納方法來編寫一段程序P。這?個程序可以理解為輸入的是一些特殊的數(shù)對，輸出的是能夠生成這些數(shù)對的程序。也就是說?輸入具體的“招術”，輸出的是這些“招術”的一般規(guī)律。如果說程序P真正可以自己歸納，?那么P就必然可以歸納出所有的規(guī)律。我們已經(jīng)討論過了，其實任何一個程序都能夠被看?作是對輸入的一個變換而得到輸出。那么程序P自然也是。假設這些對子(a,b),(c,d),(e,f),……?都是程序P的輸入輸出對，那么我們挑選出前1000個（總而言之是足夠多的對子）。把這?1000個特殊情況輸入到P中，那么P就應該能夠產(chǎn)生這些對子的共性，也就是P自己這個?程序了！換句話說，程序P產(chǎn)生了它自己，P自己把自己給歸納出來了！這似乎陷入了怪圈?之中！另外，我們?nèi)祟愒O計出來P，如果P可以歸納所有的規(guī)律，那么P能否也能歸納出“人?歸納P”本身這個規(guī)律呢？仍然是怪圈問題！這樣的問題似乎還有很多。反過來講，如果假?設歸納出所有規(guī)律的程序P不存在，那么為什么我們?nèi)祟惪偰軞w納出規(guī)律呢？什么樣的具體問題是可歸納的，什么問題是不可歸納的？然而這些看起來非常重要的問題在目前還沒有 統(tǒng)一的答案！??
我們還將會看到很多問題都涉及到邏輯中的怪圈，而由于計算理論已經(jīng)觸及了邏輯、信?息的根本，所以把一些問題引向邏輯怪圈并不奇怪。

四、模擬?
1、什么是模擬？?
什么是模擬？又是一個基本的問題，愛因斯坦說過，越是基本的概念就越是難以刻畫清楚。模擬這個概念就是一個很難說清的問題。?
如果你站在一個朋友面前，沖著他做了一些鬼臉。那么他也會學著你的動作沖你做鬼臉，那么他就對你進行了模擬。?
很明顯，在你和你朋友之間存在著一系列的對應關系：你的手對應他的手，你的眼睛對應它的眼睛，你的嘴巴對應他的嘴巴……。而且你的手、眼睛、嘴巴做出來的動作也會對應他的手、眼睛、嘴巴做出來的動作。因而，模擬的關鍵是對應！如果集合A中的元素可
以完全對應B中的元素，那么A就可以模擬B。?
仍然用你沖你的朋友做鬼臉的例子，假如這次你做出的鬼臉以及動作沒有被他立即模仿而是被他用某種符號語言記錄到了日記本上了。比如：“X年X月X日，瘋子XX沖我做了一個鬼臉：他伸出了左手食指放到了右眼下面往下拉他臉上的肉，并且吐出了他長長的舌
頭！”。過了N多天后，你的這位朋友掏出了日記本，按照上面的描述沖著大家做了這個鬼臉。很顯然他仍然模擬了你當時的動作。那么，你朋友日記本上的那段對話描述是不是對你鬼臉動作的模擬呢？似乎答案是否，因為這段文字跟你沒有半點相像。然而你的朋友正是根據(jù)這段描述才做出了對鬼臉動作的模擬。也就是說，他把那段文字翻譯成了他的動作，而他這個動作就是對你的模擬。這個翻譯的過程很顯然就是某種信息的變換，我們完全可以把它理解為一個計算的過程，也就是可以用圖靈機來實現(xiàn)的算法過程。所以，我們說日記本上的那段指令也構成了對你鬼臉動作的模擬，原因是這些信息也與你的鬼臉動作構成了對應。具體的，我們可以用下面的圖表示：?
這里A是你的鬼臉動作，B是你朋友做出來的鬼臉動作，C是日記本上的描述。你朋友的動作B模擬了你的動作A，而B的動作信息是通過執(zhí)行C上的描述得到的，也就是說存在著一個從C到B上信息的變換。這樣我們認為C也對A進行了模擬。?
2、圖靈機之間的模擬?
下面來考慮圖靈機之間的模擬。按照前面的定義，一臺圖靈機包括：輸入集合I，輸出集合O，內(nèi)部狀態(tài)集合S，程序規(guī)則表T四個要素。那么如果兩個圖靈機之間的這些元素都存在剛才說的對應關系，就認為兩個圖靈機可以相互模擬了。然而圖靈機的功能是完成對輸入信息進行變換得到輸出信息的計算。我們關心的也僅僅是輸入輸出之間的對應關系。因而一臺圖靈機A如果要模擬B并不一定要模擬B中的所有輸入、輸出、內(nèi)部狀態(tài)、程序規(guī)則文本框: A文本框: B文本框: C文本框: 模擬文本框: 變換文本框: 模擬表這些元素，而只要在給定輸入信息的時候，能夠模擬B的輸出信息就可以了。?
因此，我們可以用下面的圖來表示圖靈機之間的模擬：?
也就是說在給定相同輸入信息的情況下，只要輸出信息o’能夠模擬信息o就可以，也就認為B模擬了A。而信息o’對信息o的模擬又符合我們上面對一般集合之間模擬的定義。
也就是說如果存在另外一臺圖靈機能夠把信息o’計算并映射成信息o，就認為o’模擬了o。
說白了也就是o’可以與o不一樣，但是只要你能用一個圖靈機把o’經(jīng)過一系列運算變換到相同的o，就認為o’模擬了o。因而也就是圖靈機B模擬了圖靈機A。?
進一步，我們可以假設A和B輸入的信息也不一樣，一個i，另一個是i’，那么如果i和i’之間也存在著模擬對應關系的話，我們?nèi)匀徽J為B可以模擬A。也就是下面的圖：?
有一點需要注意，如果A圖靈機模擬了B圖靈機，那么并不一定B圖靈機可以模擬A圖靈機。因為有可能A圖靈機比B圖靈機處理的信息更多。也就是說假如B能處理的信息
就是1，2，34，而A處理的信息除了這四個數(shù)之外，還有5,6,7,8，那么顯然當輸入1234的時候A能夠模擬B，而當輸入5678的時候B沒定義了，不能完成任何操作。在這個時候B顯然不能模擬A了。?
3、計算等價性?
講了這么多關于模擬的知識有什么用呢？模擬的一個關鍵作用就是闡明什么是等價的。比如為了完成加法運算，你寫了一段程序，而我也寫了另一段程序，雖然我們兩個的程序可能完全不一樣，然而只要我們兩個程序之間能夠相互模擬，也就是說只要給定兩個數(shù)，我們都能正確的一模一樣的算出它們的和，那么我們兩個程序就是等價的！?
具體地說，如果A能夠模擬B，并且B也能模擬A，那么A和B就是計算等價的。計算等價性是非常強有力的，因為它揭示了在我們這個宇宙中某種非常普遍的規(guī)律。我們?nèi)匀挥脛偛耪f的加法算法為例子來說明。雖然計算兩個數(shù)的加法的方法可能有無窮多種，也有可能用各種各樣的計算機語言，什么C,Basic,JAVA等等來實現(xiàn)，更有可能奔跑在不同的計算機上，然而所有這些程序，這些計算的結果意義都是相同的。也就是說所有與加法運算算法計算等價的計算機程序都是一回事兒，因而加法算法這個東西是某種永恒而獨立的！?
看！我們在宇宙中找到了某種永恒性了，這種永恒性反映了宇宙規(guī)律中某種本質(zhì)上的美！計算等價性就和能量守恒定律一樣具有這種高級的對稱性，我甚至覺得計算等價性要比能量守恒定律更加深刻！因為無論如何能量守恒定律仍然是刻畫了物理系統(tǒng)的某種屬性，而計算等價性則刻畫的是非常廣泛的信息系統(tǒng)之間的某種守恒和對稱性，而一切系統(tǒng)都可以被抽象為信息系統(tǒng)，甚至是物質(zhì)世界，所以，計算等價性是跨越所有系統(tǒng)之間的某種高級對稱的、永恒的、美的東西。?
為了進一步理解計算等價性的威力所在，我們不妨科幻一下。假設我們能夠用計算機模擬某個人，比如說張三的思維過程了（也就是假設真正的人工智能可以實現(xiàn)了）。那也就是說我們可以用一個計算機軟件X來完成對張三思維的模擬。這樣，這個軟件就會在一切與它具有計算等價性的程序甚至系統(tǒng)上實現(xiàn)張三這個人的思維過程！比如我們完全有可能讓一大堆分子的碰撞來實現(xiàn)X這個軟件，那么就會在這大堆分子碰撞的過程中完成對張三思維的模擬，也就是說張三這個人的意志蹦到了這一大堆分子系統(tǒng)中去了！更進一步，我們還可以找來足夠多的人比如這個星球上所有的人來模擬那大堆分子的碰撞，從而完成軟件X的計算。這意味著什么？意味著張三這個人的思維或者說意識在那群人的整體上突現(xiàn)了！很有可能，這些構成軟件X的人都并沒有意識到在他們上層的張三的意識的出現(xiàn)。更有趣的是，張三自己很有可能就在那一群人之中呢！?
相信你已經(jīng)能夠參悟到了什么是計算等價性的威力了，那么我也相信你能夠理解為什么說任何一臺我們使用的計算機都不過是圖靈機的翻版了。?
4、意義*?
考慮下面三句話：“請把窗戶關上！”，“Please close the window！”，“01001110111”。這三句話分別說給不同房間中的三個人。第一句話告訴給一個中國人，于是他關上了窗戶；第二句話告訴了一個英國人，他也關上了窗戶；第三句話告訴的是一個機器人，他也關上了窗戶。這三句話從表面看顯然是完全不一樣的，然而當它們讓不同的人來聽的時候，卻達到了相同的最終結果：窗戶被關上了。那么，我們自然會想，這三句話有何相同呢？顯然，答案是他們的意義相同。然而什么又是意義呢？?
真正回答意義的本質(zhì)是一個很困難的問題，現(xiàn)在人們正在努力理解語義是什么。雖然我們?nèi)詻]有完全回答這個問題，但是，不妨從圖靈機、計算以及計算等價性的觀點來考慮該問題。如果把中國人、英國人、機器人都看作是圖靈機，而那三句話看作是對他們的輸入信息，那么最終的結果就是圖靈機計算的輸出。這個時候我們看到三種結果是相同的。也就是說這些圖靈機之間是可以相互模擬的。?
考慮這三句話，顯然它們都具有相同的意義。而根據(jù)前面的敘述，能夠相互模擬的圖靈機是具有相同的計算等價性的。因而描述聽到關窗指令后并按照指令行事的圖靈機具有相同的計算等價性。而這種計算等價性就好像是前面說到的加法規(guī)則一樣是獨立于計算系統(tǒng)、
執(zhí)行機構的。因而，我們能得到下面的圖：

通過這個對比圖，我們不難得出結論：所謂語言的意義，就是執(zhí)行這個語言系統(tǒng)的計算等價性！?
我們?nèi)绾沃啦煌恼Z言表達了相同的意義呢？顯然，我們只要有了翻譯就可以明白“請把窗戶關上”與“Please close the window”具有相同意義，而翻譯所作的工作無非就是輸入中文信息輸出英文信息這樣的信息轉換工作，因而，也就是一個計算過程！?
然而當不存在從一個語言到另外一個語言的翻譯的時候，我們也并不能斷定某一個符號序列對于固定的圖靈機是否有意義。這就是說，我們雖然不能明白鳥叫是什么含義，但并不能否認它們的叫聲可能有意義，因為只有鳥自己才能明白叫聲的含義。

五、萬能圖靈機?
1、編碼?
其實我說的這個“萬能圖靈機”就是計算機術語中的“通用圖靈機”，英文是Universal?Turing Machine。而我之所以稱之為“萬能圖靈機”完全是因為這個名字似乎聽起來更加直觀。?
前面已經(jīng)講述了模擬的概念，那么自然會產(chǎn)生這樣一個問題：存在不存在一臺圖靈機能夠模擬所有其他的圖靈機呢？答案是存在的。這種能夠模擬其他所有圖靈機的圖靈機就叫做通用圖靈機，也就是我們所說的“萬能圖靈機”。這種機器在圖靈計算這個范疇內(nèi)，是萬能的！?
“萬能圖靈機”會怎樣工作呢？假如我把信息x輸入到了圖靈機M中，M就能計算出一個結果o。那么如果我把x和M的信息都輸入給萬能圖靈機，那么萬能圖靈機也會輸出o，也就是萬能圖靈機可以模擬任何一臺特殊的圖靈機。這樣的話我們就可僅僅通過改變輸入x和M的值就能“改變”萬能圖靈機的程序規(guī)則了。因而也可以認為萬能圖靈機就是可以任意編程的。這里的改變兩個字加上了引號，是因為事實上任何圖靈機在誕生之后規(guī)則就不能改變了，因而我們能夠改變“萬能圖靈機”的規(guī)則，僅僅是因為看上去是這樣的，其實根本沒有改變。?
要說明為什么“萬能圖靈機”是存在的，以及它是怎樣模擬其他任何圖靈機的動作的，我們必須先要理解究竟怎樣把任何一臺圖靈機輸入到“萬能圖靈機中”，這就需要理解編碼的概念。什么是編碼呢？你可以理解為對某一堆事物進行編號就是編碼。?
其實我們每人每天都在跟編碼打交道。每個人都有一個身份證，而這個身份證都有一個ID號碼吧？那么這個號碼就是你的編號。上學的時候老師給我們每個人都分配一個學號也是編碼。?
26個字母能夠被編碼，比如a對應1，b對應2，……，這是顯而易見的。然而任意一個英文單詞都是可以被編碼的則不那么容易一眼看出來。事實上，我們可以按照字典順序把所有的單詞都列出來。也就是說字母順序越靠前，字符長度越短的單詞排在前面，其次長單詞，字母順序靠后的單詞就排在后面。比如一種可能的字典順序：?
a, about, an…, bad, be, behave…..?
只要這樣一排好序，我們就能給每個單詞賦予一個數(shù)字，最簡單的方法是，給第一個字母分配1，第二個分配2，……，因而我們就給所有的單詞都編碼了。?
下面討論任意一個圖靈機能不能被編碼。我們假設討論的所有圖靈機的輸入集合都是僅有0,1兩種，而它的輸出也僅僅有0,1,2,3四個動作分別表示前移，后移，涂寫0，涂寫1。
而內(nèi)部狀態(tài)數(shù)最多為10000個（總之足夠多就可以了）。下面考慮程序。?
假設圖靈機的程序表為：?
當前內(nèi)部狀態(tài)s 輸入數(shù)值i 輸出動作o 下一時刻的內(nèi)部狀態(tài)s'?
2 1 0 3?
1 0 3 2?
3 0 1 1?
… … … …?
那么我們可以把它寫到一行中，這就是2,1,0,3; 1,0,4,2; 3,0,1,1，注意用“，”分開了內(nèi)部狀態(tài)，輸入數(shù)值，輸出動作和下一時刻的狀態(tài)，而用“；”分開了一行一行具體的程序。
這樣無論這個表有多大，我們都可以把它寫成這樣的一個字符串。這個字符串就相當于一個英文單詞，這就是對該圖靈機程序的一個描述。同理，其他的圖靈機也能夠得到這樣的一個單詞描述，那么我們再用字典序的方法對這些描述進行編碼，也就得到了對所有圖靈機的編碼。?
如果一臺圖靈機的編碼是M，它讀入的信息是x，這樣只要把M和x用“.”號隔開的方法分開作為數(shù)據(jù)輸入到“萬能圖靈機”中，運用特殊的算法，這個萬能的機器就能得出對M計算x的模擬結果了。事實上可以由定理證明萬能圖靈機對于任意的編碼都是存在的，
在這里我們就不敘述證明過程了。?
2、自食其尾?
既然“萬能圖靈機”能夠模擬任何一臺圖靈機的動作，那么它能不能模擬它自己的動作呢？答案是肯定的。我們首先看到“萬能圖靈機”也是圖靈機，也有固定的輸入、輸出、狀態(tài)的集合、固定的程序，因而它也能被編碼。于是我們就可以把它自己的編碼信息輸入給它自己了。這就好像一條蛇咬到了自己的尾巴。會發(fā)生什么呢？自食其尾就會產(chǎn)生怪圈，雖然我們現(xiàn)在還沒有看到任何不好的征兆，然而在下一節(jié)里面，我們將看到這種怪圈會誕生什么樣的結論。而且我們也會看到，其實這個怪圈是和康托爾對角線法則、哥德爾定理有關的。?
圖靈機一旦能夠把程序作為數(shù)據(jù)來讀寫，就會誕生很多有趣的情況。首先，存在某種圖靈機可以完成自我復制！事實上，計算機病毒就是這樣干的！我們簡單說明一下，這個特殊的圖靈機是如何構造的。我們假定，如果一臺圖靈機是X，那么它的編碼就記為<X>，這
樣能夠自我復制的圖靈機T的功能是，把T的編碼<T>寫到紙帶上輸入到“萬能圖靈機”，那么“萬能圖靈機”就能根據(jù)讀入的<T>，在紙帶上再次輸出<T>的一份拷貝<T>’，并且<T>=<T>’。下面就來大概解釋如何構造這樣的T。首先T由兩部分構成AB。第一部分A的功能是指導“萬能圖靈機”把B的編碼<B>原封不動的打印到紙帶上，這個時候紙帶上就有了<B>，如果這個時候你想用同樣的方法打印<A>到紙帶上是不行的，因為會出現(xiàn)循環(huán)定義。然而B可以這樣做，讀入紙帶上的信息X，生成能夠打印X的圖靈機：p(X)的編碼<p(X)>打印到紙帶上，并把X和<p(X)>的內(nèi)容前后調(diào)換，有定理保證這樣的圖靈機是存在的。這樣當B讀到紙帶上的信息<B>之后就會打印出能夠打印<B>的圖靈機的編碼也就是<A>了，然后把<A>和<B>位置對換就構成了<AB>也就是<P>，所以P把自己進行了一次拷貝。初看起來，這種自我復制的程序是不可能的，因為這包含了無窮無盡的怪圈。P要能產(chǎn)生它自己<P>就意味著P中至少包含了一個<P>，而這個<P>中又包含了至少一個<P>……，最后P必然是一個無限大的程序，然而我們卻能夠證明P是可能的。?

有了“萬能圖靈機”還能得到很多有趣的結論，比如假設有一大群圖靈機，讓它們彼此之間隨機的相互碰撞，當碰到一塊的時候，一個圖靈機可以讀入另一個圖靈機的編碼，并且修改這臺圖靈機的編碼。那么這樣一個圖靈機“湯”中會產(chǎn)生什么呢？圣塔菲研究所的芳塔娜已經(jīng)研究了這個實驗，并得出了驚人的結論：在這樣的系統(tǒng)中會誕生自我繁殖的、自我維護的類似生命的復雜組織，而且這些組織能進一步聯(lián)合起來構成更大的組織！

六、停機問題?
1、死循環(huán)?
在進行正式討論之前，我們先來看看一個非常簡單的猜硬幣游戲。?
假如我的兩個拳頭中一個攥著一枚硬幣，另一個沒有，然后讓你猜是哪一個？于是你告訴我左手中有。這時候我不會把手張開，而是背過身去做一番手腳，然后把拳頭伸過來，張開手！哈，你錯了吧，硬幣在右手中！大概傻子都能看出來我的伎倆之所在！不用說，采
用這種方法我保證百戰(zhàn)百勝。因為我總是等你說出來哪個手有硬幣之后再動態(tài)的改變我的策略。所以，這改變之后的狀態(tài)就已經(jīng)不是你猜的了。?
大概你會覺得不可思議：其實圖靈停機問題就是一個類似該游戲的原理！?
下面我們來看看圖靈停機問題是怎么回事兒。讓我們考慮這樣一個問題：存在不存在一個程序比如說P，能夠判斷出任意一個程序X是否會在輸入Y的情況下陷入死循環(huán)？我們不妨設P(X,Y)表示P判斷程序是X，數(shù)據(jù)是Y的結果。如果存在死循環(huán)，那么P(X,Y)就輸出一個yes。如果不存在死循環(huán)，那么P(X,Y)就輸出一個no。我們的問題就是這樣的P(X,Y)存在么？這就是停機問題。所謂的某個程序X在輸入Y上停機就是說X不存在著死循環(huán)，反過來如果不停機就是存在著死循環(huán)，因而這里停機和死循環(huán)是一回事兒。那么，這種判斷停機問題的程序P存在么？?
答案是不存在的。下面我可以證明我的這個結論。?
我們不妨假設程序P存在。那么我們可以根據(jù)P設計一個新的程序Q如下：?
X是任何一段程序的編碼：?
Program Q(X){?
m=P(X,X)?
do while (m=no)?
…?
…?
end do?
if m=yes then return

}?
這段程序通俗來講就是：輸入任何一段程序X，調(diào)用函數(shù)P(X,X)并得到返回值m，如果m=no，也就是說根據(jù)P的定義，P判斷出程序X作用到它自己身上X不存在死循環(huán)。那么Q就不停的做do while和end do之間的語句。如果m=yes，我們知道這表示P判斷出程序X在X上存在死循環(huán)。就返回，結束該函數(shù)。?
我們可以看到，這樣定義的函數(shù)Q(X)是沒有問題的。下面就進入關鍵時刻了：我們問Q這個程序作用到Q自身的編碼上也就是Q(Q)會不會死循環(huán)呢？當然我們可以運用強有力的函數(shù)P(Q,Q)來計算這個問題。?
假設Q(Q)會發(fā)生死循環(huán)，那么P(Q,Q)就會返回yes。然而根據(jù)Q函數(shù)的定義，把X=Q代入其中會發(fā)現(xiàn)由于P(Q,Q)返回的是yes，也就是m=yes，因此Q函數(shù)會馬上結束，也就是程序Q(Q)沒有發(fā)生死循環(huán)。然而如果假設Q(Q)不發(fā)生死循環(huán)，那么P(Q,Q)應該返回no，這樣根據(jù)Q函數(shù)的定義，把X=Q代入Q(Q)之中會得到m=no，這樣程序就會進入do while循環(huán)，而這個循環(huán)顯然是一個死循環(huán)。因而Q(Q)發(fā)生了死循環(huán)！這又導致了矛盾。?
無論Q(Q)會不會發(fā)生死循環(huán)，都會產(chǎn)生矛盾，然而哪里錯了呢？答案只能是最開始的前提就錯了，也就是說我們最開始的假設P(X,Y)能夠判斷任意程序X在輸入Y的時候是否死循環(huán)是錯誤的！也就是說這樣的程序P(X,Y)不存在！?
2、如何理解?
也許你會感覺整個論證過程有些怪異，為什么不存在這種P(X,Y)程序呢？而上面的論證過程中僅僅說P(X,Y)當作用到P(Q,Q)上時會產(chǎn)生矛盾。似乎并不能說明P作用到其他程序上不能判斷是否死循環(huán)。比如你可以考慮編寫這樣一段程序，當一發(fā)現(xiàn)某個程序do?
while(T)，這里T總是為真，這樣的語句出現(xiàn)的時候就判斷這個程序有死循環(huán)。這顯然是可能的。但問題的關鍵是，你假設了P(X,Y)能夠判斷任意的一個程序是否死循環(huán)！最關鍵的就是這“任意程序”上了。因為假如你已經(jīng)按照剛才提到的判斷是否有do while(T)語句的方法寫出了一個程序P來判斷某程序是否死循環(huán)，那么我就會根據(jù)你這個程序P再構造出一個程序Q，就是利用上面提到的論證方法，我們不妨寫成QP(這里下標P的含義表示根據(jù)你的程序P而構造的Q)。這樣你的P在遇到了P(Q,Q)這樣的怪東西的時候無能為力了！?可能你還不服輸，于是你又改進了你的程序變成了P’，這個時候P’能夠判斷包含了QP這個程序時候的所有程序情況了。那么我又會根據(jù)你的新程序P’來構造出一個更新的QP’，你的程序P’仍然不能判斷，當然你還可以構造P’’,P’’’,……，我也會跟著構造QP’’,QP’’’，……，總而言之這個過程是無窮的！因為我總在你之后構造程序，所以你是水我是船，水漲船高，我總能比你高一級別！?
這很像剛開始敘述的那個猜硬幣的游戲。你想猜對我的硬幣，就必須告訴我一個答案是左手還是右手，然而關鍵問題是我總能根據(jù)你做出的答案動態(tài)調(diào)整，使得你永遠也猜不對！
停機問題也是如此，我總能根據(jù)你的程序P來構造你的P判定不出來的問題Q，我總會贏！
很簡單，因為你總要在我之前構造好P呀，就相當于你總要先說出硬幣在哪個手！?
3、對角線刪除方法?
我在開始的時候就提到了圖靈停機問題、哥德爾定理等等都來源于康托爾的對角線刪除法則。那么，下面我們就來看看，如果運用對角線刪除法則如何證明圖靈停機問題呢？采用這種全新的證明思路，也許你會更加清楚地認識到停機問題的本質(zhì)。?
問題沒有變，是否存在一個程序P(X,Y)判斷出來任意一個程序X當輸入Y的時候是否有死循環(huán)，或者說是否停機。?
我們?nèi)匀挥梅醋C法，假設這樣的P(X,Y)是存在的。而我們知道程序X本身是可以被編碼的。也就是可以為所有的程序進行編號：1，2，3，……，而數(shù)據(jù)Y本身也是這樣的編號1，2，3，……，因而我們就可以把每一對X和Y的組合排列在一張表上。比如列表示的是數(shù)據(jù)Y，而行表示的是程序X，這樣P(X,Y)的值也就是yes或no就可以寫在第X行第Y列的對應位置上，表示P(X,Y)判斷出的X作用在輸入Y上是否會死循環(huán)的結果。比如下面的表就是一個示例：?

1 2 3 4 5 6 …… Y ……?
1 yes no no yes yes no …… yes ……?
2 no no yes yes no yes …… no ……?
… ……………………………………………………?
X no yes no yes yes no …… yes ……?
… ……………………………………………………?
到這里沒有發(fā)生什么毛病。我們知道上表中的每一個行都表示一個確定的程序作用到不同的數(shù)據(jù)上所得到的結果。比如程序X作用在1,2,3,4,……,Y，……上給出的結果就是一個序列：?
no,yes,no,yes,yes,no,……,yes，……?
下面我們把上表對角線上的元素挑出來。也就是專門找那些第1行第1列，第2行第2列，……這樣的元素就可以得到一個序列：?
yes,no,no,yes, ……?
而根據(jù)這個序列我們完全可以構造這樣一個反序列：?
no,yes,yes,no, ……?

也就是說這個序列在每一個位上都與前一個對角線序列不同！這個序列就稱為對角線刪除序列。那么我問，這個對角線刪除序列是否在我們表中的某一行上呢？答案是否定的！這個序列必然不在表中。因為它的第一個元素與1,1不同，第二個元素與2,2不同，……。換一種方式解釋就是：假設對角線刪除序列的確在表上列出來了，那么這個序列必然在某個固定的行，比如說就在第1001行。那么我們就要考慮這第1001行，第1001列的元素，我們知道根據(jù)序列的構造方法(1001,1001)對應表中的元素是與序列上的這個元素不同的！因而產(chǎn)生了矛盾，也就是說這個構造出來的對角線刪除序列不在表中！?
我們完全可以設計出一段程序Q使得Q作用在1,2,……,X,……上產(chǎn)生的序列就是對角線刪除序列，而對角線刪除序列不在表中就意味著程序P并不能判斷出程序Q作用在任意輸入上是否停機。其實這里的程序Q就是前一節(jié)論證停機問題的程序Q。?
用對角線刪除的證明方法來看究竟哪里出錯了呢？錯誤就出在我們假設程序P能夠得到這樣一張完整的表，這張表對所有的程序計算得到是否停機的答案。?
4、意味著什么？?
我們已經(jīng)看到了，的確存在著一類問題我們?nèi)祟惸軜嬙斐鰜?#xff0c;而圖靈機是不能解的，。我們知道圖靈機不能解的問題也就是一切計算機不能解的問題，因而這類問題也叫做不可計算的。因此，必然存在著計算機的極限。實際上，運用我們前面敘述的計算等價性原理，有
很多問題都可以被歸結為圖靈停機問題，也就是說圖靈停機問題揭示了宇宙中某種共性的東西，所有那些計算機不能解決的問題從本質(zhì)上講都和圖靈停機問題是計算等價的。比如在最開始我們就提到的希爾伯特第10問題就是一個典型的不可計算問題！還有很多問題是不可計算的，尤其是那些涉及到計算所有程序的程序。比如是否存在一個程序能夠檢查所有的計算機程序會不會出錯？這是一個非常實際的問題。我們都知道計算機程序特別容易犯錯誤，為了檢查出某段計算機程序的錯誤，我們?nèi)祟惥捅仨殞@個程序進行人工的檢查。那么能不能發(fā)明一種聰明的計算機軟件，輸進去任何一段計算機程序，這個軟件就會自動幫你檢查輸入的程序是否有錯誤？答案仍然是不存在的，其實這個問題可以被證明和圖靈停機問題實質(zhì)上是一樣的！于是我們的夢想又破滅了！?

圖靈停機問題也和復雜系統(tǒng)的不可預測性有關。我們總希望能夠預測出復雜系統(tǒng)的運行結果。那么能不能發(fā)明一種聰明的程序，輸入進去某個復雜系統(tǒng)的規(guī)則，輸出的是這些規(guī)則運行的結果呢？從原則上講，這種事情是不可能的。它也是和圖靈停機問題等價的。因而，
我們得出來的結論就是：要想弄清楚某個復雜系統(tǒng)運行的結果，唯一的辦法就是讓這樣的系統(tǒng)實際運作，沒有任何一種計算機算法能夠事先給出這個系統(tǒng)的運行結果。你很有可能不同意我的觀點，因為畢竟我們能夠發(fā)明很多預測復雜系統(tǒng)的方法，而不需要一定要讓復雜系統(tǒng)去真實的運作。但是，你還是沒有理解我這里的問題。我們強調(diào)的是不存在一個通用的程序能夠預測所有復雜系統(tǒng)的運行結果，但并沒有說不存在一個特定的程序能夠預測某個或者某類復雜系統(tǒng)的結果。那么這種特定的程序怎么得到呢？顯然需要我們?nèi)藶榈鼐幊痰玫?#xff01;也就是說存在著某些機器做不了的事情，而人能做。這似乎為人工智能的崇拜者給以了沉重的打擊！?
人工智能真的是不可能的么？彭羅斯曾經(jīng)寫過一本科學明著：《皇帝新腦》來論證人工智能的不可能性。它所運用的方法就是我們上面的邏輯。因為對于任何一個人工智能程序來說，總存在著它解決不了的問題！但是似乎我們?nèi)祟悈s不受這種限制，我們總是能夠發(fā)現(xiàn)一
個程序是否有死循環(huán)，總是能夠找到對某類復雜系統(tǒng)預測的方法，并且我們還能構造出來圖靈停機問題這樣的問題。然而事實并沒有那么簡單，反對者馬上就會論證到，其實針對某一個具體的人，比如說就是彭羅斯，我們也能夠運用前面的方法構造出一個彭羅斯自己不能解的問題！然而事實情況下要構造彭羅斯不可解的問題太麻煩了，而我們只是說原則上講這種問題是存在的！因而計算機超越不了的問題，人自己也超越不了，所以說人工智能是可能的！?
看看上面提到的兩方面論證似乎都很有道理，究竟哪個正確呢？真的會存在某個人不可解的類似圖靈停機的問題么？其實要想徹底回答這個問題就相當于問超越圖靈計算的限制是否可能？如何超越圖靈機停機問題呢？下面我們將詳細討論一下這個問題。?
5、超越圖靈計算*?
我們?nèi)匀挥媚莻€猜硬幣的游戲為例來說明。?
在進行了幾輪猜硬幣的游戲之后，你已經(jīng)很惱火了，認為這樣的游戲不公平。于是你想了一個妙招來對付我：每當我讓你說硬幣在哪個手中時，你先胡亂的說一個答案，比如左手。
這個時候我會根據(jù)你的答案動態(tài)調(diào)整把硬幣放到了右手中。這個時候你趕緊搶著說，不對，我猜你的硬幣在右手！我沒辦法只能再次調(diào)整策略把硬幣放到了左手。你又趕快說：是在左手！……。就是這樣，你也學會了我的方法，根據(jù)我的策略不斷調(diào)整你的策略從而讓我不可能贏你。能不能把這種方法用到超越圖靈停機問題呢？?
前面我們已經(jīng)看到了類似這樣的過程。假如你寫出了一個程序P能夠判斷所有程序是否停機，那么我就能夠構造一個程序Q是你的程序判斷不了的。這個時候還沒有結束，你又根據(jù)我的Q構造了新的程序P’，然而我又能構造一個程序Q’仍然讓你的程序P’解決不了。
但是你沒有結束，又構造了新的程序P’’，我于是又構造Q’’……。?
乍一看，似乎這個過程并不能說明任何問題。原因很簡單，我要求的是構造一個固定的程序P判斷出所有程序是否停機。而你給我的并不是一個具體的實實在在的程序，而是一個不斷變化的捉摸不定而虛無飄渺的程序序列！并且你的這些總在變化的程序序列總是要根據(jù)我構造的程序才會確定改變！?
首先一點值得肯定的是，運用這種方法，我們的確能夠超越圖靈計算了，只要反復不停的變換我們的程序就不可能找出它不能解的問題。然而，另一方面又會讓我們很失望：這樣的變換過程并不能給出一個實實在在的程序來！我們擁有的僅僅是不斷改變的程序序列，而

不是一個實際存在的程序！?
這正是問題的關鍵所在：要想徹底超越圖靈計算的限制，我們必須要放棄程序的實在性。也就是說程序在每時每刻都要變化成不是它自己了。那么這樣的一個不斷變化得不是它自己的怪東西存在么？?
幾千年的人類科學一直在研究實實在在的東西。無論是原子、分子還是計算機程序，它們必須是一個實實在在存在的個體，在這種前提下科學才能夠?qū)λM行研究！如果當我們研究它的時候，它已經(jīng)變得不是它自己了，那么科學就對它無能為力了。然而，我不禁要提出
這樣的問題：真的一切都是固定不變的存在著么，有沒有某種東西在每一時刻都在變得不是它自己了呢？?
這個問題似乎是一個古老的哲學問題了記得赫拉克里特就曾經(jīng)提到過：一個人不能兩次踏入同一條河流。我想他說的正是這樣的問題：因為河流在每時每刻都不再是它自己了。河流是一大群流動的水滴構成的整體，在每時每刻這些水滴都在不停的運動、流逝，因而當你
兩次踏入這條河的時候，所有的水滴可能都不一樣了，那么我們怎么能說這些水滴構成的整體還是同一條河呢？?
再考慮我們?nèi)俗约骸Ｄ愫芸赡苣弥粋€你3歲時候的照片興奮的對你的朋友說：“看，我3歲的時候多可愛呀！”。然而你這句話意味著什么呢？意味著照片反映的3歲時的你和現(xiàn)在的你是同一個個體！然而，3歲的你和現(xiàn)在的你是多么不同呀！我們知道，你無疑就是一大堆細胞構成的一個整體。而基本生理學知識告訴我們，實際上人體的所有細胞每隔大約4年就會因為新陳代謝的作用全部更新一遍。也就是說，你的細胞全被掉了包了，更何況3歲時候的你和現(xiàn)在的你差了多少個4年呀？那憑什么說那個3歲時候的你就是現(xiàn)在的你呢？?
這個問題看似玄學，不過我認為現(xiàn)在我們的確應該認真對待該問題了。盡管從分析的角度來說3歲的你和現(xiàn)在的你的確不是一個個體，然而常識告訴我們，這兩個你的確都是同一個人！那就意味著，你這個個體并不是一成不變的一些固定的細胞，而是一個每時每刻都在變化，都在更新的一個一大堆細胞組成的構形。這個構形在每時每刻都要利用更新的一大堆細胞去維持自己的存在！我們得到了什么？和我們前面敘述的超越圖靈機的討論結合起來，就發(fā)現(xiàn)，原來人還有赫拉克里特的河流這種東西剛好就滿足那種超越圖靈計算的要求。也就是說人還有赫拉克里特的河流在每時每刻都在不停的更新它自己從而變得不是它自己了。那么很有可能，某一種做類似變化的個體的變化規(guī)律就是不停超越它自己的圖靈停機程序，這樣的虛幻的個體就真的能夠超越圖靈計算了！?
總結前面的討論，我們不難給出結論，一個固死的能夠被寫出就不再變化的程序不可能超越圖靈計算的限制，然而如果一個程序每時每刻都已經(jīng)變化得不是它自己了，這個程序就能夠超越圖靈計算。聯(lián)系到人這個個體，我們能得到：因為每時每刻的人都已經(jīng)由于細胞的變化而變得不再是它自己了，所以人是超越圖靈計算的！還記得在前面我提到的一個問題么：
“人腦的信息處理過程能不能被表示成固定的程序呢？”。我這里的答案就是否定的！也就是說人腦信息處理的過程并不是一個固定的程序！如何制造真正的人工智能呢？很顯然，我們不能用一個簡單的程序來構造，而必須是利用其它的方法，這個方法是什么呢？現(xiàn)在還沒有結論！?
七、懸而未決?
到此，我已經(jīng)把全部的有關圖靈機、可計算理論、停機問題的一些重要概念介紹完了。
然而在計算理論這個領域里還有很多重要的問題沒有介紹。但我不得不根據(jù)我的興趣進行取舍。在整個介紹過程中，一方面我介紹了人們已經(jīng)得出來的結論，另一方面，我盡量把一些沒有解決的問題展現(xiàn)給大家。回憶起來，這些懸而未決的問題包括下面幾個：

1、 是否一切的信息處理過程都具有固定的程序呢？人腦有固定的程序么？?
2、 如何用計算機程序進行歸納？能對所有事物進行一勞永逸的歸納算法是否存在？?
3、 什么是意義，更確切的，什么是語義？?
4、 圖靈停機問題是不可超越的么？?
5、 人工智能是否可能？?
還有很多問題在本文中沒有提出來，然而我認為也是相當重要的。例如，我們?nèi)绾斡脠D靈機模型表示一般的學習過程？若干小的圖靈機是如何自動的構造出更大的圖靈機的（這就是萬事萬物自組織的過程）？生命的目的性如何用圖靈機模型表示？?
另外最近的計算主義已經(jīng)把宇宙中一切的過程都歸結為計算過程了，也就是說到處都是圖靈機正在做運算。那么我們能不能從圖靈機的角度探討時間和空間的本質(zhì)呢？我們知道，計算理論另外一大類問題就是探討計算的時間和空間復雜度，那么這種計算的時間和空間與
我們這個宇宙的時間和空間有什么關系呢？?
我希望，在新世紀的今天，人們會最終解答這些問題！

?

轉載于:https://www.cnblogs.com/hjlweilong/p/9434534.html

總結

以上是生活随笔為你收集整理的离散数学图灵机文章的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。