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

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


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


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


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