科學(xué)視點：用跑得最慢的電腦程序，理解最高深的哥德巴赫猜想

五條規(guī)則的圖靈機(jī)可視化。每列像素代表一步計算，步驟從左到右。黑色代表1。最右邊表示圖靈機(jī)的停機(jī)。（圖片來源：Peter Krumins/Quanta Magazine）
“忙碌的河貍”這個問題的目的是為了找到運行時間最長的電腦程序。對它的研究與哥德巴赫猜想、黎曼猜想等一系列數(shù)學(xué)難題建立了驚人而又深刻的聯(lián)系。
程序員總想讓代碼跑的更快。可在1962年，匈牙利數(shù)學(xué)家蒂博爾·拉多（Tibor Radó）卻提出了截然相反的問題：要怎么才能讓一個簡單的電腦程序在終止之前跑的盡可能久？拉多將這樣跑得盡可能低效但仍有效的程序稱為“忙碌的河貍”。
自從《科學(xué)美國人》于1984年刊載這則問題之后，眾多程序員和業(yè)余數(shù)學(xué)愛好者們份份開始尋找“忙碌的河貍”。不過最近幾年，由于與一些高大上的概念與數(shù)學(xué)未解的難題建立起聯(lián)系，“忙碌的河貍”已經(jīng)變成了非常嚴(yán)肅的數(shù)學(xué)問題，
得克薩斯大學(xué)的理論計算機(jī)科學(xué)家斯科特·亞倫森近日發(fā)表了一篇關(guān)于“忙碌河貍學(xué)”的調(diào)查，他說：“在數(shù)學(xué)上，娛樂和真正重要的問題，其邊界非常模糊?！?br> 最近一項研究表明，這些得跑到猴年馬月的程序，或許能澄清一些數(shù)學(xué)命題，甚至告訴我們哪些內(nèi)容是可知的。據(jù)研究者們稱，忙碌的河貍能幫助我們判斷一個數(shù)學(xué)問題的難易程度，比如哥德巴赫猜想和黎曼猜想。它能讓人一目了然地看到數(shù)理邏輯到哪里就該走不下去了。邏輯學(xué)家?guī)鞝柼亍じ绲聽枺↘urt G?del）在大半個世紀(jì)之前就證明了，有一些命題既不能證明也不能證偽，也就是所謂的“不可知”。不過現(xiàn)在，忙碌的河貍能為我們指出，這個“不可知”究竟位于什么地方，就如同一張古老的地圖指引旅者走向世界的邊緣。
無法計算的問題
“忙碌的河貍”這個問題，歸根結(jié)底是關(guān)于圖靈機(jī)——這是阿蘭·圖靈（Alan Turing）于1936年提出的一種理想化模型，其中有一條被分為正方形小塊的長度無限的紙帶，用筆在上面寫或者擦去記號，這些操作需要滿足一套給定的規(guī)則，比方說：
規(guī)則1. 如果正方形中含有0，則擦掉改成1；然后向右一格，使用規(guī)則2；
規(guī)則2. 如果正方形中含有1，那就不改，然后向左一格使用規(guī)則3；
……
每一項規(guī)則都像冒險棋一樣。有些規(guī)則甚至可以讓你跳回到之前的規(guī)則。在這些規(guī)則中，最終有一條“停機(jī)”的指令。圖靈證明，如果時間充足，規(guī)則得當(dāng)?shù)脑挘瑘D靈機(jī)就能做任何計算。
圖靈稱，為了真正計算出一個結(jié)果，圖靈機(jī)最終必須得停機(jī)——不能卡死或者陷入循環(huán)。判別是否能停機(jī)的問題稱為停機(jī)問題。他在1936年證明了世界上并不存在解決停機(jī)問題的萬精油算法。
而“忙碌河貍”提出了以下問題：給定有限條規(guī)則，那么圖靈機(jī)在停機(jī)之前最多能走多少步？


蒂博爾·拉多（圖片來源：俄亥俄州立大學(xué)檔案）
比方說，我們只用一條規(guī)則，又要保證圖靈機(jī)停機(jī)，那么這條規(guī)則肯定就必須包含停機(jī)指令。我們把停機(jī)問題的最長步數(shù)稱為忙碌河貍數(shù)，那么BB(1) = 1，因為最多走一步就得停機(jī)。
自變量稍有增加，需要考慮的圖靈機(jī)數(shù)量就會爆炸性增長。如果允許有兩條規(guī)則，就有6561種圖靈機(jī)，而它們中，只有一只“忙碌的河貍”，它最長可以走6步。其他大多數(shù)圖靈機(jī)都不停機(jī)，這些不停機(jī)的肯定不是“忙碌的河貍”，不過對于一般的情況，要怎么才能區(qū)別出它們？畢竟前面圖靈已經(jīng)證明，不管圖靈機(jī)跑了1000步還是100萬步，都不能咬定圖靈機(jī)不會停下來。
這樣就使得尋找忙碌河貍的任務(wù)異常艱巨。規(guī)則的條數(shù)隨便一改，我們就得從頭開始找最長步數(shù)的圖靈機(jī)，沒有捷徑。即是說，一般的“忙碌的河貍” 問題是“不可計算的“。
要證明 BB(2) = 6 和 BB(3) = 107 就已經(jīng)非常復(fù)雜了，拉多的學(xué)生 Shen Lin 做出了這個成果，并于1965年獲得了博士學(xué)位。拉多認(rèn)為， BB(4) 的問題是“徹底的絕望“，不過還是有人在1983年解決了這個問題。除此之外，研究人員對于5條規(guī)則的情況，已經(jīng)找到了一種圖靈機(jī)，它在運行47 176 870步之后停機(jī)，也就是說，BB(5) 起碼比這個數(shù)字要大。而 BB(6) 最小也得有7.4 × 1036534。亞倫森說：“除非能找到新觀點新思路，否則這個問題根本不可能得到解決。”
不可知的閾值
威廉·加斯塔克（William Gasarch）是馬里蘭大學(xué)學(xué)院市分校的計算機(jī)科學(xué)家，他關(guān)心的不是如何解決忙碌河貍數(shù)問題，相反他對“一般的不可計算問題”非常感興趣。他和其他數(shù)學(xué)家正以此為基礎(chǔ)，來估計數(shù)學(xué)上一些未解之謎的困難程度，或是看看這些問題究竟是否是可知的。
比方說哥德巴赫猜想，說的是對于任何大于2的偶數(shù)，總能分解為兩個質(zhì)數(shù)的和。要是這個問題能得到解決，那么數(shù)論這一學(xué)科將迎來史詩般的一刻，數(shù)學(xué)家對質(zhì)數(shù)分布的了解也會更加深入。2015年，一位網(wǎng)名為Code Golf Addict的Github用戶發(fā)布了一臺27條規(guī)則的圖靈機(jī)代碼。這臺圖靈機(jī)非常特別，它當(dāng)且僅當(dāng)哥德巴赫猜想不成立時，才會停機(jī)。其實很簡單，它一開始工作，就會從4開始，挨著檢查哥德巴赫猜想（當(dāng)然也是靠遍歷）。如果找到了所需的兩個質(zhì)數(shù)，就往上繼續(xù)，以此往復(fù)。如果發(fā)現(xiàn)了不能表示為質(zhì)數(shù)和的偶數(shù)，就會停機(jī)。
這種暴力的方法是不可能解決哥德巴赫猜想的，因為如果不停機(jī)，我們永遠(yuǎn)也不會知道猜想是不是正確的。不過，“忙碌河貍”問題為我們提供了一些思路。假如我們能計算出 BB(27) ，那我們最多也只需運行 BB(27) 這么多步，再往上如果還沒停機(jī)的話，就說明哥德巴赫猜想成立。畢竟 BB(27) 就是27規(guī)則停機(jī)問題的最大步數(shù)了。如果在此之前就停機(jī)，自然說明猜想不成立。
困難在于，BB(27) 是如此大的一個數(shù)，寫下來都很難，要運行那么多次去檢驗哥德巴赫猜想，這在我們的宇宙中是遠(yuǎn)不可能的。雖然如此，那個巨大的數(shù)字仍然是一個具體的數(shù)，亞倫森稱，這代表著我們對于數(shù)論領(lǐng)域“現(xiàn)有知識的陳述”。


圖片來源：Pixabay
2016年，亞倫森同尤里·馬季亞謝維奇（Yuri Matiyasevich）、斯特凡·奧里爾（Stefan O’Rear）一同做了一項類似的工作。他們設(shè)計了一臺744條規(guī)則的圖靈機(jī)，當(dāng)且僅當(dāng)黎曼猜想不成立時停機(jī)。黎曼猜想同樣與質(zhì)數(shù)的分布有關(guān)，是七大千禧問題之一，獎金高達(dá)一百萬美元。亞倫森的這臺圖靈機(jī)只要運行 BB(744) 步，就能解決黎曼猜想。當(dāng)然這里也是同樣暴力的算法，挨著遍歷直到反例出現(xiàn)。
BB(744) 比 BB(24) 又大了很多很多。不過亞倫森說道，要是深入研究一些簡單的問題，比如 BB(5) ，“就有可能從中發(fā)現(xiàn)一些本身就很有趣的數(shù)論問題?！崩纾瑪?shù)學(xué)家帕斯卡爾·米歇爾（Pascal Michel）在1993年證明，目前保持著5規(guī)則步數(shù)記錄的那個圖靈機(jī)，其規(guī)則與考拉茲猜想中函數(shù)行為極其相似，而后者是數(shù)學(xué)中又一個著名的未解之謎。
亞倫森說道：“這么多問題可以歸結(jié)為‘圖靈機(jī)是否停機(jī)？’，那如果我們能知道所有的‘忙碌河貍數(shù)’，就能解決所有問題?！?br> 最近，亞倫森又在使用一種基于“忙碌河貍”的方法去測量整個數(shù)學(xué)系統(tǒng)的“不可知閾值”。哥德爾1931年證明了他那著名的不完備定理：對任意的公理集合，要么公理不相容（也就是會產(chǎn)生矛盾），要么不完備（存在不可證明的真命題）。而現(xiàn)代數(shù)學(xué)賴以生存的ZF集合公理也毫不例外地存在哥德爾界限。而亞倫森想要用“忙碌河貍”去估計它的邊界具體在哪里。
2016年，他和他的研究生亞當(dāng)·葉迪迪亞（Adam Yedidia）鼓搗出了一臺7910條規(guī)則的圖靈機(jī)，當(dāng)且僅當(dāng)ZF集合理論不相容時停機(jī)。這就是說 BB(7910) 次計算就能得到ZF集合理論的相容性。而這些公理本身在計算 BB(7910) 的時候是用不到的，就像我們算2 + 2 = 4的時候用不到集合公理時一樣。
奧里爾緊接著提出了一個更簡單的748條規(guī)則的圖靈機(jī)，同樣用來檢測ZF公理。這樣就把不可知的閾值降低了。奧爾良州立大學(xué)名譽(yù)教授，數(shù)理邏輯學(xué)家哈維·弗里德曼（Harvey Friedman）說：“這有些戲劇性，規(guī)則數(shù)變得沒那么夸張了?！备ダ锏侣J(rèn)為，這些數(shù)字還能進(jìn)一步降低：“我覺得最終答案應(yīng)該在50左右。”而亞倫森認(rèn)為，真正的閾值應(yīng)該接近BB(20) 。
無論大小，不可知的閾值的確是存在的。亞倫森說道：“自從哥德爾以來，我們的世界就一直是如此（不可知）；而‘忙碌河貍’函數(shù)得以讓這一切更加清晰明了。”
撰文：John Pavlus
翻譯：張和持
編輯：吳非
引進(jìn)來源：quantamagazine
引進(jìn)鏈接：https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/


關(guān)注【深圳科普】微信公眾號，在對話框：
回復(fù)【最新活動】，了解近期科普活動
回復(fù)【科普行】，了解最新深圳科普行活動
回復(fù)【研學(xué)營】，了解最新科普研學(xué)營
回復(fù)【科普課堂】，了解最新科普課堂
回復(fù)【科普書籍】，了解最新科普書籍
回復(fù)【團(tuán)體定制】，了解最新團(tuán)體定制活動
回復(fù)【科普基地】，了解深圳科普基地詳情
回復(fù)【觀鳥知識】，學(xué)習(xí)觀鳥相關(guān)科普知識
回復(fù)【博物學(xué)院】，了解更多博物學(xué)院活動詳情
?