計算機變得越來越強大，能力越來越強，但一切都是有限的。 RYZHI/SHUTTERSTOCK

　　授權人 人工智能 技術，今天的計算機可以與人進行令人信服的對話(謝謝， 查特), 創作歌曲, 繪畫玩 國際象棋和圍棋 和 診斷疾病，僅舉幾個他們技術實力的例子。

　　這些成功可以表明計算沒有限制。要了解情況是否如此，重要的是要了解是什么使計算機強大。

　　計算機的能力有兩個方面：其硬件每秒可以執行的操作數量以及它運行的算法的效率。硬件速度受物理定律的限制。 算法 基本上是指令集，由人類編寫，并轉換為計算機硬件可以執行的一系列操作。即使計算機的速度可以達到物理極限，由于算法的限制，計算障礙仍然存在。

　　這些障礙包括計算機無法解決的問題，以及理論上可以解決但實際上甚至超出了當今最強大版本的計算機的能力的問題。數學家和計算機科學家試圖通過在想象的機器上嘗試來確定問題是否可以解決。

　　虛構的計算機

　　算法的現代概念，稱為圖靈機，由英國數學家于1936年提出 艾倫·圖靈.它是一種虛構的設備，模仿用鉛筆在紙上進行算術計算的方式。圖靈機是當今所有計算機都基于的模板。

　　為了適應手動完成需要更多紙張的計算，在 圖靈機 假定為無限制。這相當于一個想象中的無限絲帶或正方形的“磁帶”，每個正方形要么是空白的，要么包含一個符號。

　　機器由一組有限的規則控制，并從磁帶上的初始符號序列開始。機器可以執行的操作是移動到相鄰的正方形，擦除符號并在空白正方形上寫入符號。機器通過執行這些操作的序列進行計算。當機器完成或“停止”時，磁帶上剩余的符號是輸出或結果。

　　計算通常是關于有是或否答案的決策。以此類推，醫學測試(問題類型)檢查患者的標本(問題的實例)是否具有某種疾病指標(是或否答案)。該實例以數字形式在圖靈機中表示，是符號的初始序列。

　　如果圖靈機針對每個實例(無論是正數還是負數)停止，并正確確定實例產生的答案，則問題被認為是“可解決的”。

　　不是每個問題都能解決

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

　　任務是使用一組多米諾骨牌覆蓋整個網格，并按照大多數多米諾骨牌游戲的規則，匹配相鄰多米諾骨牌末端的點數。事實證明，沒有算法可以從一組多米諾骨牌開始，并確定該集是否會完全覆蓋網格。

　　保持合理

　　許多可解決的問題可以通過在合理時間內停止的算法來解決。這些”多項式時間算法“是有效的算法，這意味著使用計算機來解決它們的實例是實用的。

　　數以千計的其他可解決的問題不知道具有多項式時間算法，盡管一直在努力尋找這樣的算法。其中包括旅行推銷員問題。

　　旅行推銷員問題詢問一組具有一些點直接連接的點(稱為圖)是否具有從任何點開始并恰好穿過每隔一點一次的路徑，然后返回到原始點。想象一下，一個推銷員想要找到一條路線，該路線正好經過一個社區中的所有家庭一次并返回起點。

　　這些問題，稱為 NP完全，由兩位計算機科學家獨立制定并證明在 1970 年代初存在，美國加拿大人 斯蒂芬·庫克 和烏克蘭裔美國人 列昂尼德·萊文.庫克的工作排在第一位，他因這項工作獲得了1982年計算機科學界最高的圖靈獎。

　　準確了解的代價

　　NP完全問題最著名的算法本質上是從所有可能的答案中尋找解決方案。幾百個點的圖表上的旅行推銷員問題需要數年時間才能在超級計算機上運行。這樣的算法效率低下，這意味著沒有數學捷徑。

　　不過，在現實世界中解決這些問題的實用算法只能提供近似值。 近似值正在改善.是否有有效的多項式時間算法可以 解決NP完全問題 是七人之一 千年開放問題 由克萊數學研究所在21世紀初發布，每個獎金為100萬美元。

　　超越圖靈

　　在圖靈的框架之外，還有一種新的計算形式嗎?1982年，美國物理學家 理查德·費曼諾貝爾獎獲得者，提出了基于量子力學的計算思想。

　　1995年，美國應用數學家Peter Shor提出了一種量子算法 多項式時間中的因子整數.數學家認為，這是圖靈框架中的多項式時間算法無法解決的。分解整數意味著找到一個大于 1 的較小整數，該整數可以除以整數。例如，整數 688，826，081 可被較小的整數 25，253 整除，因為 688，826，081 = 25，253 x 27，277。

　　一種稱為 RSA 算法廣泛用于保護網絡通信，是基于分解大整數的計算難度。Shor的結果表明，量子計算如果成為現實，它將 改變網絡安全格局.

　　能否構建一臺成熟的量子計算機來分解整數并解決其他問題?一些科學家認為這是可能的。世界各地的幾個科學家小組正在努力建造一個，有些人已經建造了小型量子計算機。

　　然而，就像以前發明的所有新技術一樣，量子計算的問題幾乎肯定會出現，這將帶來新的限制。

　　王杰 是麻省大學洛厄爾分校的計算機科學教授。