一:前言

從下半本書開始,每一個篇章的內容都擴展了很多。之前也有人提過,說內容太過於龐雜,主題繁多看不下去。好吧這隻能說是筆者能力有限,沒有辦法做到讓這些內容更加引人入勝。但是書中涉及到的主題恐怕比筆記內提到的還要更多,雖然多卻並不是毫無關聯的堆砌,而是一個有機的把眾多領域聯結起來的一個結構。其實這個已經在之前反覆提及了,同樣的,後半本書的很多主題論述實際上在上半本書裡的時候就已經講過了,後面的內容是進一步的延伸和拓展。

看這本書確實很累,尤其是會前看後忘的情況下,翻這本書就跟翻字典一樣了,得返回去看一遍前面的內容,來和當下的內容對上號才行。筆者寫筆記的時候也是同樣要翻前面的筆記來對照內容,雖然記過筆記稍微有點印象,但還得回去查。

這一篇章的內容感覺有點跳脫,和前面的篇幅內容比,主題突然跳遠了。前面兩章節還在探討關於人類大腦和心智的問題,這一篇章卻把主題跳躍到了關於數論的內容上面來了。但看似沒有關係,實際上卻關係緊密。通過前面章節我們對自己的大腦有所瞭解(瞭解有限),但我們還是大概看得出來,大腦是一種有限表現無限的形式(其中的關係之錯綜複雜,前面的筆記已經說了)。這種表現形式可能並不準確和全面,但是確實是可以找到對應的情況——就是數論的證明——你要用一個“有限的”證明去證明出“無限的”自然數性質。

而且關於數論的內容其實早在之前第二章節關於歐幾里得的部分的時候就有所提及了——“質數證明”的問題,同樣一些內容也在前面的筆記裡有所涉略,比如:費馬大定理、代數幾何、丟番圖方程、斐波那契數列等等。

在對話部分,對應的巴赫音樂作品是著名的《哥德堡變奏曲》,然後在阿基里斯和烏龜的探討中,引入了數論裡一個我們耳熟能詳的著名“猜想”——“哥德巴赫猜想”(最難的題目終於還是來了)。變奏結合“哥德巴赫猜想”的內容是為了要顯示數論當中最困難也是最精妙的一處:“對無窮空間進行探索。”哥德巴赫猜想的困難之處;之前討論過的歐幾里得定理的證明困難之處、包括費馬大定理的證明困難之處都已經展示出來了——困難就在於我們如何能夠嚴謹的窮盡“無窮”的證明?

同時,同樣一個問題也有很多變體,這是為什麼這裡要強調“變奏曲”的原因。無窮空間探索要面對的是三種不同的方向:無窮的探索、有窮的探索以及搖擺於兩者之間的探索。在對話之後的論述部分,標題給出了的三個詞語“BlooP、FlooP、GlooP”是指侯世達教授自己想出來的三種計算機語言。這三種語言正是對應這裡說的三種探索證明變奏:BlooP程序只可以進行可預見的有窮搜索、FlooP程序可以進行不可預見的,或甚至是無窮的搜索。GlooP程序則可以進行似有窮、似無窮的搜索。這裡的內容像是一個釦子——為後面的內容留下伏筆;可能是圖靈停機問題的伏筆(而且好像又能連接到哥德爾不完備性定理上去)。

前兩種程序同時還對應兩個概念:“原始遞歸函數”和“一般遞歸函數”,這兩個概念在數論和可計算性理論中非常重要,同時也是哥德爾的證明中的根本性的概念。記得在關於“遞歸”的那一篇筆記裡說過關於“回溯”的問題——遞歸有兩種情況,其一是存在一個“終止”,最終你可以從“夢裡”醒來回到“現實”。這就是“原始遞歸”。另一種情況是,你永遠處在夢裡,不斷地醒來卻還是在夢裡,這就是“無窮回溯”。“一般遞歸”就是這樣的性質。

而且這兩個概念在可計算性理論當中也是非常重要的概念內容,比如“原始遞歸函數”就會涉及到圖靈機計算的內容,而“一般遞歸函數”則會涉及到圖靈完全系統。

當然這會在後面具體地說,還是從對話開始吧。

二:烏龜夜訪阿基里斯的“詠歎調及其種種變奏”

阿基里斯這段時間失眠了,似乎被什麼問題困擾一直睡不好覺,於是呢,這天烏龜正好找上了門。(夜訪)於是阿基里斯就請烏龜陪他解解悶,兩位就開始聊天了。阿基里斯說自己試過了世界上最煩人的事情來讓自己無聊到睡著,結果壓根沒有用,於是他打算試試看來討論數論催眠自己。(感情數論是比世界上最煩的事情還要煩啊23333)

於是烏龜開始和阿基里斯聊起來了,不過他們並不是從數論開始的,而是從一個叫“凱瑟琳”的侯爵的話題開始的。烏龜說:這個侯爵也遇上了和阿基里斯類似的情況,因為某種原因失眠而睡不著覺。於是這位侯爵請來一位音樂家,為自己譜寫可以讓自己睡著的曲目。於是那位作曲家寫作了一首“變奏曲”獻給侯爵,這位音樂家自然就是巴赫。而這首“變奏曲”就是大名鼎鼎的《哥德堡變奏曲》,但實際上這首曲子原本叫《詠歎調及其種種變種》。因為當時演奏這個曲子的管風琴樂手叫哥德堡,於是給起了這個名字。

烏龜強調,《哥德堡變奏曲》的種種變調之所以可以保持一致,不是因為旋律相同,而是因為變奏都保持在同一種和聲基礎之上。在相同基礎之上的種種不同變奏,就有了一種內在的“統一性”。然後阿基里斯和烏龜說起《哥德堡變奏曲》一開始人們以為只有三十首“變奏”,但是之後有人發現,在一本特殊的《哥德堡變奏曲》樂譜副本後面,巴赫又留下了一些特殊的“終止之後的終止”,就在樂譜的背面。結果通過這個留下來的“終止”,人們又發現了新的十四首卡農曲。於是《哥德堡變奏曲》就有了四十四首“變奏曲”。

聊到這裡烏龜開始把話題引向數論,以《哥德堡變奏曲》為例,最終音樂家們在樂曲結尾之後又發現了原本就保存在“樂曲”當中的新“樂曲”。那麼按照普遍性來說,是不是別的樂曲也有類似的情況。你看,我們最後從《哥德堡變奏曲》的結尾發現了整整十四首新的變奏曲,也就是說就算我們知道樂曲是有限的,它一定會結尾,我們也不知道它會在什麼地方結尾。(所以也許你可能又找出新的曲子)

這裡可以理解為,烏龜把形式系統比喻成了樂曲。而關於樂曲當中找出新旋律,就好像哥德爾不完備性定理下運行的系統一樣。即使我們知道形式系統下的定理是有限的,我們也不知道有多少個,所以永遠可能需要“打補丁”。而不完備性定理治下的所有“強力”系統,都逃不出這個情況。(注意這裡強調“強力”)

阿基里斯:“總數——稱之為‘g’吧——肯定是有限的,你同意吧?——可僅僅知道g是有限的並不等於知道g有多大。因此,這一信息無法使我們知道什麼時候我們能確定最後一支《哥德堡變奏曲》。

之後阿基里斯問烏龜,巴赫是什麼時候寫的這首變奏曲,烏龜這裡說了一個雙關語,它說:“這是1742年的事,那時他在萊比錫當‘康托爾【Czntor】’——就是教堂聖詠班的指揮。”這裡強調了“康托爾”,我們知道數學當中的“集合論”就是由一位叫康托爾的俄國數學家和德國數學家理查·戴德金一起發明的。(他們發明的叫樸素集合論,這在第二篇筆記裡提到過,因為這裡的內容和第二次數學危機有關)

緊接著這個回答,阿基里斯和烏龜就圍繞年份這個數字展開了。烏龜告訴阿基里斯:1742這個數字恰好是兩個奇素數1723與19之和。阿基里斯一上來被烏龜這麼一說,以為這個數字和這個巧合有什麼特殊意義。然後他列了一張小表格,然後發現這種所謂的“巧合”,放眼偶數內,這種性質遍地都是,一點都不特殊。阿基里斯表示奇怪,問這其中能有什麼顯而易見的規律嗎?

烏龜說也許找找就能有。(這裡已經開始進入關於“哥德巴赫猜想”的內容了)果然烏龜開始順著數字“1742”接著展開了。這裡阿基里斯稍微插了一句,他說他發現1742恰好是兩個奇素數的差:1747與5。這裡已經暗示了,偶數具有某種性質:既可以被表現為兩個奇素數的差(特定範圍),也可以表現為兩個奇素數的和(也是特定範圍)。

然後烏龜接著講了下去:“……我剛才說到,1742年,有個業餘數學家——他的名字我一下子記不起來了——寄了封信給歐拉。歐拉那時正在波茨坦腓德烈大帝的宮廷裡……在信裡,這位業餘的數論愛好者向偉大的歐拉提出了一個為證明的猜想:‘每個偶數都能表示成兩個奇素數之和。’這傢伙的名字指什麼來著?……啊,對了!是‘哥德巴赫’!這傢伙是哥德巴赫!”

隨後阿基里斯開始聽烏龜介紹哥德巴赫猜想的證明歷史(很簡略的介紹):“已經有了一些值得注意的很接近的結果。比如,1931年俄國數論專家施尼勒曼證明了:任何一個數——偶的或奇的——都能表示成不多於300000個素數之和。

阿基里斯問:“這結果真怪。它有什麼用處呢?

烏龜回答說:“這就把問題限制在了有窮領域,在施尼勒曼給出證明之前,有可能當你取越來越大的偶數時,就需要越來越多的素數來表示。沒準有什麼偶數需要一萬億個素數來表示!現在我們知道了不會有這種事——300000個素數(或更少些)的和就足夠了。”(有沒有人聯想到之前關於“費馬大定理”的證明過程?是不是有很類似的地方?都是逐步縮小範圍,最後不斷地逼近然後終於得到了證明。)

烏龜接著說了下去:“後來,1937年,一個名叫維諾格拉多夫的狡猾傢伙——也是個俄國人——設法建立了一個與期望目標接近得多的結果,就是:每個足夠大的奇數都可以表示成不多於三個奇素數之和。例如,1937=641+643+653.我們可以把能表示成三個奇素數之和的奇數稱為具有‘維諾格拉多夫性質’的數。這樣,所有足夠大的奇數都具有維諾格拉多夫性質。

阿基里斯問道:“很好——可‘足夠大’是什麼意思?

烏龜回答:“意思是說,有數量有限的某些奇數也許不具有維諾格拉多夫性質,但會有一個數——稱之為‘v’吧——大於它的所有奇數都是具有維諾格拉多夫性質的,不過維諾格拉多夫無法確定v有多大。所以某種意義上說,v就像g,那個有限的、但不知道多大的哥德堡變奏曲數目。僅僅知道v是有限的並不等於知道v有多大。因此,這一信息無法使我們得知什麼時候我們能確定最後那個需要由多餘三個奇素數來表示的奇數。

這裡就是涉及到數論的很深的內容了,當然說是說“深”,其實也就是一個說法。數論的本質就是對於“數”的研究,“數”的關係和性質,用算術的方式來表示。很多人對於數論都很難提起興趣,與其說是太難了,不如說是太無聊了——找不到實際的意義。當然學這方面的人肯定有不同的看法,但至少對於沒有入門提起興趣的人來說,要看“數論”確實是需要極大耐心的。

這裡筆者可以給出一個自己的看法,數論中表現的關於“數”的種種性質,互相之間的關係。就好像是我們生命中很多“巧合”,有說命該如此、或是單純的巧合、或是上帝擲色子……但不管怎麼說我們都會賦予其“意義”,去試圖解釋這些“巧合”——因為存在既是合理。我們如果用同樣的看法來看待數論,也許可以讓我們發現其中的那些樂趣。(不知道多少人看過金·凱瑞的《靈數23》)那我們繼續來看看阿基里斯和烏龜訴說的,關於哥德巴赫猜想的證明過程。

阿基里斯總結:“我明白了。於是任何足夠大的偶數2N都能表示成四個素數之和,因為可以先把2N-3表示成三個素數之和,然後再添上素數3。

烏龜:“正是如此。另一個角度的研究得出了一個很接近的結果,它是這樣一個定理:‘任何一個偶數都可以表示成一個素數和另外一個數的和,後者是至多兩個素數的積’。

烏龜和阿基里斯聊的這些內容實際上就是哥德巴赫猜想的種種變奏版本,不看兩個素數之和,那麼來看看兩個素數之差。阿基里斯列了一個偶數表示成兩個奇素數之差的列表,結果發現這個列表是無限的,而且紊亂無序,至少表面上看不出什麼規律來。

《秩序與紊亂》艾舍爾

烏龜:“你是不是認為每個偶數都能以某種方式表示成兩個奇素數之差?

阿基里斯:“從我的表來看,回答當然是肯定的。不過我仍然可以假定回答也可能是否定的。這並沒有真的使我們走得太遠,是吧?

烏龜:“這裡有很多值得注意的方面,我說的是在這個問題上會有更深入的洞見。

阿基里斯:“真奇怪,這個問題和哥德巴赫原來的那個問題這麼想像。也許該稱之為‘哥德巴赫變奏’。

烏龜:“……我們假設:如果一個偶數是兩個奇素數之和,就是具有‘哥德巴赫性質;而如果它是兩個奇素數之差,則具有‘烏龜性質’……如果一個數不具有烏龜性質,則我們就說它具有‘阿基里斯性質’。”(這裡阿基里斯建議烏龜把“哥德巴赫性質”換成“阿基里斯性質”,因為是自己先提出來的,可能是為了便於讀者區分這個問題——當然估計很多人到這裡就已經被繞暈了)

烏龜:“現在想一想,比如說,一萬億是否具有哥德巴赫性質,或具有烏龜性質?當然,它也可能兩者兼備……假如我是問你其中一個問題,前一個或者後一個,你會選擇哪個問題去考慮?

阿基里斯:“我想我會扔一枚硬幣。我沒看出兩者有什麼差別。

烏龜:“這可有天壤之別啊!如果你選了哥德巴赫性質,說的是素數之和,那麼就僅限於使用那些介於2和一萬億之間的素數。對吧……因此,你為一萬億找一個兩個素數之和表示這一過程是註定會終止的。

阿基里斯:“啊!我知道關鍵所在了。要是我選擇把一萬億表示成兩個素數之差,涉及到的素數就會沒有個頭,有可能大到要花一萬億年才能找到它們……如果它們不存在,那麼搜索過程就會永遠進行下去,永遠不作肯定答覆,也不作否定答覆。然而儘管如此,其答案是否定的。

在這裡筆者收縮了一下烏龜和阿基里斯的對話,感覺內容更加集中一點,而到這裡我們似乎可以回溯之前的兩個形式系統遊戲了:WJU形式系統和pq形式系統。所以關於“有窮搜索”和“無窮搜索”的內容其實早就在開篇就已經做了鋪墊了。

烏龜:“所以,如果你有了某個數,想測試一下它是否具有哥德巴赫性質或烏龜性質,兩種測試的差別就在於,前者涉及的搜尋過程是註定會終止的,而後者則有可能是無窮盡的——沒有任何保證。它會無休無止、沒完沒了,永遠給不出一個回答。然而另一方面,在某種情形下,它或許會在第一步時就停住了。

……那兩個相似的問題就是關於這兩個極為不同的性質的。哥德巴赫猜想如成立,則所有偶數具有哥德巴赫性質;哥德巴赫變奏如成立,則所有偶數具有烏龜性質。兩個問題都還有解決,但有趣的是,雖然它們看起來很相像,它們涉及到的確實有關全體整數的極為不同的性質。

阿基里斯:“我明白你的意思。哥德巴赫性質對於任何一個偶數來說是可檢測的,或者說是可識別的性質,因為我知道怎樣測試它是否存在——進行搜索就是了。這個過程必定會到達一個終點,並給出肯定的或否定的回答。而烏龜性質則難對付多了,因為盲目的搜索可能會永遠給不出回答。

數論最讓人感到沒有耐心的地方(可能主要對於沒有接受過專業訓練的人來說),在於其對於邏輯嚴謹的要求,當然其他理科領域也有一樣的要求(這種嚴謹是數學的基本,而數學又是其他科學的重要基礎,這就不言而喻了)。邏輯要嚴謹,則要求在公理基礎之上進行的每一個推理的步驟都必須要嚴格遵循規則來,這在介紹形式系統的時候就說過了。而困難的地方就在於,嚴格遵守推理規則的證明步驟往往會和巨大的甚至於“無限”的工作量有關係。這也是我們的思維很容易對這類工作產生疲勞的原因,我們的思維往往會憑藉直覺直接跨過步驟。

所以反過來說,數論的證明工作要保持如此嚴謹的邏輯證明的前提下,還要面對可能是“無限”的驗證步驟。最重要的就是首先劃分範圍(概念上):不論是“哥德巴赫猜想”,還是前面關於“費馬大定理”的證明。我們都看到了,我們首先要做的就是把這個問題的性質證明出來——“是否可以有窮證明”,然後再逐步的縮小範圍。以前面費馬大定理的證明來看也是差不多情況:先證明其在一些特定情況下是否成立,然後在此基礎上不斷擴大範圍,最後在過程中獲得了啟發,通過另一種可以”有限證明“的方式,驗證了這個定理。(關於哥德巴赫猜想的內容則在後面會詳細說說)。

烏龜和阿基里斯在這裡討論的就是類似的情況,對於”猜想“本身我們一時間可能束手無策,那麼就先找找類似問題的解法來給自己尋找啟發。(這是比較通俗的說法)

那麼上面這個說的例子是對於”肯定“答案的情況,”否定“的答案如何證明呢?(無法證明,則可以證偽,反之也如此,而只要結果出來之前,就不下定論)

烏龜:”也許對於烏龜性質會有一些更聰明的搜索辦法,按照其中的一個辦法做下去總能到達一個終點,並給出回答。

阿基里斯:”難道這一搜索不是僅僅在答案是肯定時才會終止嗎?

烏龜:”那倒不一定。沒準兒會有什麼辦法證明:一旦搜索的時間超過某一限度,回答就必定是否定的。甚至也可能會有某種其他的搜索素數的辦法——而不是這種盲目的方法——能在該性質存在時發現它,而若是不存在,也能給出回答。任何一種情形下否定的回答都只需有限的搜索。可我不知道這種事情是否能被證明。在無窮的空間裡進行搜索總是很難駕馭的,這你也知道。“(這裡其實已經可以涉及到圖靈的”停機問題“了,後面的章節會專門涉及這個內容,因為圖靈的”可計算理論“是計算機科學裡非常重要的一塊內容)

阿基里斯:“所以就目前來看,你知道對烏龜性質來說還沒有註定會終止的測試——然而沒準兒還是會有這樣一種搜索。

烏龜:“對。我可以設想某人從事對這種搜索的搜索,但我同樣不能保證這個‘元搜索’會終止。

阿基里斯:“這種怪異的情況給我的印象太深了,某個偶數——比如說一萬億——沒能具有烏龜性質,竟是由無窮多支離破碎的信息所導致的。想想也挺有趣,把這些信息都卷在一起打成捆,稱之為——就如你仗義的龜兄所說的——一萬億的‘阿基里斯性質’。它事實上是作為整體的數論系統的一個性質,而不只是屬於一萬億這個數的。

阿基里斯這裡提到的思路,可以聯想到之前的“組塊化”,不是以低層次的個體來進行證明(工作量太大以至於無法完成)。而是以高層次的概念——“通用性質”來進行證明。(比如不是一個一個數字列出來,而是假設:N是奇素數,則2N是偶數……那我們需要證明的就不是每一個奇素數或偶數,而是隻需要證明N和2N的性質就足夠了。)

烏龜:“這是個很有意思的見解,阿基,不過我還要補充一點,把這一事實與一萬億這個數聯繫在一起是很有意義的。為了能說明這一點,我建議你考慮一個簡單的陳述:‘29是一個素數’。好,事實上這個陳述確實就意味著2乘以2不等於29,5乘以6不等於29,如此下去,對吧!

但是你把這些事實蒐集起來,打成捆,並與29這個數聯繫起來,僅僅說上一句,‘29是素數’?

阿基里斯:“是的……

烏龜這裡似乎突然顧左右而言它,阿基里斯表現得也有點懵,但隨後烏龜就點名了自己想說的意思:“……但是你想想:兩個大於29的數的乘積不可能等於29這一事實涉及了全體整數系統結構。在這種意義下,那事實本身就概括了無窮多的事實。你不能逃避這一事實,阿基,當你說‘29是素數’時,你實際上表述了無窮多的事情。

阿基里斯:“也許是吧,可我覺得它像是單單一個事實。

烏龜:“那是因為有無窮多的事實已經包括在你預先擁有的知識裡了——它們隱含地嵌在你看待事物的方式中。你沒有看到明顯的無窮,是因為它已在你把握的圖像中被隱含地捕獲了。

對於一些我們常識中不言而喻的事情,我們往往不會去深想。然而類似數論這類的深度學科恰恰需要反其道而行之,這也是為什麼外行人接觸這類領域會被阻擋在門外。而且以烏龜所說的為例,我們似乎可以發現,幾乎所有的事物都有著:“一即全,全即一”的性質(一個個例包含著無窮個引申事實,哪怕關係上沒有那麼近,但它們卻是在邏輯上被聯繫著)。

烏龜:“也許看起來怪點兒,可這也是看待事物一種相當便利的辦法。現在我們還回到你那個假設性的想法。如果像你所說的,一萬億這個數具有阿基里斯性質,那麼不論你把它加上什麼樣的素數,你都不會得到另一個素數。這種狀況會由無窮多個別的數學‘事件’所導致。那麼所有這些‘事件’是否必須都是出自同意來源?它們是否必須有共同的緣起?因為若不是這樣,那些事實就是由某種‘無窮巧合’造成的,而非背後的規律性。

阿基里斯當然不同意烏龜的說法,他認為數論當中是不存在什麼“無窮的巧合”的,沒有任何事情不是出自於背後的某種規律。隨後阿基里斯找了一個範圍比較小的例子試圖說明他的看法,不過被烏龜給質疑了一下。嚴格來說阿基里斯不是錯誤的,但是卻也不完善。

阿基里斯:“難道還有人不同意這個觀點嗎?那麼這種人就必然要相信‘無窮巧合’了,他們必然相信在人類創造物種最完美、最和諧、最漂亮的部分——自然數系統——當中,也有紊亂。

烏龜:“也許他們就是這樣,可你是否想過,這種紊亂或許是美與和諧的不可分割的組成部分?

阿基里斯:“紊亂,完美的一部分?秩序與紊亂構成了悅人的整體?真是異端邪說!

烏龜:“據說你最喜歡的藝術家埃舍爾就在一幅畫裡暗示了這種異端觀點……說起紊亂這事,我相信你會有興趣聽聽兩類不同的搜索,兩種搜索都保證會終止。

阿基里斯當然有興趣,於是烏龜接著說了下去。

第一類搜索——非紊亂型的搜索——可以用一個關於哥德巴赫性質的測試來說明。你只需看那些小於2N的素數,如果某一對素數加起來得到2N,那麼2N就具有哥德巴赫性質,否則就不具有。這種測試不僅註定會終止,而且你還能預先知道什麼時候終止。

阿基里斯:“那麼這是個可預知其終止的測試嘍。你是不是要告訴我檢驗某些數論性質時,要用到那種雖然保證會終止,但預先無法知道會過多久才終止的測試?

烏龜:“你預見的太對了,阿基,這種測試的存在就說明自然數系統從某種意義上說帶有固有的紊亂。

阿基里斯:“這種情況下,我只好說人們還不夠了解那個測試。如果他們多做些研究,他們會弄清在終止前那個測試至多要花多少時間。無論如何,整數中的模式必定是有來由的,不可能只是一些無法預知的紊亂模式。

烏龜:“我可以理解你這種直覺信念,阿基。不過,這一點並非總能得到證實。當然,很多情況下你是絕對正確的——僅僅因為某人不知道某事,不能得出結論說那件事不可知。可是有那麼一些整數的性質,可以證明檢驗它們的有終測試是存在的,同時還能證明沒有辦法預先知道那些測試要花多少時間。

這裡在重點強調的一個部分就是:證明當中的“不可知”部分。雖然這個所謂的“不可知”,只不過是我們不知道證明多久才能結束——也就是說我們並不知道證明一直到結束當中存在著“多少”步驟。這和前面反覆強調的我們不知道多少“中間層次”多多少少可能是有一些對應的。但是要注意,這裡的不可知僅僅是我們沒有“全局結構”的瞭解,我們雖然不知道有多少“中間層”,但是每一個單獨層次我們還是能明白的;同理,這樣的證明裡面,隨便一個單獨的證明步驟我們是很清楚的。

烏龜:“……我來跟你說一個很容易定義的性質,然而卻還沒有一個檢驗它的有終止測試。我沒說永遠不會發現這樣一個測試,這一點請你注意——只是現在還沒有。我們從一個數開始吧——你來選一個數。

阿基里斯:“15怎麼樣?

烏龜:“很好。我們從你這個數開始。如果它是奇數,我把它乘以3,再加1。如果它是偶數,就取其一半。然後重複這個過程。如果一個數經過這樣的一些操作得到1,就稱之為‘妙極’的數,否則就稱之為‘非妙極’的。

這裡我們並不是在通過所謂的“測試”來了解一個數學規則,恰恰相反,這裡我們是藉由數學規則來感受一下這個“證明步驟”,值得注意的是重點何在,重點不在於我們說的內容,而是這個“證明”形式本身,這是非常重要的,否則這段內容看起來就會不知所云。

書裡這段證明如下:(有十六個步驟,就不打出來,直接上圖吧,這樣也跟直觀一些)

烏龜:“你注意了沒有,再這麼簡單定義的運算下,那些數是怎樣上下襬動的?

阿基里斯:“注意了。特別讓我吃驚的是,經過十三次運算後,我得到16,僅比我起步時的15大1.在某種意義上說我幾乎回到了出發點——而在另一種意義上,我已遠離了出發點。另外還有一點使我詫異的是為了解決問題,我不得不動用大到160那樣的一個數。我真想知道這都是為什麼。

烏龜:“是的,有個無窮的‘天空’供你飛,而且事先很難知道你會被拋到這天空裡多高的地方。而且很可能你會只是不斷地往高飛,越來越高,再也不下來了。

重點在於,當我們討論一個問題的時候,它是關於“形式”的問題還是關於“性質”的問題?如果是後者,它的麻煩程度恐怕就要超出想象了。因為抽象的問題從來都不受“形式”的規範,而當我們平時一般在思考這類問題的時候,之所以能夠有“終止”是因為我們在自己沒有意識到的部分(常識部分)已經給出了形式限定。

所以當中這些“步驟”其實已經被我們的大腦跳過了,這樣類似的情況其實早在最早的WJU形式系統遊戲裡就已經提到過了——U方式(總結歸納,然後跳過一些步驟直接走向“搜索終止”)。而現在當我們在做這個當下的討論的時候,我們思考我們自己的“思考”方式,這就呈現出來這種我們覺得完全無序,又覺得背後有點什麼的朦朧感覺中了。(自指狀態下,到處都是這種感覺,就像我們為什麼會覺得“悖論”還是有意義的)。

阿基里斯:“我想你是對的。這個‘妙極’問題真是奇妙至極了,就看那些數的擺動方式吧——一會兒增大,一會兒減小。模式應該是有規則的,可是表面上卻顯得相當紊亂。所以我完全能想象為什麼至今還沒有一個檢驗妙極性質的有終止測試。

烏龜:“說起有終止過程和無終止過程,還有那些介於兩者之間玩意兒,我想起了我的一個朋友。他是個作家,正在寫一本書。”(烏龜這裡說的朋友,其實指的就是侯世達自己,不過在對話裡用了一種幽默的方式來自指自己這本書——《金、銀、銅——聚寶藏之精華》……);注意這裡給出了一個“自指”(在這GEB本書的內容裡討論GEB這本書本身)。

阿基里斯:“……可我們的討論怎麼會讓你想起他的那本書了?

烏龜:“啊,是這樣。那本書裡有篇對話,在其中他想讓讀者去搜索終了,從而甩掉讀者。

阿基里斯:“竟會有這種願望,夠奇怪的。這怎麼做到呢?

烏龜:“你無疑會注意到,一些作者在他的故事結束前的幾頁裡如何費盡心機地建立起巨大的緊張狀態——可是那個把書捧在手上的讀者能感覺出故事就要結束了。所以,有某種額外的信息以一定的方式預先提醒了讀者。書的物理性質多少有點破壞了那種緊張。如果,比如說,在小說的終了處有許多廢話,那就會好多了。

記得前面提到的哥德堡變奏曲關於那個“終止式”的討論嗎,之後人們發現老版本哥德堡變奏曲的終止之後還能找到未盡的變化,並且通過“終止式”進一步演變出來了好幾個變奏(漫畫《風雲》裡劍聖的劍二十二衍化出劍二十三?)烏龜這裡說的就是這個了——而對應到他們在討論的是否有終止的搜索上來看,這樣的情況就對應了前面提到的“搖擺於有終止和無終止之間的搜索”。

烏龜:“對。我的意思是,有許多多餘的書頁,不是故事的真正組成部分,但能用來藏住終了,使得草率瀏覽或只憑對書的物理感覺都無法確切地得知終了在哪裡。”(也許有時候作者故事寫完了,讀者讀完卻總是覺得意猶未盡,希望故事還能繼續——DLC、番外篇。當然這個其實和烏龜說的沒什麼關係了,只是一點額外的聯想。)

阿基里斯:“我明白了。這樣的話,故事的真正終了可能會出現在,比如說,書的物理終了前五十頁或一百也了?……如果這能廣為實踐,會是很有效的。可是有個問題:假如這些廢話非常明顯——比如有許多空白,或者有充滿句號或滿篇雜亂無章的字詞的書頁,那還不如沒有……可是一般來說即使草率地瀏覽正常的一頁書也足以把一個故事同另一個故事區分開來。所以你必須把那些廢話弄得與真正的故事非常相似。

烏龜:“沒錯。我的設想是這樣;把故事講完後不中斷,繼續講下去,講一些看上去是該故事的繼續,而實際上只是些廢話,與真正的主題毫無關係的事。某種意義上說,這些廢話是種‘終了後的終了’,帶有與原主題幾乎無關的多餘的文學意象。

阿基里斯:“真夠狡猾的!可這就有個問題;你無法弄清真正的終了到底在哪兒,都混在廢話裡了……哎,我有個建議。可以把從真正的故事到廢話部分的轉折做成這樣:一個有智能的閱讀者對正文充分專注仔細地審查之後,能查明什麼地方是前者的結束、後者的開始。也許這會使他花費相當的時間。也許沒有辦法預先知道到底要花多長時間……但出版者能夠保證對真正終了的一個充分專注仔細的搜索一定會終止,即使他無法在其終止前說出到底要花多少時間。

這裡一段阿基里斯在和烏龜探討關於故事的終止,前面已經提醒了,這個“終止後的終止”在前面提到的哥德堡變奏曲的時候就已經提到了。但這裡如果僅僅是做形式上的對應的話就毫無意義,這裡使用的寫作方式和前面使用地圖比喻大腦的寫法是一個樣子——就是一個比喻,阿基里斯和烏龜討論的股市的寫作,這個故事就是比喻“搜索”:有明確結局的故事就是“有終止的搜索”、沒有明確結局的故事就是“沒有終止的搜索”而阿基里斯他們說的這種結尾之後意猶未盡的故事就是“介於終止和無終止之間的搜索”

對話到這裡主題看起來就結束了,但是實際上並沒有。很明顯侯世達想在形式上和內容上完全對應起來。原本烏龜和阿基里斯聊到這個關於“搜索”的“故事”比喻之後就打算結束對話了,但後面還是多寫了一段多餘的內容——“終止後的終止”。

烏龜打著哈欠準備回去了——他們原本是因為阿基里斯失眠,才開始聊關於“數論”的各種搜索的複雜問題為了打發時間的。阿基里斯為了像烏龜表示感謝,感謝它給自己陪聊,打算送給烏龜一個禮物。那個禮物是一個包包,阿基里斯說是一個珍貴的用“變造革”(不是人造革)做的包包。(這裡還隱射了一下康托爾的對角線方法的內容)。

結果烏龜剛收下,警察就衝進來了,說是博物館失竊了一個“變造革”做的包包,一路找到了這裡來。結果烏龜就倒黴的被逮起來了,阿基里斯乘機甩鍋——感情他這段時間失眠是因為做賊心虛啊……

哥德堡變奏曲第一版書皮

1·變奏曲

變奏曲是一種樂曲的結構形式,在一個樂曲的主題之後,緊接著將主題進行變化,而變化之後依然可以讓人認出原來的主題。這種變化可以產生在和聲、旋律、對位、節奏上,也可以由不同的配器方法在音色上求變化。這種變化就是主題變形,或叫“變奏”。變奏的次數不固定,可以變奏任意多次。曲式發展如:A(主題)+A1+A2+A3+A4……

變奏曲是一種古老的經典作曲方式,在一個主題上連續寫一系列器樂變奏的做法,最早出現於16世紀的西班牙琉特琴曲。16世紀晚期和17世紀初期的英國作曲家寫維吉那琴曲也用類似的方式作曲,當時所選的主題大多為流行歌曲。從那時起,“主題與變奏”一直是一種標準的曲式。到了後來,主題的選用除了當時的流行歌曲之外,也還會借用其他作曲家的“主題”——名稱上會標出。

變奏即可用於奏鳴曲和交響樂其中的一部分,後來也可以作為獨立的器樂曲作品。17世紀有人寫變奏組曲,其中幾個舞曲樂章有主題上的聯繫,實際上也就是建立在一個基本旋律上的一段段變奏。18世紀後期以來,變奏曲常用作奏鳴曲、交響曲一類作品的一個完整的樂章。從廣義來說,變奏是一切交響樂寫作不可或缺的要素。一個或幾個主題的展開便是將素材本身固有的各種可能性付諸實現,這本身就是一種變奏。

變奏曲中可以找到這樣一些基本要素:旋律變奏、音型或織體變奏、節奏變奏、調性變奏(如小調換大調或者反之)以及和聲變奏。同一段變奏中又可將幾種要素或全部要素結合起來。但是,變奏的藝術比僅僅利用這些基本類型要複雜得多,更重要的是把主題作為靈感的源泉,從中引申出各種初看似乎與主題關係不大的聯想。如何由此及彼,不應著眼於表面,而應該發自作曲家的想像。

巴洛克音樂時代比較著名的變奏曲有巴赫的《哥德堡變奏曲》,亨德爾的《和諧的鐵匠》系列。

在古典音樂時期,莫扎特寫了大量的變奏曲,莫扎特習慣在變奏曲的倒數第二樂章時讓節奏變慢,然後在最後一個樂章突然加快,並常用華彩即興演奏的形式;其中最有名的即為小星星變奏曲。海頓喜歡用雙變奏的形式,即用兩個相關的主題,一般一個是大調式另一個是小調式,互相進行變奏。

貝多芬一生也寫過不少變奏曲,有的在他的大型樂曲中應用,如《第三交響曲》的最後部分,《第十二鋼琴奏鳴曲》的開始部分,他最後一部《第32號鋼琴奏鳴曲》的第二部分等

舒伯特寫過5部變奏曲,最著名的是《死神與少女》絃樂四重奏,他的著名作品《鱒魚》鋼琴五重奏也包括對他自己創作的歌曲《鱒魚》的變奏。

浪漫主義音樂時期變奏曲形式更為重要,但一般作曲家不再單獨寫變奏曲,但勃拉姆斯的《亨德爾變奏曲》表現了他對古典主義音樂的偏愛。

20世紀又流行單獨的變奏曲,韋伯、布里頓、保羅·欣德米特等人都寫過獨立的變奏曲套曲。

有經驗的音樂家經常可以即興演奏變奏曲,在巴洛克音樂時期非常普遍,尤其是慢節奏的主題,可以使演奏者不斷地在變奏過程中完善主題。古典主義音樂時期也回即興演奏變奏曲,貝多芬的作品第77號《G小調幻想曲》幾乎就是一個小主題在他即興演奏後記下的樂譜。莫扎特的許多作品也是即興演奏後完善的。 即興演奏完善變奏也是爵士樂的主要創作方法。

變奏的一大要素是加工雕琢,因此為獨奏樂器寫的變奏曲(為室內樂重奏和樂隊寫的也一樣)必然要求精湛的演奏技巧。一些作曲家為發揮演奏技巧而熱衷於創作變奏曲。貝多芬探索以更加難以捉摸的方式賦予主題以新面貌。門德爾鬆的《嚴肅變奏曲》實際上是為了抗議,19世紀初像許多作曲家運用這一形式寫作內容空洞的音樂。到了後來的作曲家,如勃拉姆斯和埃爾加的變奏曲已遠非炫技之作,裡面包含了更多的內涵。

2·關於數論

數論在前面已經提到過了(不止一次,而且還有一些具體的例子),但是為了後面的內容這裡還是多嘴再說一句,這裡就直接引用維基百科的內容吧:

數論是純粹數學的分支之一,主要研究整數的性質。被譽為“最純”的數學領域。

正整數按乘法性質劃分,可以分成質數,合數,1,質數產生了很多一般人能理解卻又懸而未解的問題,如哥德巴赫猜想,孿生質數猜想等。即,很多問題雖然形式上十分初等,事實上卻要用到許多艱深的數學知識。這一領域的研究從某種意義上推動了數學的發展,催生了大量的新思想和新方法。數論除了研究整數及質數外,也研究一些由整數衍生的數(如有理數)或是一些廣義的整數(如代數整數)。

整數可以是方程式的解(丟番圖方程)。有些解析函數(像黎曼ζ函數)中包括了一些整數、質數的性質,透過這些函數也可以瞭解一些數論的問題。透過數論也可以建立實數和有理數之間的關係,並且用有理數來逼近實數(丟番圖逼近)。

數論早期稱為算術。到20世紀初,才開始使用數論的名稱,而算術一詞則表示“基本運算”,不過在20世紀的後半,有部分數學家仍會用“算術”一詞來表示數論。1952年時數學家Harold Davenport仍用“高等算術”一詞來表示數論,戈弗雷·哈羅德·哈代和愛德華·梅特蘭·賴特在1938年寫《數論介紹》簡介時曾提到“我們曾考慮過將書名改為《算術介紹》,某方面而言是更合適的書名,但也容易讓讀者誤會其中的內容”。

卡爾·弗里德里希·高斯曾說:“數學是科學的皇后,數論是數學的皇后。”

數論初期的鋪墊工作有三大內容

歐幾里得證明素數無窮多個。

尋找素數的埃拉託斯特尼篩法;歐幾里得求最大公約數的輾轉相除法。

公元420至589年(中國南北朝時期)的孫子定理。

以上工作成為現代數論的基本框架。

數論中期工作

在中世紀時,除了1175年至1200年住在北非和君士坦丁堡的斐波那契有關等差數列的研究外,西歐在數論上沒有什麼進展。

數論中期主要指15-16世紀到19世紀,是由費馬、梅森、歐拉、高斯、勒讓德、黎曼、希爾伯特等人發展的。最早的發展是在文藝復興的末期,對於古希臘著作的重新研究。主要的成因是因為丟番圖的《算術》(Arithmetica)一書的校正及翻譯為拉丁文,早在1575年Xylander曾試圖翻譯,但不成功,後來才由Bachet在1621年翻譯完成。

早期的現代數論

費馬:皮埃爾·德·費馬(1601–1665)沒有著作出版,他在數論上的貢獻幾乎都在他寫給其他數學家的信上,以及書旁的空白處。費馬的貢獻幾乎沒有數論上的證明,不過費馬重複的使用數學歸納法,並引入無窮遞降法。

費馬最早的興趣是在完全數及相親數,因此開始研究整數因數,這也開始1636年之後的數學研究,也接觸到當時的數學社群。他已在1643年研讀過巴歇版本的丟番圖著作,他的興趣開始轉向丟番圖方程和平方數的和。

初等數論

意指使用不超過高中程度的初等代數處理的數論問題,最主要的工具包括整數的整除性與同餘。重要的結論包括中國餘數定理、費馬小定理、二次互反律等等。

解析數論

藉助微積分及複分析的技術來研究關於整數的問題,主要又可以分為積性數論與加性數論兩類。積性數論藉由研究積性生成函數的性質來探討質數分佈的問題,其中質數定理與狄利克雷定理為這個領域中最著名的古典成果。加性數論則是研究整數的加法分解之可能性與表示的問題,華林問題是該領域最著名的課題。此外例如篩法、圓法等等都是屬於這個範疇的重要議題。

代數數論

引申代數數的話題,關於代數整數的研究,主要的研究目標是為了更一般地解決不定方程的問題,而為了達到此目的,這個領域與代數幾何之間有相當關聯,比如類域論(class field theory)就是此間的顛峰之作。

算術代數幾何

研究有理係數多變數方程組的有理點,其結構(主要是個數)和該方程組對應的代數簇的幾何性質之間的關係,有名的費馬最後定理、莫德爾猜想(法爾廷斯定理)、Weil猜想,和千禧年大獎難題中的貝赫和斯維訥通-戴爾猜想都屬此類。

幾何數論

主要在於透過幾何觀點研究整數(在此即格子點)的分佈情形。最著名的定理為閔可夫斯基定理。

計算數論

藉助電腦的算法幫助數論的問題,例如素數測試和因數分解等和密碼學息息相關的話題。

超越數論

研究數的超越性,其中對於歐拉常數與特定的黎曼ζ函數值之研究尤其令人感到興趣。

組合數論

利用組合和機率的技巧,非構造性地證明某些無法用初等方式處理的複雜結論。這是由保羅·埃爾德什開創的思路。

模形式

數學上一個滿足一些泛函方程與增長條件、在上半平面上的(復)解析函數。

——摘自維基百科‘數論’詞條。”

3·康托爾的對角線論證

康托爾的名字早在第二篇筆記的時候就出現過了,他是數學歷史上地位舉足輕重的人,因為就是他發明了“樸素集合論”為當今數學體系開創了基礎。當然作為奠基者,遭遇挫折也是必然的,康托爾的集合論遭遇了“悖論”,所以後面才有了進一步的發展,更加嚴謹的現代集合論在試圖解決一些問題,當然有些問題到今天還沒有完全解決完。

這裡提到康托爾不是完全沒有道理的,對角論證法是喬治·康托爾於1891年提出的用於說明實數集合是不可數集的證明方法。這樣一來我們直接就明白了為什麼這裡要提康托爾的對角線論證了,就像我們在面對的論題一樣——“對於無限空間的探索”。

對角線法並非康托爾關於“實數不可數”的第一個證明,他的第一個證明既未用到十進制展開也未用到任何其它數系。最早的原始證明發表於 1874年,這個證明使用了較為複雜的歸納反證法。1891年他用對角線法重新證明了這個定理。

康托爾提出了通過一一對應的方法對無限集合的大小進行比較,並將能夠彼此建立一一對應的集合稱為等勢,即可以被認為是“一樣大”的。他引入了可數無窮的概念,用來指與自然數集合等勢的集合,並證明了有理數集合是可數無窮,而實數集合不是可數無窮,這表明無窮集合的確存在著不同的大小,他稱與實數等勢(從而不是可數無窮)的集合為不可數無窮。

這裡涉及到一些集合論的概念,必須要先了解一下,才能明白康托爾的對角線論證是在幹什麼。首先是“可數集”這個概念(先明白“可數集”才能明白康托爾證明的“不可數集”):在數學上,可數集,或稱可列集,是與自然數集的某個子集具有相同基數(等勢)的集合。在這個意義下,可數集由有限可數集和可數無窮集組成。不是可數集的無窮集稱為不可數集。這個術語是康托爾創造的。可數集的元素,正如其名,是“可以計數”的:儘管計數有可能永遠無法終止,集合中每一個特定的元素都將對應一個自然數。

等勢在數學領域中,是指如果兩個集合A和B是等勢的,那麼這兩個集合之間存在一個雙射——這個雙射簡單來說就是兩個集合之間的元素存在唯一對應的情況:也就是集合A映射至集合B,則每一個集合A內的元素a,存在唯一一個在集合B內的元素b與其對應。值得一提的是:在抽象代數中,保持結構的雙射關係可以叫——“同構”。)

可數集”這個術語有時也指代可數無窮集,即僅代表能和自然數集本身一一對應的集合。兩個定義的差別在於有限集合在前者中算作可數集,而在後者中不算作可數集。為了避免歧義,前一種意義上的可數有時稱為至多可數,後一種可數集則稱為無限可數集。

可數無窮,是指集合中的元素可以與自然數一一對應,也就是說可以用自然數來"數"它的數量,從而其數量為可數無窮。

比如說:整數的全體可以和自然數一一對應;偶數的全體可以和自然數一一對應;奇數的全體可以和自然數一一對應;同樣,有理數也可以和自然數一一對應。

採用如下法則對上述例子驗證,從而更好地理解"可數+無窮"的概念:

1.驗證整數可以和自然數一一對應:讓n表示任意自然數(不為0),則整數的全體為{-n,n,0}.讓0對應自然數中的1;讓1對應自然數中的3,讓2對應自然數中的5,即讓正整數n對應自然樹2n+1;同時,同理,讓-n對應2n.你可以驗證,通過這個對應法則,自然數與整數一一對應。

2.讓0對應1;讓2對應3,讓4對應5,讓6對應7,即讓非負偶數2n對應自然數2n+1;同理,讓負偶數-2n對應自然數2n.你可以驗證,這也是一個一一對應關係。

那麼“可數集”是如此,那麼“不可數集”的概念也就能明白了。不可數集是無窮集合中的一種。一個無窮集合和自然數之間要是不存在一個對應關係(雙射),那麼它就是一個不可數集。集合的不可數性與它的基數密切相關:如果一個集合的基數大於自然數的基數,那麼它就是不可數的。

百度百科上有一個很詳細的證明步驟(和維基百科的一模一樣,畢竟這是已經進了教科書的內容,所以這裡就直接引用了):

對角論證法證明實數集合為不可數集

康託的原始證明表明區間[0,1]中的點數不是可數無窮大。該證明是用反證法完成的,步驟如下:

1·假設(從原題中得出)區間[0,1]中的點數是可數無窮大的

2·於是乎我們可以把所有在這區間內的數字排成數列, (r1,r2,r3,...),已知每一個這類的數字都能以小數形式表達。我們把這些數字排成數列(這些數字不需按序排列; 事實上,有些可數集, 例如有理數也不能按照數字的大小把他們全數排序,但單只是成數列就沒有問題的)在部份有多種表達形式的數字上,例如0.499 = 0.500, 我們選擇前者.

3·如果該數列小數形式表現如下:

r1 = 0 . 5 1 0 5 1 1 0

r2 = 0 . 4 1 3 2 0 4 3

r3 = 0 . 8 2 4 5 0 2 6

r4 = 0 . 2 3 3 0 1 2 6

r5 = 0 . 4 1 0 7 2 4 6

r6 = 0 . 9 9 3 7 8 3 8

r7 = 0 . 0 1 0 5 1 3 5...

4.考慮rk小數點後的第k個位,為了方便起見, 我們底間並粗體這些數字,從下圖你應明白為什麼這個證明被稱為對角論證法

r1 = 0 . 5 1 0 5 1 1 0

r2 = 0 . 4 1 3 2 0 4 3

r3 = 0 . 8 2 4 5 0 2 6

r4 = 0 . 2 3 3 0 1 2 6

r5 = 0 . 4 1 0 7 2 4 6

r6 = 0 . 9 9 3 7 8 3 8

r7 = 0 . 0 1 0 5 1 3 5...

5.我們設一實數x, 其中x是以以下的方式定義的

如果rk的第k個小數位等於5,那麼x的第k個小數位是4

如果rk的第k個小數位不等於5,那麼x的第k個小數位是5

6.明顯地x是一個在區間[0,1]內的實數,以之前的數為例, 則相對應的x應為 0 . 4 5.5 5 5 5 4

7.由於我們假設(r1,r2,r3,...)包括了所有區間[0, 1]內的實數,所以一定有一個rn = x

8.但由於x的特殊的定義,這使得x和rn的第n個小數位是不同的,所以x不屬於(r1,r2,r3,... )

9.所以(r1,r2,r3,...)並不能羅列所有區間[0, 1]內的實數,這發生了矛盾。

10.所以在第一點內所提出的假設"區間[0,1]中的點數是可數無窮大的"是不成立的。——證明完畢

康托爾的“對角線方法”精巧、令人讚歎。這個證明方法同時也為後面一些列的概念和系統提供了基礎——甚至是悖論。畢竟康托爾的集合論被髮明出來之後,他自己就發現了集合悖論,最後還引發了第三次數學危機。(所以數學領域之間的各個分支其實又是環環相扣的,很多概念和內容當中互相都有關聯)

“對角線證法"是康托爾在無窮集合的研究中得出的。1873年康托爾在他與戴德金的一次通信中提出實數集是否能和自然數集構成一一對應的問題。康托爾於1874年的文章給出了一個複雜的證明之後,他又給出了一個不依賴於無理數的技術性的證明,這就是熟知的優美而深刻的“對角線證法"。

這是用完全直觀的無窮階方陣的“對角線”構造了一個不包含在某個假設為已知的集合的元素,也就是在一個特定的系統中構造一個“自我否定”,這正是這一方法的實質。在悖論各種證明中,“對角線證法’’得到了離開直觀的發揮和推廣。“對角線證法”不斷地反覆出現在遞歸函數論、計算機科學中。還出現在哥德爾第一不完全性定理的證明和A.塔斯基關於真理的論證中。

英國邏輯學家湯姆遜在1962年發表的論文《論一些悖論》,對一些悖論的構成方法進行了分析。指出羅素悖論、理髮師悖論、格雷林悖論、理查德悖論都是建立在康託對角線證法之上。現代一些邏輯學家幾乎把所有邏輯悖論(集合論的和語義學方面的)都叫做“對角線悖論”,包括著名的哥德爾不完全性定理。

“康托爾對角線”恰恰是一種以“有窮”探索“無窮空間”的方式,這就是為什麼在這裡要反覆暗示康托爾的名字的原因。另外一個方面來說,這部分也是現代數學很多理論構建的入口。因為“集合論”對於如今數學重要性已經不言而喻了。而且還不僅僅如此——上述的“同構”也起著重要作用,恰恰是“同構”讓數學中行之有效的方式可以延伸到其他方面:物理、化學、計算機……乃至一起可以和數學“同構”(掛上鉤)的學科領域。

哥德巴赫本人

4·哥德巴赫猜想

哥德巴赫猜想(Goldbach's conjecture)是數論中存在最久的未解問題之一。這個猜想最早出現在1742年普魯士人克里斯蒂安·哥德巴赫與瑞士數學家萊昂哈德·歐拉的通信中。用現代的數學語言,哥德巴赫猜想可以陳述為:任一大於2的偶數,都可表示成兩個素數之和

這個猜想與當時歐洲數論學家討論的整數分拆問題有一定聯繫。整數分拆問題是一類討論“是否能將整數分拆為某些擁有特定性質的數的和”的問題(注意,這是“一類”問題,哥德巴赫猜想只是其中一種,這就是為什麼在上文對話裡說它存在種種“變奏的原因”),比如能否將所有整數都分拆為若干個完全平方數之和,或者若干個完全立方數的和等

將一個給定的偶數分拆成兩個素數之和,則被稱之為此數的哥德巴赫分拆。比如:“4 = 2 + 2、6 = 3 + 3、8 = 3 + 5、10 = 3 + 7 = 5 + 5、12 = 5 + 7、14 = 3 + 11 = 7 + 7……”

簡而言之,哥德巴赫猜想主張每個大於等於4的偶數都是哥德巴赫數——可表示成兩個素數之和的數。哥德巴赫猜想也是二十世紀初希爾伯特第八問題中的一個子問題。

其實,也有一部分奇數可以用兩個素數的和表示,大多數的奇數無法用兩個素數的和表示,例如:15=2+13 ,而 23、35等數則無法用兩素數的和表示。

哥德巴赫猜想存在另一個較弱的版本(也稱為弱哥德巴赫猜想)是聲稱大於:“5的奇數都可以表示成三個素數之和。”(對話裡烏龜提到了類似的情況,是“變奏”之一)這個猜想可以從哥德巴赫猜想推出。1937年,蘇聯數學家伊萬·維諾格拉多夫證明了每個充分大的奇數,都可以表示成三個素數之和,基本證明了弱哥德巴赫猜想。

哥德巴赫猜想在提出後的很長一段時間內毫無進展,直到二十世紀二十年代,數學家從組合數學與解析數論兩方面分別提出瞭解決的思路,並在其後的半個世紀裡取得了一系列突破。目前最好的結果是中國數學家陳景潤在1973年發表的“陳氏定理”(也被稱為“1+2”)。

哥德巴赫猜想在中國可以說是耳熟能詳,這主要是歸因於中國當代作家徐遲發表於《人民文學》雜誌1978年第1期的報告文學作品,題目就叫《哥德巴赫猜想》。這篇文章詳細描寫了陳景潤的身世和在文化大革命期間的困難條件下證明“陳氏定理”的過程。

這篇報告文學作品影響力巨大,在徐遲的報告文學影響下,哥德巴赫猜想成為了中國民間科學愛好者熱衷研究的數學問題之一。不少民間科學愛好者對哥德巴赫猜想產生興趣,許多人自稱在此問題上取得了進展,甚至自稱證明了哥德巴赫猜想。中國科學院每年都收到“幾麻袋”的討論或聲稱證明了哥德巴赫猜想的來信來稿。不少報章也刊登過哥德巴赫猜想被民間科學愛好者證明的消息。但這些證明基本都是錯誤的,缺乏足夠專業訓練的人很多甚至都沒有辦法正確理解這個內容。但之所以會讓很多人陷入迷霧當中,產生這個問題自己也可以解決的“假象”是因為哥德巴赫猜想本身表述的內容確實非常“淺顯易懂”。(實際上大多數“數論”問題也都是這樣)。目前中國科學院已聲明不會審理來自科學共同體之外的任何自稱證明了哥德巴赫猜想的文章。

我們不妨來看看哥德巴赫猜想的歷史:

1742年6月7日,普魯士數學家克里斯蒂安·哥德巴赫在寫給瑞士數學家萊昂哈德·歐拉的通信中,提出了以下的猜想:“任一大於2的整數都可以寫成三個質數之和。”

上述與現今的陳述有所出入,原因是當時的哥德巴赫遵照的是“1也是素數”的定義。(關於1是不是“素數”的爭論在之前的筆記裡提過一句,關於這個問題一直有爭議,而且影響非常巨大,因為這會影響整個“素數”的定義)現今數學界已經不使用這個定義了。哥德巴赫原初猜想於是就變成了:任一大於5的整數都可寫成三個質數之和

歐拉在6月30日的回信中註明此一猜想可以有另一個等價的版本:任一大於2的偶數都可寫成兩個質數之和。

歐拉將此一猜想視為一定理,但他卻無法證明。今日常見的“猜想”陳述實際上是歐拉的版本,也被稱為“強哥德巴赫猜想”或“關於偶數的哥德巴赫猜想”。

從關於偶數的哥德巴赫猜想,可推出:任一大於5的奇數都可寫成三個素數之和

後者稱為“弱哥德巴赫猜想”或“關於奇數的哥德巴赫猜想”。若關於偶數的哥德巴赫猜想是對的,則關於奇數的哥德巴赫猜想也會是對的。1937年時前蘇聯數學家維諾格拉多夫已經證明充分大的奇素數都能寫成三個素數的和,也稱為“哥德巴赫-維諾格拉多夫定理”或“三素數定理”。2013年,祕魯數學家哈洛德·賀歐夫各特等人將維諾格拉多夫的結論進一步加強,並驗證了較小的奇素數的情況,宣稱完全證明了弱哥德巴赫猜想。

哥德巴赫猜想相當困難。直至今日,數學家對於哥德巴赫猜想的完整證明沒有任何頭緒。事實上,從1742年這個猜想正式出現,到二十世紀初期,在超過160年的時間裡,儘管許多數學家對這個猜想進行了研究,但沒有取得任何實質性的進展,也沒有獲得任何有效的研究方法。二十世紀以前對哥德巴赫猜想的研究,僅限於做一些數值上的驗證工作,提出一些等價的關係式,或對之做一些進一步的猜測。1900年,希爾伯特在第二屆國際數學家大會上提出的著名的二十三個希爾伯特問題之中的第八個問題,就包括了哥德巴赫猜想和與它類似的孿生素數猜想。希爾伯特的問題引發了數學家的極大興趣,但對於哥德巴赫猜想的研究仍舊毫無進展。1912年第五屆國際數際數學家大會上,德國數論專家愛德蒙·朗道曾經說過,即使要證明每個偶數能夠表示成K個素數的和,不管K是多少,都是數學家力所不及的。1921年,英國數學家戈弗雷·哈羅德·哈代曾經在哥本哈根數學會議的一次演講中聲稱:“哥德巴赫猜想的困難程度可以與任何一個已知的數學難題相比”。

一直到2013年,弱哥德巴赫猜想已經獲得了完全的證明。而這麼多年來,對於哥德巴赫猜想的研究工作始終沒有停止過。由於問題本身的艱難,於是為了找尋突破,數學家們紛紛尋找這個問題的拓展版本,然後逐漸向主題靠攏(農村包圍城市……)

無論是哈代和利特爾伍德等人使用的“圓法”證明、布朗使用“篩法”的證明,都為後續的工作打下了基礎。(埃拉託斯特尼篩法在之前關於“素數”的內容裡提過,簡單來說就是這個方法可以篩選一定範圍內的“素數”)。

這兩種思路都在二十世紀中得到了極大的發展。1933年,蘇聯數學家列夫·傑里科維奇·史尼爾曼同樣基於篩法證明了:存在某個整數K,使得每個偶數能夠表示成K個素數的和,彌補了朗道的遺憾。史尼爾曼給出的K的上限是800000,不久後羅曼諾夫證明了這個K不會超過2208。

1936年,朗道和彼得·希爾克把結果改進到71,一年後意大利數學家吉奧凡尼·裡奇又將結果改良為67。

1938年,華羅庚證明了弱哥德巴赫猜想的一個推廣:任意給定一個整數k,每個充分大的奇數都可以表示p1 + p2 + p3^k的形式。當k = 1的時候,就是弱哥德巴赫猜想。

1956年,Sharpio證明了K不超過20,

1956年尹文霖證明了K不超過18。

1976年,英國數學家羅伯特·查爾斯·沃恩證明了K小於等於6。

弱哥德巴赫猜想已經基本得到解決(2013年已經獲得完全的證明),對於偶數的哥德巴赫猜想,數學家們則主要將希望放在布朗的“篩法”上。

使用布朗方法的最好結果是陳景潤得到的。他在1973年發表了“1+2”的證明,其中對篩法作出了重大的改進,提出了一種新的加權篩法。因此“1+2”也被稱作是陳氏定理。現今數學家們普遍認為,陳景潤使用的方法已經將篩法發揮到了極致,以篩法來證明最終的“1+1”的可能性已經很低了。布朗方法似乎在最後的一步上停止了下來。如今數學界的主流意見認為:證明關於偶數的哥德巴赫猜想,還需要新的思路或者新的數學工具,或者在現有的方法上進行重大的改進,也有認為僅僅基於現有的方法上的改進是無法證明偶數哥德巴赫猜想。

回想到之前筆記裡講述過關於“費馬大定理”的證明過程,有沒有發現數論的證明工作似乎都有些相似的地方?確實是,而且這也就是這一章想要講述的重要主題:有窮步驟探索無窮。(這已經說了好幾遍了:重要的事情說三遍2333)這就是困難所在。

這個問題對於人工智能的意義所在,相信說到這裡有的人已經能明白了。如果把我們自身的“思維”對應到數論當中,就好比那個“無窮“的“數”。而我們的大腦硬件就好比是”有窮“的”證明“一樣。找出這之間的對應的”抽象“關係也許能成為了解”智能“的關鍵,同時也別忘了並不只有這一個、一種、一類……它還存在多個變奏版本。

陳景潤

三:三種搜索:BlooP、FlooP、GlooP

BlooP、FlooP和GlooP不是神話中的巨人,不是唐老鴨的小侄子們,也不是船沉時發出的冒泡聲——它們是三種計算機語言,其中每種都有特殊的用途。這些語言是專門為本書的這一章發明的。它們將被用來解釋‘遞歸’這個詞的某些新意義——特別是‘原始遞歸’和‘一般遞歸’這兩個概念。事實將證明,這些語言有助於闡明TNT中自我相關的機制。

在計算機科學中這裡提到的“原始遞歸”和“一般遞歸”涉及到可計算性理論的概念。可計算理論在數理邏輯範疇內也可以叫做遞歸論,是數理邏輯的一個分支。它起源於對可計算函數和圖靈度的研究。它的領域包括一般性的可計算性和可定義性的研究。遞歸論所考慮的基本問題是:“給定一個從自然數到自然數的函數f,f是否是可以被計算的”。

“可以被計算”,我們先將它當作一個直觀的概念。根據直覺,我們一般會認為,一個函數可以被計算是存在一個給定的運算過程,接受一個自然數n後,該過程進行一定的操作並給出f(n)作為輸出。將計算這一直觀的概念上升到數學層面的形式化定義(計算—推導規則),這工作是遞歸論的根本,並由哥德爾、邱奇、圖靈、克萊尼和Emil Post等人在1930年代奠定。他們將圖靈可計算性作為有效計算的形式化。(這裡為後面涉及邱奇-圖靈論題的概念已經做下鋪墊了,後面會有專門一個章節來講述這個題目的)

在瞭解了遞歸論的基本概念之後,一方面人們將這個概念應用於數學中,從而證明了一系列自然的問題,如字問題,以及希爾伯特第十問題等問題是“不可計算”的。另一方面,理論家們進一步拓展,開始了相對可計算性,圖靈度等問題的研究。數理邏輯中的可計算性理論家經常研究相對可計算性、可歸約性概念和程度結構的理論。如今,遞歸論仍是數理邏輯中活躍的領域。

相對而言計算機科學家他們則研究次遞歸層次,可行的計算和公用於可計算性理論研究的形式語言。在這兩個領域(計算機科學和數理邏輯)之間有著相當大的知識和方法上的重疊,而沒有明顯的界限。

這裡還可以涉及到計算理論,計算理論的“計算”並非指純粹的算術運算(Calculation),而是指從已知的輸入透過算法來獲取一個問題的答案(Computation),因此,計算理論同時屬於計算機科學和數學這兩個範疇。

其中的理論是現代密碼協議、計算機設計和許多應用領域的基礎。該領域主要關心三個方面的問題:

1·採用什麼計算模型(即形式語言、自動機)

2·解決哪些是能計算的、哪些是不能計算的(即可計算性理論及算法)

3·要用多少時間、要用多少存儲(即計算複雜性理論)

這三方面的問題可以用一個問題來總括:“計算機的基礎能力及限制到什麼程度?

那麼在計算機科學中,可計算性理論(Computability theory)作為計算理論的一個分支,就是研究在不同的計算模型下哪些算法問題能夠被解決。相對應的,計算理論的另一塊主要內容,計算複雜性理論考慮一個問題怎樣才能被有效的解決。

我們似乎很突然地從大腦和心智跳到了數學和計算機科學中的技術。雖然這個跳躍從某些方面來看有點突然,但它還是有意義的。我們已經看到,某種自我意識似乎是意識的關鍵所在。現在我們要在更形式化的背景下進一步分析‘自我意識’,例如在TNT的背景下。在TNT和心智之間還有很大一段距離,但一些想法將會是富有啟發性的,或許會以隱喻的方式被傳回到我們關於意識的思考之中。

1·足夠“複雜”?——再看哥德爾不完備性定理

在前面已經說過了,當我們面對一個特別艱深的問題的時候,如果我們沒有辦法直接解決它,我們可以選擇先“繞路”:先解決這個問題的“變奏”(簡化)版本,然後以此為思路逐漸接近最後的問題解決。數論當中那些艱深的問題無一不是這麼解決的:“費馬猜想”、“哥德巴赫猜想”、“希爾伯特問題”……無一不是如此。

說到人工智能上來,這其中最深奧的問題就在“自我意識”這一塊了。關於這個問題的討論多如繁星,但要想確實的解決這個問題,還是應該先做點什麼,為後面的來者鋪路。人工智能的“自我意識”我們無法直接獲得,那麼我們不妨看一看這個問題的一個非常簡單的“變奏版本”——“機械自動化”。這在前面也有提到過:——形式推理自動化(記不記得關於歐幾里得證明素數的那個證明“推廣”?)

關於TNT的自我意識,令人驚奇的一點就是它密切的聯繫於自然數中的有序與無序問題。特別是我們將會看到,一個充分複雜以至能反映自身的有序系統不可能是完全有序的——它必定包括某種奇怪的無序特徵。對於那些具有某種阿基里斯式想法的讀者來說,這將是很難接受的。但是,存在一種‘魔術式的’補償——存在某種關於無序的有序,這本身已經形成了一個研究領域,成為‘遞歸函數論’。遺憾的是,我們所能做到的,只是略微展示一下這個課題的魅力。

“遞歸函數”暫且先放到後面,這裡其實還在繼續一個之前就討論過的內容——依舊是哥德爾不完備性定理。話題又回到了之前的“龜蟹之戰”——也就是關於“完備唱片機”的那次爭論上,不知道還有沒有人記得這個內容,簡而言之,就是用唱片機播放唱片來比喻哥德爾不完備性定理在形式系統當中的運行情況——“每一個唱機都會有一個唱片,剛好可以播放出產生共振效果的音波,從而導致唱片機自毀。”

像‘足夠複雜’或‘足夠強有力’及類似的說法,在前面已經多次出現了。但這些說法是什麼意思呢?讓我們回到龜蟹之戰,並問這樣一個問題:‘是什麼使某個東西有資格稱為一臺唱機的?’螃蟹可能會聲稱它的冰箱是一臺‘完備的’唱機。然後為了證明這一點,它可能會隨便拿個唱片放在冰箱頂上,說:‘你看——它在播放唱片了。’而烏龜,如果想要反駁這個禪宗式的行動。就必須說:‘不——你的冰箱保真度太低,已經不能算是唱機了:它根本不能重現唱片上記錄的聲音(更不必說那種讓它自我破壞的聲音了)’。”這裡要注意了,不完備性定理本身針對的是“足夠強力”的系統,也就是說不能隨便亂套用——這裡要跳脫自然語言的自由語義,而嚴格遵守“專門的定義”。

再回過頭來看一遍哥德爾的兩個不完備性定理:

1·任何兼容的形式系統,只要蘊涵皮亞諾算術公理,就可以在其中構造在體系中不能被證明的真命題,因此通過推演不能得到所有真命題(即體系是不完備的)。

2·任何邏輯自洽的形式系統,只要蘊涵皮亞諾算術公理,它就不能用於證明它本身的兼容性。

所以書中經常出現的:“足夠複雜的”、“足夠強的”、“足夠保真度的”……在這裡應該就是指“蘊含皮亞諾算術公理”的意思。這個算術公理在之前就介紹過了,皮亞諾五大算術公理可以建立起一個“一階邏輯”:一階邏輯是使用於數學、哲學、語言學及計算機科學中的一種形式系統。一階邏輯出現過許多種名稱,包括:一階斷言演算、低級斷言演算、量化理論或謂詞邏輯。一個一階邏輯,若具有由一系列量化變量、一個以上有意義的斷言字母及包含了有意義的斷言字母的純公理所組成的特定論域,即是一個一階理論。

通俗點的說法:“能講明白,定義一些講法概念。”如同形式系統當中的:“公理”。它是構建起系統的基礎,比如歐幾里得幾何裡的“四大公設”之類。公理本身就是自可證——對應到唱機比喻裡,放唱片能放出聲音來的才叫“唱機”。

實際上是存在完備的情況的,這在之前就說過,但問題在於,完備的系統“強度有限”——哥德爾完備性定理:在一階謂詞演算中所有邏輯上有效的公式都是可以證明的。

上述詞語“可證明的”指的是有著這個公式的形式演繹。這種形式演繹是步驟的有限列表,其中每個步驟要麼涉及公理要麼通過基本推理規則從前面的步驟獲得。給定這樣一種演繹,它的每個步驟的正確性可以在算法上檢驗(比如通過計算機或手工)。

所以哥德爾定理是一階邏輯的定理,故最終只能在這個有限框架內理解。在形式邏輯中,數學命題及其證明皆以一種符號語言描述,只要檢查每一個證明的有效性,便可從一組公理開始無可辯駁地證明一條定理。理論上,這樣的證明可以在計算機上檢查,事實上這樣的有效性檢查程序也已經有了。

為了這個證明過程得以進行,必須要確定手頭有什麼樣的公理。可以從一組有限的公理集合開始,例如歐幾里得幾何的公設。或者更一般地,由一個可以允許無窮的公理列表開始,只要能機械地判斷給定的命題是否是一條公理就行。在計算機科學裡面,這被稱為公理的遞歸集。(公理看作定理的前提,定理變成公理,就繼續能推出定理,於是它就又變成了後一個定理的前提……)儘管無窮的公理列表聽起來有些奇怪,實際上自然數的通常理論中(皮亞諾算術公理)就是如此。

“……說TNT是一個形式化的N(數論),其原因是TNT的符號以正確的方式活動:這也就是指它的定理不像並相似的一聲不響——它們確實說出了N中的真理……那麼,這些N中的‘核心真理’是什麼?它們是‘原始遞歸真理’,這就是說,它們僅僅涉及到‘可預測其終止’的計算。這些核心真理在N中的作用就像歐幾里得的前四個公設在幾何學中的作用一樣:它們使你可以在比賽開始前就能淘汰掉某些‘力量不夠強’的選手。從此以後,‘全部原始遞歸真理的可體現性’將作為我們稱一個系統為‘足夠強有力’的判別標準。

哥德爾的第一條不完備定理表明任何一個允許定義自然數的體系必定是不完備的:它包含了不能在此體系內以一階謂詞邏輯形式證明的命題,並且該命題的否命題也不能在該體系內以一階謂詞邏輯的形式證明。

存在不完備的體系這一事實本身並不使人感到特別驚訝。例如,在歐幾里得幾何中,如果把平行公設去掉,就得到一個不完備的體系。不完備的體系可能只意味著尚未找出所有必須的公理而已。(所以一階邏輯雖然“完備”但是“強度有限”,從後面這個強度的概念來理解,它還是不完備的——並不能推導出所有“定理”。)

哥德爾不完備性定理揭示的是在多數情況下,例如在數論或者實分析中,永遠不能找出公理的完整集合。換句話說,每一次將一個命題作為公理加入,將總有另一個命題出現在所能形式證明的範圍之外。

如果你有數論的一個足夠強有力的形式化體現,那麼哥德爾定理就是可應用的,結果你的系統即是不完備的。另一方面,如果你的系統不是足夠強有力的(即不是所有原始遞歸真理都是定理),那麼你的系統由於有這個缺陷,也是不完備的。……另一點需要注意的是,這完全平行於《對位藏頭詩》中的‘高低保真度之別’。

2·無序中的有序

實際上,人們發現很弱的系統依然是會受到哥德爾方法攻擊的。‘所有原始遞歸真理都需要體現成定理’,這個標準過於嚴格了……

現在,在我們進入對原始遞歸函數的謂詞的詳細討論之前,我想把這一章的主題和前幾章的主題聯繫起來,一提供一個更好的背景。

實際上我相信一直在看筆記的讀者可能已經注意到了,前面的內容經常被反覆提起。這是很重要的,有些時候不提前面的內容,當下的內容幾乎就看不不懂。之前出現過的三個形式系統,基本上已經非常形式化的展現了後面要說的諸多理論。當然這些例子對於專業的人士來說可能先得非常淺顯易懂,而對於非專業的讀者來說基本上就是不知所云了——主要差距就在於腦子裡有這麼多概念,或者沒有這麼多概念、還有一個就是一個思維方式的問題:專用語言區別於自然語言的意義

我們很早就已經看到,形式系統可能是難以駕馭的,因為它們有加長和縮短符號串的規則,這可能會導致在大量符號串中進行無終止的搜索。哥德爾配數法發現,顯示了任何對一個具有特殊的符號性質的串的搜索都有一個算術中的表兄弟:對一個具有相應的特殊算術性質的整數的同構搜索。”(聯繫到前面提過的,集合論當中的概念術語:“等勢”、“雙射”。)

在本章前面的對話中,我可能過分強調了和整數有關的問題中顯示出的無序現象。事實上,和‘妙極性’問題相比,人們已經馴服了一些更復雜的無序現象,發現它們不過是些很溫順的傢伙。

來對比一下下列的兩個數列:

7、8、5、3、9、8、7、6、3、3、9、7、4、4、8、3、0、9、6、7、5、6、6、0、8……

另一個是:

1、-1/3、+1/5、-1/7、+1/9、-1/11、+1/13、-1/15……

先來看第一個數列,能找出規律來說出省略號後面下一位數嗎?似乎不行,看起來第一個數列是隨機的。那麼第二個序列呢?省略號後面一個數該是什麼?估計有人看出來了:+1/17那麼這有什麼關係呢?實際上上下兩個數列直接的構成規律是有關聯的。簡而言之,第一個數列只不過是第二個數列的和的十進制小數部分(展開式)的開始幾位,這個數列的和是:π/4

所以說第一個數列並不是隨機的,只是表面上看似隨機,而背後實際上是有更抽象的規律。(用了好幾個數學技巧拐彎抹角的構築)

自然規律恰恰是以這種方式被發現的。自然只是提供給我們大量的現象,它們表面上雜亂無章,知道我們選擇了某些有意義的事件,而且把它們從特定的,關係不大的環境中抽象出來,使它們成為理想化的時候為止。只有那時它們才會展現出光彩奪目的真實結構。

上面這一段是GEB當中引用的文獻,文獻名叫《量子是實在的嗎?》。這段內容可以讓人聯想到兩個領域:混沌理論和概率論,當然這裡的衍生就先到此為止,否則就變成“無窮回溯”了,那就沒完了。

從哲學中退出來,我們仍然考慮表面上的隨機序列中深藏的規律性。第五章中的函數Q(n)是否也具有一個簡單的非遞歸解釋?是不是每個問題都像《一首無的奉獻》中提到的那片果樹林一樣,從某個特定的角度看進去,其中的祕密就一覽無餘了?還是說在數論中存在著一些不論從哪個角度看都是神祕的問題?

有了這段開場白,我覺得現在應該繼續前進,去定義所謂‘長度可預測的搜索’的精確意義了。這將用BlooP語言來完成。

3·BlooP搜索語言——有限搜索

BlooP語言的基本步驟:我們的議題是搜尋具有各種性質的自然數。為了討論任意搜索的‘長度’,我們必須定義一些基本‘步驟’,任何搜索都由它們組成。這樣,搜索長度就可以根據其中的步驟數來度量。被我們當作基本面步驟的有:兩個自然數相加;兩個自然數相乘;確定兩個數是否相等;確定兩個數的相對大小。”這裡要提醒一下,和前面給出過的形式系統一樣,這裡是用“字符串”來表示各種自然數的,所以會有長度“增減”。這個轉換概念必須一直記得,否則後面說的內容就會看不懂。(比較典型的例子就是前面TNT系統表示一個“20”,用了一長串“字符”)

搜索語言:可以理解為構建了一個“測試”,它會對輸入的特定信息進行判斷,最後給出結果,或者不給出結果。

如果我們想用這些步驟嚴格地構造一個測試,例如測試一個數是否是素數,我們很快就會發現必須在其中包含一個‘控制結構’——即對操作次序的描述:和是需要回過頭來重新嘗試某些東西,何時跳過一些步驟,何時停止,以及諸如此類的事情。”(參照之前提過的“遞歸遷移網”:調用、存儲這些都是程序運行過程中發生的事)

在典型的情況下,任何‘算法’——即對任務完成過程的明確描述——都由下列成分組成:(1)需完成的特定運算,(2)控制語句。因此,當我們為表示長度可預測的計算開發我們的語言時,我們必須同時包括基本控制結構。

在BlooP中,基本上唯一的控制結構就是‘有界循環’(即‘bounded loop’,這也正是‘BlooP’的來歷)

那麼BlooP搜索語言的特點就在於它的控制結構——“控制結構集”是有限的,嚴格遵循步驟順序不能夠任意轉移或者無限制的循環某個步驟:重複執行一組指令,但重複次數不得超過一個確定的最大值,一旦超過就停止運行。這個最大值被叫做“上界”或“頂”。

在一個程序中,並不要求程序員準確地給出所有上界的數值——事實上它們是無法預知的。但是,每個上界都可以在進入該循環之前通過計算來確定。

值得一提的是在BlooP搜索當中,也是用到了“組塊化”的概念。注意前面提到,程序可以執行有限次的循環,然後前一個循環的結果是下一個循環的開始,而組塊化就是把前面“幾次的循環”獲得的結果看成“一次循環”得到的結果——你也可以給程序不同的“初始值”。直白來說就是:程序操作的每一個步驟只能做一次簡單處理,但是通過“循環操作”和“組塊化”,我們是能得到“複雜的”結果的。

……一旦一個過程已經被‘定義’了,它就可以在後面的過程定義中被‘調用’。其效果是一旦某個操作在一個過程中被定義了,它就會被認為和基本步驟一樣簡單。這樣,BlooP就具有了自動組塊的特點。你可以把這和一個溜冰好手學習新花樣的過程相比:他不是把新動作看作長長的基本肌肉活動序列,而是看作以前學過的一些動作的組合,而那些動作自身又是用更早所學的動作所組成,如此等等——這種嵌套或組塊可以上溯許多層次,直至遇到基本肌肉活動為止。這樣,BlooP程序的能力就和溜冰者的技能一樣,可以突飛猛進地增長了。

在這樣的“搜索”語言中,是存在很多限制的。一些一開始的初始設定是不能更改的。比如書裡BlooP語句如果進行數學運算的操作的話,它只能做加法——後一個結果是前面結果的不斷疊加一直達到想要的結果為止。那麼問題來了,如果我們需要減法怎麼辦?把整個算法推導重來?並不是,記不記得pq形式系統那個關於篩選“素數”的例子。直白來說,減法是加法的反向操作。

假設我們需要“M-N”這個減法運算在這裡進行,那麼很簡單,BlooP當中的循環操作會把N一直進進行加法運算,直到得出一個與N的和等於M的數為止。那麼如果M小於N怎麼辦?由於BlooP的搜索結果僅限於自然數域(自然數一般是指正整數,所以是沒有負數的。),那麼可以設置一旦這樣的情況出現,BlooP獲得的結果就是0那麼操作循環終止,我們得到結果。

我們通過BlooP程序所能做的事情可以看出來,它實際上可以做兩件事,既可以是“搜索”(或者可以叫“函數”)也可以做“測試”。也就是說BlooP除了可以給出我們想要的“自然數”之外,也可以只給出“YES”或“NO”。因為我們知道BlooP只能進行有限次的操作,所以它的終止只有兩個結果:獲得我們想要的結果“搜索”結束。或者一直沒有得到想要的結果,到達“上界”則“搜索”結束。前者可以把輸出結果替換成“YES”,後者則是輸出“NO”。(書中給出了具體算法的例子)

簡而言之BlooP程序的運算過程可以看作是一條“過程定義鏈”(其中每個過程僅僅調用前面定義的過程),這樣我們再回過頭來看,就明白為什麼把BlooP來計算的函數叫做“原始遞歸函數”了(“遞歸”的概念在第五篇筆記已經做了非常詳細的解釋了)。

可以用BlooP測試來驗證的性質的標準名稱是’原始遞歸謂詞‘。這樣,函數2^3^n就是個原始遞歸函數,而命題’n是個素數‘則是個原始遞歸謂詞。

憑直覺就能看出哥德巴赫性質是原始遞歸的。

(警告:哥德巴赫性質是原始遞歸的,但這一事實並沒有使’是否所有的數都具有哥德巴赫性質?‘成為一個簡單的問題——遠非如此!)

到這裡我們可以直接搬出“原始遞歸函數”的定義了:在可計算性理論中,原始遞歸函數對計算的完全的形式化而言是形成重要構造板塊的一類函數。它們使用遞歸和複合作為中心運算來定義,並且是遞歸函數的嚴格的子集,它們完全是可計算函數。通過補充允許偏函數和介入無界查找運算可以定義出遞歸函數的更廣泛的類。

通常在數論中研究的很多函數,近似於實數值函數,比如加法、除法、階乘、指數,找到第 n 個素數等等是原始遞歸的。實際上,很難設計不是原始遞歸的函數,儘管某些函數是已知的(比如阿克曼函數)。所以,通過研究它們,我們能發現有廣泛影響的結論的那些性質。

原始遞歸函數可以用總是停機的圖靈機計算,而遞歸函數需要圖靈完全系統。

原始遞歸函數的集合在計算複雜性理論中叫做PR。

在繼續討論一些關於BlooP及其’親戚‘FlooP的問題之前,讓我們先回顧一下當初引進BlooP的原因,並把它和TNT聯繫起來。我在前面說過,一旦全部原始遞歸的概念對一個形式系統來說都是可體現的,那麼這個系統就達到了使用哥德爾方法所需的’臨界質量‘。

在數論領域當中,用詞真的是一個非常重要的事,這在前面就已經強調過了。自然語言為了交流便利而模糊了一些用法和定義,而數論語言則完全反之:一就是一,二就是二,不存在模糊、大概的解釋。

我們必須區別這樣兩個概念:可表示性和可體現性。’表示‘一個謂詞只不過是一個從自然語言到嚴格的形式化表述的翻譯問題。這和該謂詞是不是定理沒有關係。而要’體現‘一個謂詞,這顆就是個強得多的概念了。這意味著:

(1)該謂詞的全部為真的例均為定理;

(2)全部為假的例均為非定理。

’例‘在這裡是指用數值取代謂詞中所有自由變量後所得到的串。

……TNT的優點是能夠表示數論中的任何謂詞。例如,很容易寫一個TNT串來表示謂詞’b具有烏龜性質‘。因此,根據表示能力來看,TNT滿足我們的全部要求。

但是,問’在TNT中哪些性質是可體現的?‘,這恰恰就是在問’TNT作為一個公理系統有多強?‘。是不是所有可能的性質在TNT中都是可體現的?若是如此,那麼TNT就能回答數論中的任何問題,它就是完全的。”但實際上我們很清楚“完全的”是不可能的事,不過TNT系統依然可以涵蓋整個“原始遞歸謂詞”。

如果能為自然數的某個性質寫出一個BlooP測試,那麼這個性質在TNT中是可體現的。”那麼這個問題反過來問,是否數的每一種性質都能被某個適當的BlooP程序所檢查?“這個問題實質上是’是否總能給出運算長度的上界——還是說在自然數系統中存在一種內在的混亂,致使有時無法事先預測運算的長度?‘令人震驚的是,恰好是後一種情況出現了,其原因我們不久就會看到……在我們的論證中,將使用享有盛名的’對角線法‘,這是由集合論的奠基人康托爾發現的。

現在知道為什麼要在對話裡反覆暗示康托爾的存在了,而且這裡的論證某種程度上來說,就是康托爾“對角線法”的一個“變奏版本”。這裡直接就給出結論了,根據“對角線法”得出的結論,恐怕確實存在一些不能在BlooP中編程序的函數,這些函數不是“原始遞歸的”。

值得一提的是,通過這個例子,我們又繞回到了第三次數學危機的內容上面來了。康托爾實際上比羅素更早發現集合論當中存在的悖論,而這個悖論很有可能是通過“對角線方法”發現的:

在數學中,康托爾悖論是集合論的一個定理,即沒有最大的基數,所以“無限大小”的蒐集自身是無限的。進一步的,從這個事實得出這個蒐集不是集合而是真類;在馮·諾伊曼-博內斯-哥德爾集合論中從這個事實得出大小限制公理,即這個真類和所有集合的集合之間存在雙射。所以,不只是有無限多個無限,而是這個無限大於無限的任何枚舉。

這個悖論以德國數學家格奧爾格·康托爾命名,他在1899年(或在1895年到1897年之間)首先提出了它。像多數數學悖論一樣,它實際上不是矛盾,而是在關於無限本質和集合概念的情況下錯誤直覺的體現。換個方式說,它在樸素集合論中的確是悖論,從而證實了這個理論對數學發展的需要是不充足的。在其後的各個公理化集合論中,這個悖論已經被解決。

儘管通常認定康托爾是第一個提出基數集合的這個性質的人,有些數學家認為這個貢獻是伯蘭特·羅素做出的,他在1899年或1901年定義了類似的定理。——維基百科:’康托爾悖論‘詞條”

上述的說法太過於抽象,那麼類似用理髮師悖論來比喻羅素悖論一樣,這裡也換一個簡單通俗點的說法:即“對角線論證”最後得出了完備實數列表之外還有實數。通過這個我們也明白了,哥德爾不完備性定理的工作也是基於了“對角線論證”的方法——前面的內容全串上了(包括《對位藏頭詩》那一篇的全部內容)。

4·FlooP搜索語言————無限搜索

至此,我們已經用以BlooP語言寫的程序為工具,定義了自然數上的原始遞歸函數和原始遞歸謂詞所組成的類。我們也表明了BlooP不能囊括全部可用詞語定義的自然數上的函數。我們甚至還用康托爾的對角線法構造了一個‘非BlooP可編程的’函數,即‘藍對角’[N]。為什麼在BlooP中不能表示‘藍對角’呢?是否能改進一下BlooP,以使得‘藍對角’成為可表示的呢?

BlooP的根本特徵就是其中循環的有界性。如果我們拋掉對循環的這種要求,發明另一種語言,稱其為FlooP(英文Free有‘自由’的意思,我們藉此表明FlooP的循環是自由的),會出現什麼情況呢?FlooP除掉一點之外與BlooP完全相同:在FlooP中我們既可以用無頂的的循環,也可以用有頂的循環(雖然在FlooP中寫循環語句時註明其頂的唯一理由是為了好看)。這些新的循環將被稱為MU-LOOP(μ循環)。這是為了遵守數理邏輯中的約定:在其中‘自由’搜索(無界搜索)通常備註上一個叫‘μ算子’的符號。

這個μ算子(英語:μ operator)也可以被叫做極小化算子(minimization operator)或者無界查找算子(unbounded search operator)在可計算性理論中,被用來查找給定性質下的最小自然數。這個概念還涉及到可計算理論、圖靈度等等概念,有相當多的涉及這個概念的專業術語目前甚至還沒有中文翻譯(μ是第十二個希臘字母,大寫是M,音譯:姆/繆)。暫時只能說這麼多,但是從這裡可以聯繫到另一個前面提到的概念:“遞歸函數”。

在數理邏輯和計算機科學領域中中,遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數概念。從直覺上講遞歸函數是"可計算的"。而且在可計算性理論中已經證明了它確實是圖靈機的可計算函數。遞歸函數與原始遞歸函數相關,而且遞歸函數的歸納定義創建在原始遞歸函數之上。但不是所有遞歸函數都是原始遞歸函數——其中最著名的是阿克曼函數。換言之,如果把遞歸函數看作是一個集合(所有遞歸函數的集合叫做R)的話,則原始遞歸函數相當於R的子集。遞歸函數還存在其他等價的函數類:λ-遞歸函數和馬爾可夫算法可計算的函數。

……我們可以用FlooP為妙極性及烏龜性質這樣的性質寫測試程序——而這樣的測試程序我們用BlooP是無法寫的,因為其中的搜索或許會無窮無盡……在這個測試中要實現下列功能:

(1)如果輸入N是妙極的,則程序結束,給出答案YES

(2)若N是非妙極的,而且導致一個不同於1-4-2-1-4-2-1……的封閉循環,則程序停止,給出答案NO。

(3)若N是非妙極的,而且導致一個‘無窮上升過程’,程序將不會結束。以這種方式,FlooP的不回答就是回答。FlooP的不回答就像用趙州的‘無’來‘廢問’一樣。

在第3中情況下,具有諷刺意味的是:輸出變量OUTPUT的值一直NO但我們又一直無法得到它,因為程序仍在不停的運轉。這個討厭的第三種可能性是我們寫自由循環時所必須付出的代價。在所有包含了MU-LOOP的FlooP程序中,無終止總是一種理論上的可能性。當然,有許多FlooP程序實際上相對於其所有可能的輸入值都是能終止的。

所以FlooP某種程度上來說是BlooP的拓展升級版,我們通過上面的描述看出來,這個搜索語言理論上存在著“有終止”(一般遞歸)和“無終止”(部分遞歸)兩種情況。而實際上無論如何,程序還是需要有一個終止操作,否則的話就會使得程序完全沒有反應——因為沒有終止,所以當你輸入之後,程序就不理你了;它一直在運算但是沒結果。

那有沒有辦法避免這種問題呢?記得BlooP程序的兩個能力嗎?它可以進行判斷。但是問題在於,BlooP程序能輸入語言,怎麼能把FlooP這個“程序”塞進去呢?其實是可以的,用數字對FlooP程序進行編碼就可以了,這個編碼方式我們之前接觸過,就是哥德爾配數——之前在講命題演算和TNT系統的時候提到過。

現在我們的計劃是寫一個名為‘TERMINATOR?’的BlooP測試,其功能是:如果被其輸入數字所編碼的那個FlooP程序是有終止的,則回答YES,否則回答NO。用這個辦法就可以把這個任務交給機器去完成。如果走運,就能把有終止和無終止過程分開了。但是,阿蘭·圖靈給出的一個精巧的論證表明,任何BlooP程序都不能一貫正確地完成這種區分工作。圖靈所用的技巧實際上和哥德爾的技巧基本相同,因此也密切聯繫於康托爾的對角線技巧。

這個證明和前面的情況類似:因為之所以不能一貫的正確區分是因為有無終止的“終止測試器”實際上是不可能存在的。這個證明和上面用對角線方法證明BlooP程序是類似的,而得出的結果也類似——存在一個良定義的單變量可計算函數,但這個可計算函數不在FlooP的搜索目錄之內。值得注意的是,如果這個證明裡沒有使用“終止測試器”的話,則對於FlooP不能使用對角線論證,因為程序會無休止計算,而對角線論證要求對角線上的函數為所有可能的輸入算出輸出值。

之前對於強力TNT系統的證明也存在和這個相類似的情況——系統升級強化,依然不能擺脫不完備性定理。

5·GlooP搜索語言——神話?

這裡直接引用原文了:“如果說FlooP是去掉限制的BlooP,那麼GlooP一定是去掉限制的FlooP。但一個限制怎麼可能去掉兩次呢?你怎麼能構造一個比FlooP更強有力的語言呢?在‘紅對角’中,我們已經發現了一個函數,我們人知道如何去求它的值——求值方法已經明確的用自然語言描述出來了——但似乎不能用FlooP語言編出程序來完成這項工作。這是一個尖銳的二律背反,因為還沒有人曾經發現過比FlooP更強有力的計算機語言。

有人曾經詳盡地研究過計算機語言的能力,我們不必自己再去做這項工作,只需報告這樣一項結果:有一大批計算機語言可以被證明是與FlooP具有完全相同的描述能力的,這就是說:任何一個可以用其中某種語言編程序完成的計算過程,必然能用所有這些語言中的任何一個來編程序完成。奇怪的是,幾乎任何設計計算機語言的合理企圖,都以構造出這個類中的一個成員而告終——也就是說,造出了一種能力等價於FlooP的語言。當然通過某種努力也可以構造出一種比這一類語言要弱一些的合理並有趣的計算機語言。陷入,BlooP就是弱語言的一個例子,但這是一種例外,而不是規律。關鍵在於存在許多很自然的方式可以用來發明算法語言,而不同的人,循著不同的途徑,往往最終創造出等價的語言。它們只有形式上差別,能力是一樣的。

事實上,絕大多數人都相信不會再有描述計算的能力強於FlooP及其等價物的語言了。這個假說在30年代被兩個人互相獨立地表述出來:阿蘭·圖靈——關於他,後面還會進一步介紹——和阿朗佐·丘奇,本世紀傑出的邏輯學家之一。他們的結果被稱為‘丘奇·圖靈論題’。如果我們接受這個論題,我們就必須下結論說‘GlooP’是個神話——在FlooP中已經沒有限制可以取消,無法通過‘解放’來增強它的能力,像我們對BlooP做過的那樣。

這把我們置於一種尷尬的境地,即斷言人可以為N的任意值計算‘紅對角’,但無法編出程序讓計算機來完成這項任務。因為,如果這項任務可以得到完成,那它一定是用FlooP語言來完成的。而根據任務的構造方式,它又不可能用FlooP來完成。這個結論實在太奇特了,致使我們得非常仔細地研究它賴以建立的基礎。而在這當中,你會想起來,就有我們那個不牢靠的假設,即存在一個可以區別有終止和無終止的FlooP程序的判定過程。這個判定過程的想法本來就有點可疑,因為我們已經看到它的存在將導致數論中的所有問題以一種統一的方式被解決。現在我們有了雙重的理由相信任何終止測試都是一種神話——根本就無法把FlooP程序裝到一臺‘甩幹機’裡,把有終止程序和無終止程序分離開來。

懷疑論者可能會堅持說這不像對此類終止測試的不存在性的一個嚴格證明。這種反對意見是合理的。但是,圖靈的方案更為嚴格地論證了這一點:用一個和FlooP同類的語言,不可能寫出計算機程序,來對所有FlooP程序進行終止測試。”(通俗來說:一旦問題陷入自指,那這個問題就沒完了,而自我超越——這更像個神話。)

這條二維龍的自我超越——進入三維

四:關於哥德爾配數以及邱奇-圖靈論題

1·哥德爾配數

在形式數論中,哥德爾配數是對某些形式語言的每個符號和公式對應一個叫做哥德爾數(GN)的唯一的自然數的函數。這個概念是哥德爾為證明他的哥德爾不完備性定理而引入的。可計算函數集合的配數有時叫做哥德爾配數或有效配數。哥德爾配數可以被解釋為一個編程語言,帶有指派哥德爾數到每個可計算函數作為在這種編程語言中計算這個函數的值的程序。哥德爾使用基於素數因數分解的哥德爾配數系統。他首先把唯一的自然數對應到在他所處理的算術的形式語言中的每個基本符號。

為了讓配數成為符號序列的整個公式,哥德爾使用瞭如下系統。給出正整數的序列:x1、 x2、x3 . . . xn ,哥德爾對這個序列的編碼是第n個素數自乘這個序列中對應值的次數:

 e n c ( x 1 x 2 x 3 . . . x n ) = 2^ x 1 ⋅ 3^ x 2 ⋅ 5^ x 3 ⋅ . . . ⋅ p n ^x n

依據算術基本定理(又稱為正整數的唯一分解定理,即:每個大於1的自然數,要麼本身就是質數,要麼可以寫為2個或以上的質數的積,而且這些質因子按大小排列之後,寫法僅有一種方式。),用這種方式獲得的任何數都可以唯一的因數分解到素因子,所以可以有效的從其哥德爾數恢復到最初的序列。

哥德爾特別的在兩個部分使用這個方案: 首先配數表示公式的序列,其次配數表示證明的序列。這允許他證明在關於自然數的命題和關於自然數的定理的可證明性的命題之間的對應。

哥德爾配數問題在於,它不是唯一的。一般性的想法是把公式映射到自然數上。假設有K個基本符號。可替代的哥德爾配數可以通過把每個基本符號映射到基數為K的記數系統的一個數字來構造,這樣由 n 個符號的字母串構成的公式 :

s 1 s 2 s 3 … s n

將被映射成哥德爾數:

h ( s 1 ) × K ( n − 1 ) + h ( s 2 ) × K ( n − 2 ) + ⋯ + h ( s n − 1 ) × K 1 + h ( s n ) × K 0

換句話說,藉由將K個基本符號以某種固定順序擺放,那麼每個方程就會產生唯一對應的哥德爾數。但是如果將K個基本符號以另一種固定順序擺放,則會產生另一種哥德爾編號。也就是說還能有其它的方式來構造序列的哥德爾數。哥德爾配數是參照命題演算和形式算術的符號而構造的.每個符號都被指派了一個自然數。實際上在之前講述TNT系統的時候,已經給出過具體配數的例子了。

圖靈:著名的圖靈測試提出者

2·邱奇-圖靈論題

讓我們簡略地回顧一下丘奇-圖靈論題。我們將在第十七章中相當詳細的討論它——以及它的變種,而現在只需要敘述它的幾種形式,把關於其價值和意義的討論推遲到後面去完成。這裡是三種相互聯繫的敘述此論題的方式:

(1)人所能計算的也就是機器所能計算的。

(2)機器所能計算的也就是FlooP所能計算的。

(3)人所能計算的也就是FlooP所能計算的(即一般遞歸或部分遞歸)。

邱奇-圖靈論題(Church–Turing thesis,又稱邱奇-圖靈猜想,邱奇論題,邱奇猜想,圖靈論題)是一個關於可計算性理論的假設。該假設論述了關於函數特性的,可有效計算的函數值(用更現代的表述來說--在算法上可計算的)。簡單來說,邱奇-圖靈論題認為“任何在算法上可計算的問題同樣可由圖靈機計算”。

20世紀上半葉,有很多人嘗試對可計算性進行公式化表示:美國數學家阿隆佐·邱奇創建了稱為λ演算的方法來定義函數。英國數學家阿蘭·圖靈創建了可對輸入進行運算的理論機器模型,現在被稱為通用圖靈機。邱奇以及數學家斯蒂芬·科爾·克萊尼和邏輯學家J·巴克勒·羅斯一起定義了一類函數,這種函數的值可使用遞歸方法計算。

這三個理論在直覺上似乎是等價的-——它們都定義了同一類函數。這導致數學家和計算機科學家相信可計算性的概念可由上述三種等價的計算過程描述。簡單來講,邱奇-圖靈論題認為如果某種方法(算法)可進行運算,那麼該運算也可被圖靈機執行(也可被遞歸定義的函數或λ函數執行)。

由於邱奇-圖靈論題是對計算特性進行描述的一種陳述,故而不能被嚴格證明。雖然上面提到的三種計算過程可被證明為等價的,但是邱奇-圖靈論題最根本的前提--聲稱一個函數是“可有效計算的”究竟意味著什麼--在某種意義上是不甚明確的直覺結果。所以,該論題依然是一個假想。

在20世紀初期,數學家們經常使用一種非正式的說法即可有效計算,所以為這個概念尋找一個好的形式描述也是十分重要的。當代的數學家們則使用“圖靈可計算”(或簡寫為可計算)這一定義良好的概念。由於這個沒有定義的用語在使用中已經淡去,所以如何定義它的問題已經不是那麼重要了。

之後用於描述有效計算的許多其他機制也被提了出來,比如寄存器機、埃米爾·波斯特(Emill Post)的波斯特系統,組合子邏輯以及馬爾可夫算法(Markov 1960)等。所有這些體系都已被證明在計算上和圖靈機擁有基本相同的能力;類似的系統被稱為圖靈完全。因為所有這些不同的試圖描述算法的努力都導致了等價的結果,所以現在普遍認為邱奇-圖靈論題是正確的。

但是實際上該論題不具有數學定理一般的地位,也無法被證明;說是定理不如說是個將可計算性等同於圖靈機的提議。如果能有一個方法能被普遍接受為一個有效的算法但卻無法在圖靈機上允許,則該論題也是可以被駁斥的。

看這本書的感覺

五:後記

之前說是月更但是這麼晚才完成,這裡道個歉。筆者幾乎是忍著頭暈寫完了這一篇筆記,因為本身數學水平很低(高中數學都沒上完……)。看數學邏輯是真的非常累的一件事的,難就難在對於數學語言的理解上。開篇就提到過,數學語言的使用不同於自然語言。即使用詞一模一樣,但是在意思上就不是一回事了。就如同前面反覆提醒的:“抽象概念與現實本身不可混淆。

這就是為什麼在哥德巴赫猜想部分說過的,沒有經過專業訓練的也與數學或邏輯學愛好者,是沒有辦法解答這種高深的數論問題的原因。他們提出的理論被駁斥的主要部分,往往就是他們混淆了“數學專用名詞”和“普通名詞”的意思。這確實是一件不容易的事情,因為我們的自然語言靠著降低表達精準性而提高了交流效率——很多時候話只需要說一半,甚至“指鹿為馬”我們都能聽明白;所以詞不達意沒關係,一切盡在不言中。但是在數學邏輯領域,這樣的情況是不允許的:一是一二是二,涇渭分明。

計算機科學領域為什麼要探討那麼深奧的數學論題?很簡單,在學術領域之間存在著名為“同構”的通道,數學理論上可獲得方法進行計算的,那麼我們就能同構到現實中實現它——計算機中所有的可操作(不論是系統運行還是圖形界面),全都首先來自於數學中的計算方法實現(函數計算、代數幾何等等)。

這一篇筆記的字數接近最長的那一篇,而且不得不承認,相對來說枯燥很多:這裡還省略了很多書裡給出的構造程序語言的列表和練習題……對於能看到這裡的讀者,表示衷心的感謝,謝謝支持!後面預計還有八篇筆記的內容(之前估計錯誤了,並且之後的筆記長度不敢保證,這幾乎是一本百科全書)。