本文由机器之心经授权转载自新原理研究所（ID：newprincipia），未经授权禁止二次转载。
上个世纪三十年代，邱奇和图灵共同提出了通用计算机的概念[1]。在接下来的十多年里，因为战争需要下的国家推动，计算机得以很快从理论发展成为实体。在众多成果中以图灵提出的Pilot ACE计算机以及冯诺依曼提出的存储式计算机最为突出。
战争之后，虽然Pilot ACE计算机运行效率更高，但存储式计算机以其更出色的可编程性获得了更多计算机科学家的青睐。计算机便以此为基础开始了近一个世纪的高速发展。
八十年代初的大众万万想不到十年后如此大块头的计算机能够被放到书桌上并快速普及到每个人的家里。
九十年代的大众万万想不到十年后计算机可以成为我们连接世界的窗口。
千禧年的大众万万想不到十年后计算机也能被握在手里，并且拥有超乎想象的计算能力。
十年前的大众万万想不到如今的计算机拥有我们无法匹敌的“学习”能力，并在很多方面的表现超过了我们最顶尖的专家。
那么十年之后的什么是我们今天想不到的呢？或者我们应该怎么想象十年后的我们才靠谱呢？
《自然》期刊在2014年刊登了一篇Igor Markov的文章《计算的基本极限的极限》（Limits on Fundamental Limits to Computation） [2]。我们将以此文为基础并综合各方面论文，探讨计算机的极限以及面对这些极限计算机科学家们所采取的措施。希望这些探讨能让大家在脑海中勾勒出十年后的一个大概的轮廓。
在对这些问题探讨之前，我们先对计算机的工作原理做个简单的介绍。几十年计算机从不同方向上的发展将整个生态大概分出了四层，如下图所示。我们将越靠近用户的层级叫做高层，越靠近计算机硬件本身的层级叫做低层。从高到低，整个生态大概可以被分为应用层、编译层、架构层和电路层。其中应用和编译层被归纳为软件层，而架构和电路层被归纳为硬件层。
应用层
在应用层面上，实际的问题被分类成为各种复杂度。需要说明的是计算机只能解决很少一类的问题，即是用有限内存能解决的问题。这类问题被归类成为PSPACE问题，如下图所示。
值得注意的是这个归类只考虑了有限内存，并没有考虑完成它所需要的时间。在此基础上，各种问题又以解决它所需的时间归纳为各种其他复杂度问题，大致包括：
P类复杂度问题必须在多项式时间 t=nc 内停止并输出正确的结果，其中n是输入的长度，c是常数。
例子：一个数是质数吗？
NP类复杂度问题只要给出一个解，经典计算机就能够快速验证给出的解是否正确的所有问题。
例子：想象一个有边和节点的图形，例如Facebook的社交网络图，其中节点是个人，如果两个人建立好友关系，两个节点就被一条边连接。小团体（Clique）是整个图形的一个子集，其中每一个人都是其他人的朋友，也就是其中任意两个节点彼此连接。有人或许会问：存在20个人的小团体吗？50个人呢？100个人呢？寻找这样的小团体是图论领域的一个“NP完全”（NP-complete）问题，NP完全意味着这是NP类问题中最复杂的一种。然而，如果给出了一个潜在的答案，比如说50个节点可以或不可以形成一个小团体，那么问题就迎刃而解了。
NPC类问题是指在多项式时间内，如果所有NP类问题都能被转化为另一个NP问题，那么这个转化后的NP类问题就称为NP完全问题。NP完全问题满足两个条件：1. 本身是NP类问题。2. 所有NP类问题都能规约到该问题。
例子：给一个整数集合，证明是否存在一个非空子集，使得该集合内的数字和为0。
BQP类问题是指在多项式时间内，量子计算机能够轻易解决，且错误机率小于1/3的所有问题。
例子：确定一个整数的质因数。
编译层
程序员在算法的指导下将问题的解决方案写成程序。程序通过编译层里的编译器被翻译成机器能懂的二进制代码。
编译器在翻译程序的同时也会进行一系列的优化，比如将程序并行，使得程序能够尽可能快得在硬件上面运行。如下图所示，如果程序员希望计算机做煮饭、洗衣及扫地三项工作，编译器会先研究可用硬件，发现三件工作的独立性（煮饭可以用电饭煲、洗衣可以用洗衣机、扫地可以用吸尘器），并对三项任务进行并行优化后翻译成二进制代码。
至此，一个问题的解决方案通过软件开发及编译，进入到硬件层面执行。架构层指的是各个硬件单元的功能设计，如下图所示：
处理器处理来自存储器和输入/输出端的指令，存储器储存指令和数据，输入/输出端连接计算机用户。简单来说，程序以指令的形式被存在存储器中。处理器通过读取存储器中的指令来执行程序。与此同时，处理器也接受来自输入/输出端的指令，并给予相应的回复。这些硬件单元如何排列，各自完成怎样的工作，就是计算机架构师研究的问题。
电路层
电路层指的是每个硬件单元最底层的硬件设计，通过各种集成电路来实现架构层所设计的功能。由场效应晶体管所组成的开关电路是现代集成电路最主要的组成成分。
传统的开关电路由MOS场效应晶体管（MOSFET) 制成。MOSFET是具有漏极（Drain）、源极（Source）、栅极（Gate）和衬底（Substrate）的4端子器件。下图显示了其三维结构。
栅极和衬底之间由氧化层（二氧化硅）隔开。其工作原理就是在栅极施加一定的电压后，源极和漏极就会在场效应下联通，从而实现通路。若栅极上没有电压，则源极和漏极断开，实现断路。正是无数个这写通路和短路的组合实现了计算机二进制0和1的转换。
最近苹果和华为相继发布了7纳米制程工艺的芯片。这是个什么概念呢？首先，制程工艺是指集成电路制造时的精度。因为电流在通过栅极时会有损耗，而栅极长度（Length）决定了电流损耗的程度。栅极长度越小，损耗就越小。而上述提到的7nm的制程工艺就是这个栅极的长度。制程工艺越小，电流损耗就越小，所以能在降低功耗的同时提高性能。这也是近几十年计算机性能高速发展的原因。
在介绍完计算机运行原理之后，我们在后文将通过每个层级，从工程、功耗、时空概念、复杂理论及新兴技术这五个方面探讨计算机的极限以及面对这些极限计算机科学家们所采取的措施。
参考链接：
[1]. Igor L.Markov, “Limits on Fundamental Limits to Computation”, Nature, vol. 512, pp. 147 - 154
[2]. Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey 2nd edn (Springer, 2013).
[3]. William. M. Holt, “Moore’s Law: A path going forward”, ISSCC, 2016
[4]. https://en.wikipedia.org/wiki/Photolithography
[5]. X.Ma and G.R. Arce, “Computational Lithography” (Wiley, 2011)
[6]. M.Bohr, “Interconnect scaling — the real limiter to high performance ULSI”, in Proc Int.Elec.Device Meeting, pp. 241-244.
[7]. V. R. Almeida et al, “All optical control of light on a silicon chip”, Nature vol.431, pp. 1081-1084.
[8]. J. A. Davis et. al, “Interconnect limits on gigascale integration in the 21st century”, Proc. IEEE pp.305-324.
[9]. D. Hisamoto et. al, “FinFET — a self aligned double-gate MOSFET scalable to 20nm”, IEEE Trans. Electron. Dev. vol. 47, pp. 2320 - 2325.
[10]. A. Seabaugh, “The tunnelling transistor”, IEEE Spectrum. http://spectrum.ieee.org/semiconductors/devices/the-tunneling-transistor
[11]. Dennard, Robert H.; Gaensslen, Fritz; Yu, Hwa-Nien; Rideout, Leo; Bassous, Ernest; LeBlanc, Andre (October 1974). "Design of ion-implanted MOSFET's with very small physical dimensions", IEEE Journal of Solid State Circuits.
[12]. H. Esmaeilzadeh et. al, “Dark Silicon and the End of Multicore Scaling”, in Porc of ISCA 2011.
[13]. Z. Yeraswork, “3D stacks and security key for IBM in server market”, EE Times, 2013.
[14]. R. Landauer, “Irreversibility and heat generation in the computing process”, IBM journal of research and development, pp. 183 – 191, 1961.
[15]. A. Berut et. al, “ Experimental verification of Landauer’s principle linking information and thermodynamics”, Nature, vol. 483, 187-189, 2012.
[16]. Y. Aharonov and D. Bohm, “Time in the quantum theory and the uncertainty relation for time and energy”, Physics, vol.122, 1649-1658, 1966.
[17]. J. Ren and V.K. Semenov, “Progress with physically and logically reversible superconducting digital circuits”, IEEE Trans. Appl. Supercond. 21, pp. 780 – 786, 2011.
[18]. C. Monroe et. al, “Large scale modular quantum computer architecture with atomic memory and photonic interconnects”, Physics, Rev.A89, 022317, 2014.
[19]. Fisher, D. Your favourite parallel algorithms might not be as fast as you think. IEEE Trans. Comput. 37, 211–213 (1988)
[20]. International Technology Roadmap for Semiconductors (ITRS). http://www.itrs.net/ (2013).
[21]. Shulaker, M. et al. Carbon nanotube computer. Nature 501, 526–530 (2013).
[22]. Simonite, T. Intel’s laser chips could make data centers run better. MIT Technol. Rev. (4 September 2013).
[23]. Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information (Cambridge Univ. Press, 2011).
[24]. Shin, S. W., Smith, G., Smolin, J. A. & Vazirani, U. How ‘quantum’ is the D-Wave machine? Preprint at http://arxiv.org/abs/1401.7087 (2014).
[25]. Gus eld, D. “Algorithms on Strings, Trees and Sequences,” Computer Science and Computational Biology. Cambridge University Press, 1997.
[26]. Conitzer, V. and sandholm, T. “New Complexity Results about Nash Equilibria,” Games and Economic Behaviour 63, 2 (july 2008), 621–641.
[27]. Fortnow, L. The status of the P versus NP problem. Commun. ACM 52, 78–86 (2009)
[28]. Markov, I. L. Know your limits: a review of ‘limits to parallel computation: P-completeness theory’. IEEE Design Test 30, 78–83 (2013).
[29]. Wiesner, S, “Conjugate Coding”, Sigact news, 18: 78–88, 1983.
[30]. David Deutsch, “Quantum theory, the Church-Turing principle and the Universal Quantum Computer”, Proc. R. Soc. Lond.
[31]. https://en.wikipedia.org/wiki/Quantum_computing
[32]. Shor, Peter W.（1997）, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26 (5): 1484–1509
[33]. Scott Aaronson, “The Limit of Quantum,” Scientific Amarican, 2008
[34]. Erico Guizzo, “Loser: D-Wave Does Not Quantum Compute,” IEEE Spectrum, Dec 2009.
[35]. Lov K Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” Quantum Physics, v3, 1996.
[36]. Scott Aaronson, “Forrelation: A Problem that Optimally Separates Quantum from Classical Computing,” STOC’15, June 14–17, 2015, Portland, Oregon, USA.
[37]. Daniel S. Abrams and Seth Lloyd, “Nonlinear Quantum Mechanics Implies Polynomial Solution for NP-complete and #P Problems,” Quantum Physics, Phys.Rev.Lett. 81 (1998) 3992-3995.
[38]. Scott Aaronson and John Watrous, “Closed Timelike Curves Make Quantum and Classical Computing Equivalent,” Quantum Physics, arXiv:08082669.
本文由机器之心经授权转载自新原理研究所（ID：newprincipia），未经授权禁止二次转载。
