文章插圖
- 目前已知運行時間最長的五規(guī)則圖靈機的可視化 。每一列像素代表計算中的一步，從左向右移動 。黑色方塊表示機器打印了1的位置 。最右邊的一列顯示了當圖靈機停止時的計算狀態(tài) 。
自從1984年在《科學美國人》的“計算機娛樂”專欄中流行以來，對于程序員和其他數(shù)學愛好者來說，尋找這些程序一直是一個極其有趣的謎題 。但在過去的幾年里，忙碌的海貍游戲已經(jīng)成為一個研究的對象，因為它與數(shù)學中一些最崇高的概念和開放問題產(chǎn)生了聯(lián)系 。
最近的工作表明，搜索長時間運行的計算機程序可以闡明數(shù)學知識的狀態(tài)，甚至告訴我們什么是可知的 。根據(jù)研究人員的說法，“忙碌的海貍”游戲為評估某些問題的難度提供了一個具體的基準，例如尚未解決的哥德巴赫猜想和黎曼假設 。它甚至讓我們看到，數(shù)學背后的邏輯基石在哪里崩潰了 。近一個世紀前，邏輯學家?guī)鞝柼亍じ绲聽柧妥C明了這種數(shù)學未知領域的存在 。但忙碌的海貍游戲可以顯示它實際上在數(shù)軸上的位置，就像一幅描繪世界邊緣的古老地圖 。
無法計算的電腦游戲“忙碌的海貍”是關于圖靈機的行為的，它是由艾倫·圖靈在1936年構(gòu)想出來的原始的、理想化的計算機 。圖靈機在被分割成無數(shù)個正方形的帶上執(zhí)行操作 。它是根據(jù)一系列規(guī)則來運行的 。第一條規(guī)則是：
如果正方形包含0，則將其替換為1，向右移動一個正方形并參照規(guī)則2 。如果正方形包含1，離開1，向左移動一個正方形并參考規(guī)則3 。每個規(guī)則都有這種分叉的“選擇自己的冒險”風格 。有些規(guī)則說要回到以前的規(guī)則，最終會有一條包含“停止”指令的規(guī)則 。圖靈證明，只要有正確的指令和足夠的時間，這種簡單的計算機就能進行任何可能的計算 。
正如圖靈在1936年指出的，為了計算一些東西，圖靈機最終必須停止——它不能陷入無限循環(huán) 。但他也證明了，沒有可靠的、可重復的方法來區(qū)分機器停機和機器簡單地無限循環(huán)運行，這個事實被稱為停機問題 。
“忙碌的海貍”游戲的問題是：給定一定數(shù)量的規(guī)則，在圖靈機停止運行之前，它能執(zhí)行的最大步驟是多少？
- 在這張未注明日期的照片中，提博爾·拉多發(fā)明了忙碌的海貍游戲，將理論上的不可計算性具體化 。
但只要再增加幾條規(guī)則，需要考慮的機器數(shù)量馬上就會激增 。有兩個規(guī)則的6561個可能的機器中，在停止運行之前的最大步驟是6步，也有些干脆無限循環(huán)了 。這些都不是忙碌的海貍，但你如何確定地排除它們呢？圖靈證明了，沒有辦法自動判斷運行1000步或100萬步的機器最終會不會終止 。
這就是為什么發(fā)現(xiàn)忙碌的海貍?cè)绱死щy的原因 。沒有通用的方法來識別使用任意數(shù)量的指令運行時間最長的圖靈機，你必須自己弄清楚每一種情況的具體情況 。換句話說，“忙碌的海貍”游戲一般來說是“不可計算的” 。
證明BB(2) = 6和BB(3) = 107是非常困難的，因此拉多的學生沈林在1965年獲得了該研究的博士學位 。拉多認為BB(4)完全沒有希望了，但這最終在1983年解決了 。除此之外，這些值實際上會暴增 。研究人員已經(jīng)確定了一個具有5條規(guī)則圖靈機，例如，5規(guī)則圖靈機運行47,176,870步才停止，所以BB(5)至少有這么大 。BB(6)至少為7.4×10^36,534 。要證明確切的值，需要新的想法和新的見解 。
閾值馬里蘭大學帕克分校的計算機科學家威廉·加斯克說，他對“忙碌海貍的數(shù)量實際上無法計算這一普遍概念”更感興趣，而不是對確定忙碌海貍的數(shù)量的前景感興趣 。他和其他數(shù)學家主要感興趣的是，將博弈作為衡量重要數(shù)學開放問題難度的標尺，或者用來弄清什么在數(shù)學上是可知的 。
例如，哥德巴赫猜想詢問是否每個大于2的偶數(shù)都是兩個素數(shù)的和 。在數(shù)論中，證明猜想的真假將是一個劃時代的事件，使數(shù)學家們能夠更好地理解質(zhì)數(shù)的分布 。2015年，一個名匿名用戶發(fā)布了一個27條規(guī)則的圖靈機代碼，當且僅當哥德巴赫猜想是假的時候，該代碼才會停止運行 。它的工作原理是向上計算所有大于4的偶數(shù)，對于每一個整數(shù)，它都會通過將另外兩個相加的所有可能方法來得到這個整數(shù)，并檢查這兩個整數(shù)對是否為素數(shù) 。當它找到合適的質(zhì)數(shù)對時，它移到下一個偶數(shù)并重復這個過程 。如果它發(fā)現(xiàn)一個不能用質(zhì)數(shù)對求和的偶數(shù)，它就會停止 。
運行這個無需動腦筋的機器并不是解決猜想的實際方法，因為在它停止之前，我們無法知道它是否會停止 。但忙碌的海貍游戲為這個問題提供了一些線索 。如果計算BB(27)是可能的，這將為我們等待哥德巴赫猜想自動解決的時間提供一個上限 。這是因為BB(27)對應的是這個27條規(guī)則的圖靈機為了停止而必須執(zhí)行的最大步驟數(shù) 。如果我們知道這個數(shù)字，我們就可以運行圖靈機這么多步驟 。如果它停在那一點，我們就知道哥德巴赫猜想是假的 。但如果它永遠不會停下來，那么就證明了猜想的正確性 。
問題是BB(27)是一個難以理解的巨大數(shù)字，更不用說去運行那么多步驟，在我們的物理宇宙中也根本不可能 。然而，這個不可理解的巨大數(shù)字仍然是一個精確的數(shù)字 。
2016年，三位數(shù)學家發(fā)現(xiàn)了一臺744條規(guī)則圖靈機，當且僅當黎曼假設為假時，它才會停止工作 。黎曼假設也涉及質(zhì)數(shù)的分布，是克萊數(shù)學研究所價值100萬美元的“千年難題”之一 。
當然，BB(744)是一個比BB(27)更大的數(shù)字 。但是，努力確定一些更簡單的東西，比如BB(5)，實際上可能會出現(xiàn)一些新的數(shù)字理論問題，這些問題本身就很有趣 。例如，數(shù)學家帕斯卡?米歇爾在1993年證明，保持紀錄的5規(guī)則圖靈機表現(xiàn)出類似于科拉茨猜想中描述的函數(shù)的行為 。科拉茨猜想是數(shù)論中另一個著名的開放問題 。
1931年哥德爾著名的不完全性定理證明，任何一組基本公理，只要能作為數(shù)學的邏輯基礎，都注定會有兩種命運，【即要么公理將不一致，導致矛盾（比如證明0 = 1），或者他們會不完整，無法證明一些真實陳述數(shù)據(jù)（如2 + 2 = 4）】，支撐幾乎所有的現(xiàn)代數(shù)學的公理系統(tǒng) 。被稱為ZF集合理論，有它自己的哥德爾邊界 。
2016年，研究生亞當·耶迪迪亞和他的導師設計了一個7910條規(guī)則的圖靈機，只有在ZF集合理論不一致的情況下，圖靈機才會停止 。這意味著BB(7910)是一個避開了ZF集合理論公理的計算 。這些公理不能用來證明BB(7910)代表的是一個數(shù)而不是另一個數(shù)，就像不能證明2 + 2 = 4而不是5一樣 。
隨后，瑞婭爾設計了一個更簡單的748規(guī)則機器，如果ZF不一致，它就會停止——實質(zhì)上是將不可知閾值從BB(7,910)移近到BB(748) 。俄亥俄州立大學的數(shù)學邏輯學家、名譽教授哈維?弗里德曼表示：“數(shù)量并非完全荒謬，這是一件引人注目的事情 ?！备ダ锏侣J為，這個數(shù)字還可以進一步降低 。無論遠近，這種不可知的閾值確實存在 。
【哥德巴赫猜想解決了嗎？揭示數(shù)學的基本極限】
以上關于本文的內(nèi)容，僅作參考！溫馨提示：如遇健康、疾病相關的問題，請您及時就醫(yī)或請專業(yè)人士給予相關指導!
「愛刨根生活網(wǎng)」www.malaban59.cn小編還為您精選了以下內(nèi)容，希望對您有所幫助：- 車標志識別圖片大全圖片邁巴赫價格 邁巴赫車的價格和圖片
- 希望每個人都能如愿 婚姻的兩種猜想
- 圖文 夢見牙里有蟲子
- 李米的猜想到底講什么 李米的猜想是真實的故事嗎
- 龐加萊猜想 原來我們?nèi)绱擞行铱吹健褒嫾尤R猜想”的證明