首頁>科學>

導讀

“忙碌的河狸”這個問題的目的是為了找到執行時間最長的電腦程式。對它的研究與哥德巴赫猜想、黎曼猜想等一系列數學難題建立了驚人而又深刻的聯絡。

撰文 | John Pavlus

翻譯 | 張和持

編輯 | 吳非

程式設計師總想讓程式碼跑的更快。可在1962年,匈牙利數學家蒂博爾·拉多(Tibor Radó)卻提出了截然相反的問題:要怎麼才能讓一個簡單的電腦程式在終止之前跑的儘可能久?拉多將這樣跑得儘可能低效但仍有效的程式稱為“忙碌的河狸”。

自從《科學美國人》於1984年刊載這則問題之後,眾多程式設計師和業餘數學愛好者們份份開始尋找“忙碌的河狸”。不過最近幾年,由於與一些高大上的概念與數學未解的難題建立起聯絡,“忙碌的河狸”已經變成了非常嚴肅的數學問題,

得克薩斯大學的理論計算機科學家斯科特·亞倫森近日發表了一篇關於“忙碌河狸學”的調查,他說:“在數學上,娛樂和真正重要的問題,其邊界非常模糊。”

最近一項研究表明,這些得跑到猴年馬月的程式,或許能澄清一些數學命題,甚至告訴我們哪些內容是可知的。據研究者們稱,忙碌的河狸能幫助我們判斷一個數學問題的難易程度,比如哥德巴赫猜想和黎曼猜想。它能讓人一目瞭然地看到數理邏輯到哪裡就該走不下去了。邏輯學家庫爾特·哥德爾(Kurt Gödel)在大半個世紀之前就證明了,有一些命題既不能證明也不能證偽,也就是所謂的“不可知”。不過現在,忙碌的河狸能為我們指出,這個“不可知”究竟位於什麼地方,就如同一張古老的地圖指引旅者走向世界的邊緣。

無法計算的問題

“忙碌的河狸”這個問題,歸根結底是關於圖靈機——這是阿蘭·圖靈(Alan Turing)於1936年提出的一種理想化模型,其中有一條被分為正方形小塊的長度無限的紙帶,用筆在上面寫或者擦去記號,這些操作需要滿足一套給定的規則,比方說:

規則1. 如果正方形中含有0,則擦掉改成1;然後向右一格,使用規則2;規則2. 如果正方形中含有1,那就不改,然後向左一格使用規則3;

……

每一項規則都像冒險棋一樣。有些規則甚至可以讓你跳回到之前的規則。在這些規則中,最終有一條“停機”的指令。圖靈證明,如果時間充足,規則得當的話,圖靈機就能做任何計算。

圖靈稱,為了真正計算出一個結果,圖靈機最終必須得停機——不能卡死或者陷入迴圈。判別是否能停機的問題稱為停機問題。他在1936年證明了世界上並不存在解決停機問題的萬精油演算法。

而“忙碌河狸”提出了以下問題:給定有限條規則,那麼圖靈機在停機之前最多能走多少步?

比方說,我們只用一條規則,又要保證圖靈機停機,那麼這條規則肯定就必須包含停機指令。我們把停機問題的最長步數稱為忙碌河狸數,那麼BB(1) = 1,因為最多走一步就得停機。

自變數稍有增加,需要考慮的圖靈機數量就會爆炸性增長。如果允許有兩條規則,就有6561種圖靈機,而它們中,只有一隻“忙碌的河狸”,它最長可以走6步。其他大多數圖靈機都不停機,這些不停機的肯定不是“忙碌的河狸”,不過對於一般的情況,要怎麼才能區別出它們?畢竟前面圖靈已經證明,不管圖靈機跑了1000步還是100萬步,都不能咬定圖靈機不會停下來。

這樣就使得尋找忙碌河狸的任務異常艱鉅。規則的條數隨便一改,我們就得從頭開始找最長步數的圖靈機,沒有捷徑。即是說,一般的“忙碌的河狸” 問題是“不可計算的“。

要證明 BB(2) = 6 和 BB(3) = 107 就已經非常複雜了,拉多的學生 Shen Lin 做出了這個成果,並於1965年獲得了博士學位。拉多認為, BB(4) 的問題是“徹底的絕望“,不過還是有人在1983年解決了這個問題。除此之外,研究人員對於5條規則的情況,已經找到了一種圖靈機,它在執行47 176 870步之後停機,也就是說,BB(5) 起碼比這個數字要大。而 BB(6) 最小也得有7.4 × 1036534。亞倫森說:“除非能找到新觀點新思路,否則這個問題根本不可能得到解決。”

不可知的閾值

威廉·加斯塔克(William Gasarch)是馬里蘭大學學院市分校的計算機科學家,他關心的不是如何解決忙碌河狸數問題,相反他對“一般的不可計算問題”非常感興趣。他和其他數學家正以此為基礎,來估計數學上一些未解之謎的困難程度,或是看看這些問題究竟是否是可知的。

比方說哥德巴赫猜想,說的是對於任何大於2的偶數,總能分解為兩個質數的和。要是這個問題能得到解決,那麼數論這一學科將迎來史詩般的一刻,數學家對質數分佈的瞭解也會更加深入。2015年,一位網名為Code Golf Addict的Github使用者釋出了一臺27條規則的圖靈機程式碼。這臺圖靈機非常特別,它當且僅當哥德巴赫猜想不成立時,才會停機。其實很簡單,它一開始工作,就會從4開始,挨著檢查哥德巴赫猜想(當然也是靠遍歷)。如果找到了所需的兩個質數,就往上繼續,以此往復。如果發現了不能表示為質數和的偶數,就會停機。

這種暴力的方法是不可能解決哥德巴赫猜想的,因為如果不停機,我們永遠也不會知道猜想是不是正確的。不過,“忙碌河狸”問題為我們提供了一些思路。假如我們能計算出 BB(27) ,那我們最多也只需執行 BB(27) 這麼多步,再往上如果還沒停機的話,就說明哥德巴赫猜想成立。畢竟 BB(27) 就是27規則停機問題的最大步數了。如果在此之前就停機,自然說明猜想不成立。

困難在於,BB(27) 是如此大的一個數,寫下來都很難,要執行那麼多次去檢驗哥德巴赫猜想,這在我們的宇宙中是遠不可能的。雖然如此,那個巨大的數字仍然是一個具體的數,亞倫森稱,這代表著我們對於數論領域“現有知識的陳述”。

2016年,亞倫森同尤里·馬季亞謝維奇(Yuri Matiyasevich)、斯特凡·奧里爾(Stefan O’Rear)一同做了一項類似的工作。他們設計了一臺744條規則的圖靈機,當且僅當黎曼猜想不成立時停機。黎曼猜想同樣與質數的分佈有關,是七大千禧問題之一,獎金高達一百萬美元。亞倫森的這臺圖靈機只要執行 BB(744) 步,就能解決黎曼猜想。當然這裡也是同樣暴力的演算法,挨著遍歷直到反例出現。

BB(744) 比 BB(24) 又大了很多很多。不過亞倫森說道,要是深入研究一些簡單的問題,比如 BB(5) ,“就有可能從中發現一些本身就很有趣的數論問題。”例如,數學家帕斯卡爾·米歇爾(Pascal Michel)在1993年證明,目前保持著5規則步數記錄的那個圖靈機,其規則與考拉茲猜想中函式行為極其相似,而後者是數學中又一個著名的未解之謎。

亞倫森說道:“這麼多問題可以歸結為‘圖靈機是否停機?’,那如果我們能知道所有的‘忙碌河狸數’,就能解決所有問題。”

最近,亞倫森又在使用一種基於“忙碌河狸”的方法去測量整個數學系統的“不可知閾值”。哥德爾1931年證明了他那著名的不完備定理:對任意的公理集合,要麼公理不相容(也就是會產生矛盾),要麼不完備(存在不可證明的真命題)。而現代數學賴以生存的ZF集合公理也毫不例外地存在哥德爾界限。而亞倫森想要用“忙碌河狸”去估計它的邊界具體在哪裡。

2016年,他和他的研究生亞當·葉迪迪亞(Adam Yedidia)鼓搗出了一臺7910條規則的圖靈機,當且僅當ZF集合理論不相容時停機。這就是說 BB(7910) 次計算就能得到ZF集合理論的相容性。而這些公理本身在計算 BB(7910) 的時候是用不到的,就像我們算2 + 2 = 4的時候用不到集合公理時一樣。

奧里爾緊接著提出了一個更簡單的748條規則的圖靈機,同樣用來檢測ZF公理。這樣就把不可知的閾值降低了。奧爾良州立大學名譽教授,數理邏輯學家哈維·弗裡德曼(Harvey Friedman)說:“這有些戲劇性,規則數變得沒那麼誇張了。”弗裡德曼認為,這些數字還能進一步降低:“我覺得最終答案應該在50左右。”而亞倫森認為,真正的閾值應該接近BB(20) 。

無論大小,不可知的閾值的確是存在的。亞倫森說道:“自從哥德爾以來,我們的世界就一直是如此(不可知);而‘忙碌河狸’函式得以讓這一切更加清晰明瞭。”

原文連結:https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/

擴充套件閱讀:

陳景潤究竟為證明哥德巴赫猜想做出了哪些貢獻?| 科學大院

接收不到外星文明資訊,是因為數學體系不一樣?| 環球科學

如何科學地寫出今年的高考零分作文?我們手把手教會你|環球科學

用一隻燈泡,百米外就能偷聽對話!以色列科學家提出遠端竊聽新手段 | 環球科學

11
最新評論
  • mRNA疫苗可誘導對SARS-CoV-2及其多種擔憂的變體的持久免疫記憶
  • 薛定諤:人活著就是在對抗熵增定律,生命以負熵為生