作者：孫鵬（劍橋大學計算機系博士）

來源：新原理研究所

上個世紀三十年代，邱奇和圖靈共同提出了通用計算機的概念。在接下來的十多年里，因為戰(zhàn)爭需要下的國家推動，計算機得以很快從理論發(fā)展成為實體。在眾多成果中以圖靈提出的Pilot ACE計算機以及馮諾依曼提出的存儲式計算機最為突出。

戰(zhàn)爭之后，雖然Pilot ACE計算機運行效率更高，但存儲式計算機以其更出色的可編程性獲得了更多計算機科學家的青睞。計算機便以此為基礎開始了近一個世紀的高速發(fā)展。

八十年代初的大眾萬萬想不到十年后如此大塊頭的計算機能夠被放到書桌上并快速普及到每個人的家里。

九十年代的大眾萬萬想不到十年后計算機可以成為我們連接世界的窗口。

千禧年的大眾萬萬想不到十年后計算機也能被握在手里，并且擁有超乎想象的計算能力。

十年前的大眾萬萬想不到如今的計算機擁有我們無法匹敵的“學習”能力，并在很多方面的表現(xiàn)超過了我們最頂尖的專家。

那么十年之后的什么是我們今天想不到的呢？或者我們應該怎么想象十年后的我們才靠譜呢？

《自然》期刊在2014年刊登了一篇Igor Markov的文章《計算的基本極限的極限》（Limits on Fundamental Limits to Computation）。我們將以此文為基礎并綜合各方面論文，探討計算機的極限以及面對這些極限計算機科學家們所采取的措施。希望這些探討能讓大家在腦海中勾勒出十年后的一個大概的輪廓。

在對這些問題探討之前，我們先對計算機的工作原理做個簡單的介紹。幾十年計算機從不同方向上的發(fā)展將整個生態(tài)大概分出了四層，如下圖所示。我們將越靠近用戶的層級叫做高層，越靠近計算機硬件本身的層級叫做低層。從高到低，整個生態(tài)大概可以被分為應用層、編譯層、架構層和電路層。其中應用和編譯層被歸納為軟件層，而架構和電路層被歸納為硬件層。

應用層

在應用層面上，實際的問題被分類成為各種復雜度。需要說明的是計算機只能解決很少一類的問題，即是用有限內(nèi)存能解決的問題。這類問題被歸類成為PSPACE問題，如下圖所示。

值得注意的是這個歸類只考慮了有限內(nèi)存，并沒有考慮完成它所需要的時間。在此基礎上，各種問題又以解決它所需的時間歸納為各種其他復雜度問題，大致包括：

P類復雜度問題必須在多項式時間 t=nc 內(nèi)停止并輸出正確的結果，其中n是輸入的長度，c是常數(shù)。

例子：一個數(shù)是質(zhì)數(shù)嗎？

NP類復雜度問題只要給出一個解，經(jīng)典計算機就能夠快速驗證給出的解是否正確的所有問題。

例子：想象一個有邊和節(jié)點的圖形，例如Facebook的社交網(wǎng)絡圖，其中節(jié)點是個人，如果兩個人建立好友關系，兩個節(jié)點就被一條邊連接。小團體（Clique）是整個圖形的一個子集，其中每一個人都是其他人的朋友，也就是其中任意兩個節(jié)點彼此連接。有人或許會問：存在20個人的小團體嗎？50個人呢？100個人呢？尋找這樣的小團體是圖論領域的一個“NP完全”（NP-complete）問題，NP完全意味著這是NP類問題中最復雜的一種。然而，如果給出了一個潛在的答案，比如說50個節(jié)點可以或不可以形成一個小團體，那么問題就迎刃而解了。

NPC類問題是指在多項式時間內(nèi)，如果所有NP類問題都能被轉(zhuǎn)化為另一個NP問題，那么這個轉(zhuǎn)化后的NP類問題就稱為NP完全問題。NP完全問題滿足兩個條件：1. 本身是NP類問題。2. 所有NP類問題都能規(guī)約到該問題。

例子：給一個整數(shù)集合，證明是否存在一個非空子集，使得該集合內(nèi)的數(shù)字和為0。

BQP類問題是指在多項式時間內(nèi)，量子計算機能夠輕易解決，且錯誤機率小于1/3的所有問題。

例子：確定一個整數(shù)的質(zhì)因數(shù)。

編譯層

程序員在算法的指導下將問題的解決方案寫成程序。程序通過編譯層里的編譯器被翻譯成機器能懂的二進制代碼。

編譯器在翻譯程序的同時也會進行一系列的優(yōu)化，比如將程序并行，使得程序能夠盡可能快得在硬件上面運行。如下圖所示，如果程序員希望計算機做煮飯、洗衣及掃地三項工作，編譯器會先研究可用硬件，發(fā)現(xiàn)三件工作的獨立性（煮飯可以用電飯煲、洗衣可以用洗衣機、掃地可以用吸塵器），并對三項任務進行并行優(yōu)化后翻譯成二進制代碼。

架構層

至此，一個問題的解決方案通過軟件開發(fā)及編譯，進入到硬件層面執(zhí)行。架構層指的是各個硬件單元的功能設計，如下圖所示：

處理器處理來自存儲器和輸入/輸出端的指令，存儲器儲存指令和數(shù)據(jù)，輸入/輸出端連接計算機用戶。簡單來說，程序以指令的形式被存在存儲器中。處理器通過讀取存儲器中的指令來執(zhí)行程序。與此同時，處理器也接受來自輸入/輸出端的指令，并給予相應的回復。這些硬件單元如何排列，各自完成怎樣的工作，就是計算機架構師研究的問題。

電路層

電路層指的是每個硬件單元最底層的硬件設計，通過各種集成電路來實現(xiàn)架構層所設計的功能。由場效應晶體管所組成的開關電路是現(xiàn)代集成電路最主要的組成成分。

傳統(tǒng)的開關電路由MOS場效應晶體管（MOSFET） 制成。MOSFET是具有漏極（Drain）、源極（Source）、柵極（Gate）和襯底（Substrate）的4端子器件。下圖顯示了其三維結構。

柵極和襯底之間由氧化層（二氧化硅）隔開。其工作原理就是在柵極施加一定的電壓后，源極和漏極就會在場效應下聯(lián)通，從而實現(xiàn)通路。若柵極上沒有電壓，則源極和漏極斷開，實現(xiàn)斷路。正是無數(shù)個這寫通路和短路的組合實現(xiàn)了計算機二進制0和1的轉(zhuǎn)換。

最近蘋果和華為相繼發(fā)布了7納米制程工藝的芯片。這是個什么概念呢？首先，制程工藝是指集成電路制造時的精度。因為電流在通過柵極時會有損耗，而柵極長度（Length）決定了電流損耗的程度。柵極長度越小，損耗就越小。而上述提到的7nm的制程工藝就是這個柵極的長度。制程工藝越小，電流損耗就越小，所以能在降低功耗的同時提高性能。這也是近幾十年計算機性能高速發(fā)展的原因。

在了解了計算機的運行原理后，我們可以從工程、功耗、時空概念、復雜理論及新興技術這五個方面的探討計算機的極限，以及面對這些極限計算機科學家們所采取的措施。

未來智能實驗室是人工智能學家與科學院相關機構聯(lián)合成立的人工智能，互聯(lián)網(wǎng)和腦科學交叉研究機構。

未來智能實驗室的主要工作包括：建立AI智能系統(tǒng)智商評測體系，開展世界人工智能智商評測；開展互聯(lián)網(wǎng)（城市）云腦研究計劃，構建互聯(lián)網(wǎng)（城市）云腦技術和企業(yè)圖譜，為提升企業(yè)，行業(yè)與城市的智能水平服務。