計(jì)算機(jī)程序揭示了數(shù)學(xué)基本極限

宜斌

忙碌的海貍（Busy Beaver）游戲的目標(biāo)是找到運(yùn)行時(shí)間最長的計(jì)算機(jī)程序，它與數(shù)學(xué)有著令人驚訝的聯(lián)系。該游戲是由匈牙利的數(shù)學(xué)家Tibor Radó在1962年發(fā)表的論文《On Non-Computable Functions》中提出的。

在計(jì)算機(jī)科學(xué)中，忙碌的海貍是一個(gè)在給定參數(shù)后，尋找可能產(chǎn)生的最大輸出的可終止程序。忙碌的海貍游戲包括設(shè)計(jì)一個(gè)可終止的，只輸出0或1的圖靈機(jī)，讓其在一條紙帶上盡可能多地輸出1。

然而對(duì)于程序員和其他數(shù)學(xué)愛好者來說，找到這些程序一直是一個(gè)巨大的難題。在過去的幾年中，繁忙的海貍游戲之所以成為一個(gè)研究對(duì)象，是因?yàn)樗c某些高階的概念和數(shù)學(xué)中的開放性問題產(chǎn)生了聯(lián)系。

忙碌的海貍

程序員通常想要以最小化其代碼執(zhí)行所需的時(shí)間。但是在1962年，匈牙利數(shù)學(xué)家TiborRadó提出了相反的問題。他問：一個(gè)簡單的計(jì)算機(jī)程序在終止之前可能會(huì)運(yùn)行多長時(shí)間？Radó將這些效率極低但仍能正常運(yùn)行的程序稱為“忙碌的海貍”。

德克薩斯大學(xué)奧斯汀分校的理論計(jì)算機(jī)科學(xué)家Scott Aaronson說：“在數(shù)學(xué)上，有趣的娛樂與實(shí)際上重要的事物之間存在非常容易結(jié)合之處?！?/p>

最近的數(shù)據(jù)表明，運(yùn)行時(shí)間長的計(jì)算機(jī)程序的搜索可以闡明數(shù)學(xué)知識(shí)的狀態(tài)，甚至可以告訴我們什么是已知的。根據(jù)研究人員的說法，忙碌的海貍游戲?yàn)樵u(píng)估某些問題（例如未解決的哥德巴赫猜想和黎曼假設(shè)）的難度提供了具體的基準(zhǔn)，它甚至可以讓研究者一目了然地了解數(shù)學(xué)背后的邏輯基礎(chǔ)。

什么是圖靈機(jī)？圖靈機(jī)是一個(gè)虛擬的機(jī)器，盡管這個(gè)機(jī)器很簡單，但它可以模擬計(jì)算機(jī)的任何算法，無論這個(gè)算法有多復(fù)雜。

忙碌的海貍游戲全都涉及圖靈機(jī)的行為——圖靈機(jī)是1936年由艾倫·圖靈（Alan Turing）構(gòu)思的原始的理想化計(jì)算機(jī)，圖靈機(jī)對(duì)被分成正方形的環(huán)形膠帶執(zhí)行動(dòng)作，根據(jù)規(guī)則列表進(jìn)行操作。

圖靈機(jī)的簡單示意圖

假設(shè)有一個(gè)無窮的紙帶，紙帶就像一個(gè)存儲(chǔ)器一樣。紙帶上面的每個(gè)格子是空白的，但是可以讀寫數(shù)據(jù)，在這個(gè)例子里，機(jī)器只能寫0或1，或者什么也不寫，這個(gè)機(jī)器就是包含3個(gè)信號(hào)的圖靈機(jī)。

這個(gè)機(jī)器有一個(gè)探頭，這個(gè)頭可以移動(dòng)到每一個(gè)空格上，用這個(gè)頭，機(jī)器可以有3個(gè)基本操作——1.讀空格的數(shù)據(jù);2.編輯數(shù)據(jù)，可以是寫一個(gè)新的數(shù)據(jù)，可以是擦除數(shù)據(jù);3.移動(dòng)紙帶向左或者向右，這樣機(jī)器可以讀或者編輯旁邊的格子。

不可知的閾值

正如圖靈1936年指出的那樣，為了進(jìn)行計(jì)算，圖靈機(jī)最終必須停止運(yùn)行，它不能陷入無限循環(huán)中。但他還證明，目前沒有可靠的、可重復(fù)的方法來區(qū)分停止運(yùn)行的機(jī)器和永久運(yùn)行的機(jī)器，就是所謂的停止問題。

忙碌的海貍游戲會(huì)問：給定一定數(shù)量的規(guī)則，圖靈機(jī)停止之前可以執(zhí)行的最大步數(shù)是多少？如果只允許一個(gè)規(guī)則，并且要確保圖靈機(jī)停止，則必須立即添加停止指令。

目前還沒有通用的方法來確定運(yùn)行時(shí)間最長的圖靈機(jī)，拋開一大堆的數(shù)學(xué)公式計(jì)算，馬里蘭大學(xué)學(xué)院分校的計(jì)算機(jī)科學(xué)家William Gasarch表示，他對(duì)固定忙碌的海貍數(shù)量的前景不感興趣，而對(duì)“實(shí)際上卻無話可說的一般概念”感興趣。他和其他數(shù)學(xué)家主要對(duì)使用游戲作為衡量標(biāo)準(zhǔn)來衡量數(shù)學(xué)中重要的未解決問題的難度，或找出所有數(shù)學(xué)上可以理解的東西感興趣。

還有網(wǎng)友問到量子計(jì)算機(jī)對(duì)運(yùn)行這種忙碌的海貍圖靈機(jī)有加速作用嗎？結(jié)論是沒有。因?yàn)閳D靈機(jī)運(yùn)行過程是順序性的，前面的沒運(yùn)行過，后面的就運(yùn)行不了，所以量子計(jì)算機(jī)的并行運(yùn)算對(duì)它使不上勁。