作者：孫鵬（劍橋大學(xué)計(jì)算機(jī)系博士）

來(lái)源：新原理研究所

上個(gè)世紀(jì)三十年代，邱奇和圖靈共同提出了通用計(jì)算機(jī)的概念。在接下來(lái)的十多年里，因?yàn)閼?zhàn)爭(zhēng)需要下的國(guó)家推動(dòng)，計(jì)算機(jī)得以很快從理論發(fā)展成為實(shí)體。在眾多成果中以圖靈提出的Pilot ACE計(jì)算機(jī)以及馮諾依曼提出的存儲(chǔ)式計(jì)算機(jī)最為突出。

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

八十年代初的大眾萬(wàn)萬(wàn)想不到十年后如此大塊頭的計(jì)算機(jī)能夠被放到書(shū)桌上并快速普及到每個(gè)人的家里。

九十年代的大眾萬(wàn)萬(wàn)想不到十年后計(jì)算機(jī)可以成為我們連接世界的窗口。

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

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

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

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

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

應(yīng)用層

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

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

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

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

NP類(lèi)復(fù)雜度問(wèn)題只要給出一個(gè)解，經(jīng)典計(jì)算機(jī)就能夠快速驗(yàn)證給出的解是否正確的所有問(wèn)題。

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

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

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

BQP類(lèi)問(wèn)題是指在多項(xiàng)式時(shí)間內(nèi)，量子計(jì)算機(jī)能夠輕易解決，且錯(cuò)誤機(jī)率小于1/3的所有問(wèn)題。

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

編譯層

程序員在算法的指導(dǎo)下將問(wèn)題的解決方案寫(xiě)成程序。程序通過(guò)編譯層里的編譯器被翻譯成機(jī)器能懂的二進(jìn)制代碼。

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

架構(gòu)層

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

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

電路層

電路層指的是每個(gè)硬件單元最底層的硬件設(shè)計(jì)，通過(guò)各種集成電路來(lái)實(shí)現(xiàn)架構(gòu)層所設(shè)計(jì)的功能。由場(chǎng)效應(yīng)晶體管所組成的開(kāi)關(guān)電路是現(xiàn)代集成電路最主要的組成成分。

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

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

最近蘋(píng)果和華為相繼發(fā)布了7納米制程工藝的芯片。這是個(gè)什么概念呢？首先，制程工藝是指集成電路制造時(shí)的精度。因?yàn)?a href="http://www.brongaenegriffin.com/tags/電流/" target="_blank">電流在通過(guò)柵極時(shí)會(huì)有損耗，而柵極長(zhǎng)度（Length）決定了電流損耗的程度。柵極長(zhǎng)度越小，損耗就越小。而上述提到的7nm的制程工藝就是這個(gè)柵極的長(zhǎng)度。制程工藝越小，電流損耗就越小，所以能在降低功耗的同時(shí)提高性能。這也是近幾十年計(jì)算機(jī)性能高速發(fā)展的原因。

在了解了計(jì)算機(jī)的運(yùn)行原理后，我們可以從工程、功耗、時(shí)空概念、復(fù)雜理論及新興技術(shù)這五個(gè)方面的探討計(jì)算機(jī)的極限，以及面對(duì)這些極限計(jì)算機(jī)科學(xué)家們所采取的措施。

未來(lái)智能實(shí)驗(yàn)室是人工智能學(xué)家與科學(xué)院相關(guān)機(jī)構(gòu)聯(lián)合成立的人工智能，互聯(lián)網(wǎng)和腦科學(xué)交叉研究機(jī)構(gòu)。

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