双语阅读

Computers are growing more powerful and more capable, but everything has limits.

计算机变得越来越强大，能力越来越强，但一切都有极限。

Empowered by artificial intelligence technologies, computers today can engage in convincing conversations with people (thanks, ChatGPT), compose songs, paint paintings, play chess and go and diagnose diseases, to name just a few examples of their technological prowess.

在人工智能技术的支持下，今天的计算机可以与人进行令人信服的对话(感谢ChatGPT)，作曲、绘画、下棋、围棋和诊断疾病，这只是它们技术实力的几个例子。

These successes could be taken to indicate that computation has no limits. To see if that's the case, it's important to understand what makes a computer powerful.

这些成功可以用来表明计算是没有极限的。要弄清楚情况是否如此，重要的是要了解是什么让计算机如此强大。

There are two aspects to a computer's power: the number of operations its hardware can execute per second and the efficiency of the algorithms it runs. The hardware speed is limited by the laws of physics. Algorithms — basically sets of instructions — are written by humans and translated into a sequence of operations that computer hardware can execute. Even if a computer's speed could reach the physical limit, computational hurdles remain due to the limits of algorithms.

计算机的能力有两个方面:其硬件每秒可以执行的操作数量和运行算法的效率。硬件的速度受到物理定律的限制。算法——基本上是一组指令——由人类编写，并转化为计算机硬件可以执行的一系列操作。即使计算机的速度可以达到物理极限，由于算法的限制，计算障碍仍然存在。

These hurdles include problems that are impossible for computers to solve and problems that are theoretically solvable but in practice are beyond the capabilities of even the most powerful versions of today's computers. Mathematicians and computer scientists attempt to determine whether a problem is solvable by trying them out on an imaginary machine.

这些障碍包括一些计算机不可能解决的问题，以及一些理论上可以解决，但实际上甚至是当今最强大版本的计算机都无法解决的问题。数学家和计算机科学家试图通过在一台假想的机器上试验来确定一个问题是否可以解决。

Contents 目录

1. An Imaginary Computing Machine 虚构的计算机
2. Not Every Problem Can Be Solved 不是每个问题都能解决
3. Keeping It Reasonable 保持合理性
4. The Cost of Knowing Exactly 了解真相的代价
5. Beyond Turing 超越图灵

An Imaginary Computing Machine 虚构的计算机

The modern notion of an algorithm, known as a Turing machine, was formulated in 1936 by British mathematician Alan Turing. It's an imaginary device that imitates how arithmetic calculations are carried out with a pencil on paper. The Turing machine is the template all computers today are based on.

现代算法的概念被称为图灵机，是由英国数学家艾伦·图灵在1936年提出的。这是一种虚构的装置，用来模仿用铅笔在纸上进行算术计算的方式。图灵机是当今所有计算机所基于的模板。

To accommodate computations that would need more paper if done manually, the supply of imaginary paper in a Turing machine is assumed to be unlimited. This is equivalent to an imaginary limitless ribbon or "tape" of squares, each of which is either blank or contains one symbol.

为了适应人工计算需要更多纸张的计算，图灵机中假想纸张的供应被假定为无限的。这相当于一个想象的无限的方块丝带或“带子”，每个方块要么是空白的，要么包含一个符号。

The machine is controlled by a finite set of rules and starts on an initial sequence of symbols on the tape. The operations the machine can carry out are moving to a neighboring square, erasing a symbol and writing a symbol on a blank square. The machine computes by carrying out a sequence of these operations. When the machine finishes or "halts" the symbols remaining on the tape are the output or result.

机器由一组有限的规则控制，并从纸带上的初始符号序列开始。机器可以执行的操作是移动到相邻的方格，擦除符号和在空白方格上写入符号。这台机器通过执行一系列这样的操作来进行计算。当机器完成或“停止”时，留在纸带上的符号就是输出或结果。

Computing is often about decisions with yes or no answers. By analogy, a medical test (type of problem) checks if a patient's specimen (an instance of the problem) has a certain disease indicator (yes or no answer). The instance, represented in a Turing machine in digital form, is the initial sequence of symbols.

计算通常是关于“是”或“否”的决定。类似地，医学测试(问题类型)检查患者的样本(问题实例)是否具有某种疾病指标(是或否答案)。例如，在图灵机中以数字形式表示，是符号的初始序列。

A problem is considered "solvable" if a Turing machine halts for every instance, whether positive or negative, and correctly determines which answer the instance yields.

如果图灵机在每个实例中都停止，无论结果是正的还是负的，并正确地确定实例产生的答案，那么这个问题就被认为是“可解决的”。

Not Every Problem Can Be Solved 不是每个问题都能解决

Many problems are solvable using a Turing machine and therefore can be solved on a computer, while many others are not. For example, the domino problem, a variation of the tiling problem formulated by Chinese American mathematician Hao Wang in 1961, is not solvable.

许多问题可以用图灵机解决，因此可以在计算机上解决，而其他许多问题则不能。例如，多米诺骨牌问题，是华裔美国数学家王浩1961年提出的平铺问题的一种变体，是不可解的。

The task is to use a set of dominoes to cover an entire grid and, following the rules of most dominoes games, matching the number of pips on the ends of abutting dominoes. It turns out that there is no algorithm that can start with a set of dominoes and determine whether or not the set will completely cover the grid.

任务是使用一组多米诺骨牌覆盖整个网格，并遵循大多数多米诺骨牌游戏的规则，匹配相邻多米诺骨牌两端的点数。事实证明，没有一种算法可以从一组多米诺骨牌开始，并确定这组骨牌是否会完全覆盖网格。

Keeping It Reasonable 保持合理性

A number of solvable problems can be solved by algorithms that halt in a reasonable amount of time. These "polynomial-time algorithms" are efficient algorithms, meaning it's practical to use computers to solve instances of them.

许多可解决的问题可以通过在合理的时间内暂停的算法来解决。这些“多项式时间算法”是有效的算法，这意味着使用计算机来解决它们的实例是可行的。

Thousands of other solvable problems are not known to have polynomial-time algorithms, despite ongoing intensive efforts to find such algorithms. These include the Traveling Salesman Problem.

成千上万的其他可解决的问题还不知道有多项式时间算法，尽管正在进行大量的努力来寻找这样的算法。其中包括旅行商问题。

The Traveling Salesman Problem asks whether a set of points with some points directly connected, called a graph, has a path that starts from any point and goes through every other point exactly once, and comes back to the original point. Imagine that a salesman wants to find a route that passes all households in a neighborhood exactly once and returns to the starting point.

旅行商问题问的是，一组点与一些点直接相连的点(称为图)是否有一条路径，从任意一点开始，经过其他所有点只经过一次，然后回到原始点。想象一下，一个销售人员想要找到一条路线，该路线刚好经过一个社区的所有家庭一次，然后返回起点。

These problems, called NP-complete, were independently formulated and shown to exist in the early 1970s by two computer scientists, American Canadian Stephen Cook and Ukrainian American Leonid Levin. Cook, whose work came first, was awarded the 1982 Turing Award, the highest in computer science, for this work.

这些问题被称为np完全问题，在20世纪70年代初由两位计算机科学家——加拿大裔美国人斯蒂芬·库克和乌克兰裔美国人列昂尼德·莱文独立提出并证明了它们的存在。库克的工作是第一位的，他因此获得了1982年的图灵奖，这是计算机科学的最高奖项。

The Cost of Knowing Exactly 了解真相的代价

The best-known algorithms for NP-complete problems are essentially searching for a solution from all possible answers. The Traveling Salesman Problem on a graph of a few hundred points would take years to run on a supercomputer. Such algorithms are inefficient, meaning there are no mathematical shortcuts.

np完全问题最著名的算法本质上是从所有可能的答案中寻找解决方案。在一个由几百个点组成的图表上，旅行商问题需要在超级计算机上运行数年。这样的算法效率很低，这意味着没有数学上的捷径。

Practical algorithms that address these problems in the real world can only offer approximations, though the approximations are improving. Whether there are efficient polynomial-time algorithms that can solve NP-complete problems is among the seven millennium open problems posted by the Clay Mathematics Institute at the turn of the 21st century, each carrying a prize of $1 million.

在现实世界中解决这些问题的实用算法只能提供近似，尽管近似正在改进。是否有有效的多项式时间算法可以解决np完全问题，这是克莱数学研究所在21世纪初发布的七个千年开放问题之一，每个问题都有100万美元的奖金。

Beyond Turing 超越图灵

Could there be a new form of computation beyond Turing's framework? In 1982, American physicist Richard Feynman, a Nobel laureate, put forward the idea of computation based on quantum mechanics.

会有一种新的计算形式超越图灵的框架吗?1982年，诺贝尔奖得主、美国物理学家理查德·费曼(Richard Feynman)提出了基于量子力学的计算思想。

In 1995, Peter Shor, an American applied mathematician, presented a quantum algorithm to factor integers in polynomial time. Mathematicians believe that this is unsolvable by polynomial-time algorithms in Turing's framework. Factoring an integer means finding a smaller integer greater than 1 that can pide the integer. For example, the integer 688,826,081 is pisible by a smaller integer 25,253, because 688,826,081 = 25,253 x 27,277.

1995年，美国应用数学家彼得·肖尔(Peter Shor)提出了一种在多项式时间内分解整数的量子算法。数学家们认为，在图灵的框架下，这是用多项式时间算法无法解决的。一个整数因式分解是指找到一个比1大的能整除这个整数的整数。例如，整数688,8260,081可以被一个更小的整数25,253整除，因为688,8260,081 = 25,253 x 27,277。

A major algorithm called the RSA algorithm, widely used in securing network communications, is based on the computational difficulty of factoring large integers. Shor's result suggests that quantum computing, should it become a reality, will change the landscape of cybersecurity.

一种被称为RSA的主要算法，广泛用于网络通信的安全，是基于分解大整数的计算难度。肖尔的结果表明，如果量子计算成为现实，它将改变网络安全的格局。

Can a full-fledged quantum computer be built to factor integers and solve other problems? Some scientists believe it can be. Several groups of scientists around the world are working to build one, and some have already built small-scale quantum computers.

一个成熟的量子计算机能被用来分解整数和解决其他问题吗?一些科学家相信这是可能的。世界各地的几个科学家小组正在努力建造一个，一些人已经建造了小型量子计算机。

Nevertheless, like all novel technologies invented before, issues with quantum computation are almost certain to arise that would impose new limits.

然而，就像之前发明的所有新技术一样，量子计算的问题几乎肯定会出现，从而带来新的限制。