計(jì)算機(jī)變得越來(lái)越強(qiáng)大，能力越來(lái)越強(qiáng)，但一切都是有限的。 RYZHI/SHUTTERSTOCK

　　授權(quán)人 人工智能 技術(shù)，今天的計(jì)算機(jī)可以與人進(jìn)行令人信服的對(duì)話(謝謝， 查特), 創(chuàng)作歌曲, 繪畫(huà)玩 國(guó)際象棋和圍棋 和 診斷疾病，僅舉幾個(gè)他們技術(shù)實(shí)力的例子。

　　這些成功可以表明計(jì)算沒(méi)有限制。要了解情況是否如此，重要的是要了解是什么使計(jì)算機(jī)強(qiáng)大。

　　計(jì)算機(jī)的能力有兩個(gè)方面：其硬件每秒可以執(zhí)行的操作數(shù)量以及它運(yùn)行的算法的效率。硬件速度受物理定律的限制。 算法 基本上是指令集，由人類編寫(xiě)，并轉(zhuǎn)換為計(jì)算機(jī)硬件可以執(zhí)行的一系列操作。即使計(jì)算機(jī)的速度可以達(dá)到物理極限，由于算法的限制，計(jì)算障礙仍然存在。

　　這些障礙包括計(jì)算機(jī)無(wú)法解決的問(wèn)題，以及理論上可以解決但實(shí)際上甚至超出了當(dāng)今最強(qiáng)大版本的計(jì)算機(jī)的能力的問(wèn)題。數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家試圖通過(guò)在想象的機(jī)器上嘗試來(lái)確定問(wèn)題是否可以解決。

　　虛構(gòu)的計(jì)算機(jī)

　　算法的現(xiàn)代概念，稱為圖靈機(jī)，由英國(guó)數(shù)學(xué)家于1936年提出 艾倫·圖靈.它是一種虛構(gòu)的設(shè)備，模仿用鉛筆在紙上進(jìn)行算術(shù)計(jì)算的方式。圖靈機(jī)是當(dāng)今所有計(jì)算機(jī)都基于的模板。

　　為了適應(yīng)手動(dòng)完成需要更多紙張的計(jì)算，在 圖靈機(jī) 假定為無(wú)限制。這相當(dāng)于一個(gè)想象中的無(wú)限絲帶或正方形的“磁帶”，每個(gè)正方形要么是空白的，要么包含一個(gè)符號(hào)。

　　機(jī)器由一組有限的規(guī)則控制，并從磁帶上的初始符號(hào)序列開(kāi)始。機(jī)器可以執(zhí)行的操作是移動(dòng)到相鄰的正方形，擦除符號(hào)并在空白正方形上寫(xiě)入符號(hào)。機(jī)器通過(guò)執(zhí)行這些操作的序列進(jìn)行計(jì)算。當(dāng)機(jī)器完成或“停止”時(shí)，磁帶上剩余的符號(hào)是輸出或結(jié)果。

　　計(jì)算通常是關(guān)于有是或否答案的決策。以此類推，醫(yī)學(xué)測(cè)試(問(wèn)題類型)檢查患者的標(biāo)本(問(wèn)題的實(shí)例)是否具有某種疾病指標(biāo)(是或否答案)。該實(shí)例以數(shù)字形式在圖靈機(jī)中表示，是符號(hào)的初始序列。

　　如果圖靈機(jī)針對(duì)每個(gè)實(shí)例(無(wú)論是正數(shù)還是負(fù)數(shù))停止，并正確確定實(shí)例產(chǎn)生的答案，則問(wèn)題被認(rèn)為是“可解決的”。

　　不是每個(gè)問(wèn)題都能解決

　　許多問(wèn)題都可以使用圖靈機(jī)解決，因此可以在計(jì)算機(jī)上解決，而其他許多問(wèn)題則不能。例如，多米諾骨牌問(wèn)題，這是美籍華裔數(shù)學(xué)家提出的平鋪問(wèn)題的變體。 王浩 在1961年，是無(wú)法解決的。

　　任務(wù)是使用一組多米諾骨牌覆蓋整個(gè)網(wǎng)格，并按照大多數(shù)多米諾骨牌游戲的規(guī)則，匹配相鄰多米諾骨牌末端的點(diǎn)數(shù)。事實(shí)證明，沒(méi)有算法可以從一組多米諾骨牌開(kāi)始，并確定該集是否會(huì)完全覆蓋網(wǎng)格。

　　保持合理

　　許多可解決的問(wèn)題可以通過(guò)在合理時(shí)間內(nèi)停止的算法來(lái)解決。這些”多項(xiàng)式時(shí)間算法“是有效的算法，這意味著使用計(jì)算機(jī)來(lái)解決它們的實(shí)例是實(shí)用的。

　　數(shù)以千計(jì)的其他可解決的問(wèn)題不知道具有多項(xiàng)式時(shí)間算法，盡管一直在努力尋找這樣的算法。其中包括旅行推銷(xiāo)員問(wèn)題。

　　旅行推銷(xiāo)員問(wèn)題詢問(wèn)一組具有一些點(diǎn)直接連接的點(diǎn)(稱為圖)是否具有從任何點(diǎn)開(kāi)始并恰好穿過(guò)每隔一點(diǎn)一次的路徑，然后返回到原始點(diǎn)。想象一下，一個(gè)推銷(xiāo)員想要找到一條路線，該路線正好經(jīng)過(guò)一個(gè)社區(qū)中的所有家庭一次并返回起點(diǎn)。

　　這些問(wèn)題，稱為 NP完全，由兩位計(jì)算機(jī)科學(xué)家獨(dú)立制定并證明在 1970 年代初存在，美國(guó)加拿大人 斯蒂芬·庫(kù)克 和烏克蘭裔美國(guó)人 列昂尼德·萊文.庫(kù)克的工作排在第一位，他因這項(xiàng)工作獲得了1982年計(jì)算機(jī)科學(xué)界最高的圖靈獎(jiǎng)。

　　準(zhǔn)確了解的代價(jià)

　　NP完全問(wèn)題最著名的算法本質(zhì)上是從所有可能的答案中尋找解決方案。幾百個(gè)點(diǎn)的圖表上的旅行推銷(xiāo)員問(wèn)題需要數(shù)年時(shí)間才能在超級(jí)計(jì)算機(jī)上運(yùn)行。這樣的算法效率低下，這意味著沒(méi)有數(shù)學(xué)捷徑。

　　不過(guò)，在現(xiàn)實(shí)世界中解決這些問(wèn)題的實(shí)用算法只能提供近似值。 近似值正在改善.是否有有效的多項(xiàng)式時(shí)間算法可以 解決NP完全問(wèn)題 是七人之一 千年開(kāi)放問(wèn)題 由克萊數(shù)學(xué)研究所在21世紀(jì)初發(fā)布，每個(gè)獎(jiǎng)金為100萬(wàn)美元。

　　超越圖靈

　　在圖靈的框架之外，還有一種新的計(jì)算形式嗎?1982年，美國(guó)物理學(xué)家 理查德·費(fèi)曼諾貝爾獎(jiǎng)獲得者，提出了基于量子力學(xué)的計(jì)算思想。

　　1995年，美國(guó)應(yīng)用數(shù)學(xué)家Peter Shor提出了一種量子算法 多項(xiàng)式時(shí)間中的因子整數(shù).數(shù)學(xué)家認(rèn)為，這是圖靈框架中的多項(xiàng)式時(shí)間算法無(wú)法解決的。分解整數(shù)意味著找到一個(gè)大于 1 的較小整數(shù)，該整數(shù)可以除以整數(shù)。例如，整數(shù) 688，826，081 可被較小的整數(shù) 25，253 整除，因?yàn)?688，826，081 = 25，253 x 27，277。

　　一種稱為 RSA 算法廣泛用于保護(hù)網(wǎng)絡(luò)通信，是基于分解大整數(shù)的計(jì)算難度。Shor的結(jié)果表明，量子計(jì)算如果成為現(xiàn)實(shí)，它將 改變網(wǎng)絡(luò)安全格局.

　　能否構(gòu)建一臺(tái)成熟的量子計(jì)算機(jī)來(lái)分解整數(shù)并解決其他問(wèn)題?一些科學(xué)家認(rèn)為這是可能的。世界各地的幾個(gè)科學(xué)家小組正在努力建造一個(gè)，有些人已經(jīng)建造了小型量子計(jì)算機(jī)。

　　然而，就像以前發(fā)明的所有新技術(shù)一樣，量子計(jì)算的問(wèn)題幾乎肯定會(huì)出現(xiàn)，這將帶來(lái)新的限制。

　　王杰 是麻省大學(xué)洛厄爾分校的計(jì)算機(jī)科學(xué)教授。