002(1 / 2)

圖靈機並不是特指某一個或某一類機器,而是一種用數學的語言所定義出來的概念,是為了解答20世紀數學家對數學的終極追問而發明的一種工具。它的目的是為了對人類頭腦內複雜數學活動的抽象和簡化。

定義圖靈機需要七個集合。其中最重要的兩個分彆是“有限的非空狀態ae的集合”與“有限的非空符號ybl的集合”。前者代表著“這台機器能夠在紙帶上讀取和寫入的符號種類”,也被稱作“色數”。後者則代表“這機器內部可以出現的狀態”,被稱作“狀態數”可以簡單的理解為“機器可以開一檔二檔”。

餘下五個則包括了“空白符號”、“初始的輸入符號”、“初始狀態”、“轉移函數集合”,以及特殊的“停機狀態”,即“機器進入該狀態之後就必須停機”。

隻要具備這七個要素,那麼一台機器就可以是圖靈機。

實際上,偉大的數學家阿蘭圖靈在創造這個概念的時候,並沒有設計出可以實際運行的機器。多年之後,馮諾依曼才製造了一種基於電力的圖靈機工程實現。

舉個例子,算盤被一根橫梁分作上下兩邊。上珠兩顆,通過靠梁與否,可以用來表現02三種符號。下珠五顆,通過靠梁與否,可以用來表現05六種狀態。算盤可以視作一種具有三色、六狀態的機器。

這個時候,若是有數學家在紙上寫下了三色六狀態所對應的所有轉移函數,並訓練一個人或猴子嚴格按照轉移函數集合撥動算盤,那麼這個算盤再加使用者,就可以視作“一個圖靈機”了。

約格莫夫依稀記得,很多年前,他好像與向山做過類似的研究。將視作圖靈機的“紙帶”,的四種堿基對視作“符號的集合”,而將氨基酸視作“狀態”,核糖體與則具備了“轉移函數集合”……

地球真核生物的細胞核,或許是四色狀態的圖靈機。

而在眾多的圖靈機之中,有一種被稱作“海狸機”的玩意最為離譜。

n,意為“usyeaer”,忙碌的海狸。是一個在給定參數後,尋找可能產生的最大輸出的可終止程序。最簡單的二色二狀態海狸機,隻有“開和關”兩種狀態,並且隻能輸出“0或1”,且會在輸出1的時候停止。二色二狀態海狸機可以通過6次狀態轉換輸出4個1,因此26。

321。

4107。

然後,目前人類尚未枚舉完所有5狀態的海狸圖靈機,隻知道5要麼就是47,176,870,要麼就是大於10的十一次方。

6已經確定大於7410^36537。

而在2016年,一名數學家將哥德巴赫猜想編碼為有4888個狀態的海狸機。編碼邏輯很簡單,就是從小到大驗證每一個偶數。如果發現某個偶數可以表示成兩個質數之和,則考察下一個偶數。隻要這台圖靈機跑完了4888步,且在跑完之前沒有停機,那人類就可以斷定它永遠不會停機,所以哥德巴赫猜想為真。

但問題在於,宇宙隻有不到10^80個原子。這個數量甚至遠小於6,更遑論4888。

約格莫夫驚歎於這個念頭的離譜程的離譜程度。整個宇宙的物質與能量,都支撐不了這種程度的計算。想要記錄下這個數字的具體數值,就得在宇宙的每一個原子上記錄下比宇宙原子數過多的數位。這是一個不可計算的數值。

“可即便如此,這仍舊是在有窮的步驟裡完成了對無窮的追索。”向山卻是這麼介紹的,“如果我們用更加平庸的方式去窮舉所有的偶數,那我們需要的物質與能量才是無窮的。有理數是個無窮的概念。這種辦法最多隻能保證在哥德巴赫猜想為假的時候使用即在無窮之中,找到了一個哥德巴赫猜想的反例。但是4888,雖然它比宇宙更大,卻是一個有窮的數字。海狸機是在有限時間內通過有限步驟,完成了對無限的探索。”