论文部分内容阅读
认识计算机的神奇性
假设你去购买一辆新车，销售员却对你说，“你知道不？这辆车不仅仅能在路上开。”
你说：“啥？”
“真的。你可以用它来做其他很多事情。例如，折叠起来它就变为一辆自行车，展开后它就变为一架飞机了。对了，沉入水中时它还能变为一艘潜水艇。另外，它还是一艘宇宙飞船！”
你可能会认为销售员是在开玩笑，但是，我们的计算机就具有这种类似的灵活性。我们可以使用同一个机器做很多的事情，例如进行飞机飞行模拟，使用电子表格来进行财务预算，用QQ软件与朋友进行聊天等等。计算机几乎与一个可变为汽车、自行车和宇宙飞船的机器一样神奇。
计算机之所以这么神奇，主要是它具有两个特征。首先，计算机是可编程的，也就是说，通过输入一系列适当的指令，我们可以改变一个计算机的行为。其次，电脑是通用的，也就是说，使用正确的程序，我们可以让计算机执行任何一种计算的具体步骤，只要机器有足够的内存和时间。其中，计算的具体步骤，用计算机术语说，叫做算法。
图灵的划时代成果
计算机的这两种特征早已被大众知晓，连一些小孩子都听说过，不过在历史上却是一个划时代的研究成果，它们是计算机科学之父阿兰·图灵在1937年发表的一篇论文中的思想结晶。论文中，图灵描述了一个通用的可编程的机器，可以执行任何一个算法。这种机器通常被称为图灵机，它可以看成现代计算机的最原始的理论模型。
图灵需要在论文中证明他的机器可以执行任何可行的算法，但这并不是一件容易的事情，因为在当时，算法这个概念的定义是非常含糊的，大家还不知道如何用严谨的数学语言来描述。当然，数学家早就发现了许多特定的算法，例如执行加法、乘法和判断一个数是否是素数等的算法。图灵用很简单的方法证明了这些已知的算法都可以在他的机器上执行。但这还不够。图灵还需要以令人信服的方式证明，他的机器可以执行任何算法，包括可能在未来发现的算法。可问题是，算法这个概念没有精确的定义。
为了克服这个问题，图灵用了多个论证方案，每一个都包含不太严谨的理由，来表明他的机器可以计算任何算法。然而，他对论文中不严谨的地方很不满意，认为“在本质上，所有的论点都来源于直觉，出于这个原因，它们在数学上是不完美的”。
超越图灵，理解算法
1985年，英国物理学家大卫·多伊奇做出了一个重要的论断，可能会帮助我们进一步理解算法的本质。
他发现，任何一个算法的执行都必然是由一个物理系统完成的。执行的方式可以是各种各样的：一个人可以用算盘来计算两个数的加法，计算机芯片可以进行飞机飞行模拟的运算。尽管它们看上去完全不同的，但是这两个例子中都是由物理系统在执行算法，而所有的物理系统都遵循相同的物理定理。有鉴于此，多伊奇提出了一个惊世骇俗的原理：任何一种物理过程，你都能够使用一个通用计算机来模拟它。听起来很了不起吧，有点“盗梦空间”的味道。一台机器可以包含一切，以及其中的所有可能的物理定律。想模拟一个超新星？还是一个黑洞的形成？甚至宇宙大爆炸？多伊奇的原理告诉我们，通用计算机可以模拟所有这些东西。所以，在某种意义上，如果你完全理解了通用计算机，你就会明白所有的物理过程。
多伊奇的原理远远超越了图灵的观点。如果他的原理是正确的，那么很自然地，你就知道通用计算机是可以执行任何算法的，因为算法的执行，从本质上来说就是一种物理过程。你可以使用通用计算机来模拟算盘在计算两个数的加法，模拟一个芯片的运行，或做其他的任何在执行某种算法的物理系统。
此外，相较于图灵的观点，多伊奇的原理更容易证明。也许，我们可以使用物理定律直接推导出这个原理。这样，图灵的观点就可以归结到物理定理之中，这最终可能会帮助我们找到给算法下准确定义的办法。
让计算机展现宇宙的一切
不过，为了完成上面的目标，我们还需要把多伊奇的原理进行改进。
首先，我们让这里计算机的概念也包含量子计算机。原则上来说，这对原来的表述并没什么影响，不过，量子计算机可以让我们快速高效地模拟量子物理过程，这一点很重要。量子物理过程是一种不可思议的过程，如果使用传统计算机来模拟的话，那过程将会非常缓慢，以至于在实际中变为一种不可能完成的任务。其次，我们必须弱化一下多伊奇的原理，不追求做到完整模拟，而是以某一精度近似地模拟。这样一来，多伊奇的原理更有可能成立。
还没有人试着从物理定律推断出改进形式的多伊奇的原理。部分原因是，我们不知道物理定律的本质究竟是什么。而且，我们还不知道如何将量子力学与广义相对论相结合在一起。所以，我们也不清楚能否用计算机来模拟出涉及到量子引力的物理过程，比如黑洞的蒸发。
但即使没有引力的量子理论，我们也可以探寻计算机能否模拟出现代物理学的最成功的理论——粒子物理学的标准模型和广义相对论。
研究人员正积极回答这些问题。在过去的几年里，美国物理学家约翰·裴士基的研究小组已经搞清楚了如何使用量子计算机模拟几个量子场论中的理论。虽然要真正在计算机里模拟出量子场论，还需要克服许多技术障碍，但从目前的研究进展来看，势头良好。
然而，广义相对论的情况就变得棘手起来。广义相对论允许奇怪的奇点存在，例如黑洞内部的奇点，而奇点撕裂时空的方式还没有被我们完全理解。虽然一些相对论研究者已经开发出许多技术来模拟特定的物理情况，但目前还没有人能做到用计算机模拟出完整的广义相对论。这仍是一个吸引人的待解问题。
两种科学的统一
美国著名学者司马贺在他的著作《人工科学》中，指出了科学可以分为两种。一种是自然科学，如物理学、生物学之类的科学；另一种则是人工科学，像计算机科学、经济学之类的科学，是由我们人类创造的研究系统。
乍一看，似乎人工科学应该是自然科学的特殊情况。但多伊奇的原理表明，人类创造的研究系统，尤其是计算机科学，可以与自然科学一样丰富多彩。我们使用计算机不仅能模拟出物理定律，也许还能模拟出一个虚拟世界。美国计算机大师阿伦·凯曾说：“在自然科学中，大自然给了我们一个世界，让我们能在其中发现定律。在计算机中，我们可以把这些定律放入其中，再创造出一个世界。”多伊奇的原理提供了一个统一自然科学和人工科学的桥梁，未来当这个桥梁真正搭建起来的时候，将会改变整个科学的面貌。
假设你去购买一辆新车，销售员却对你说，“你知道不？这辆车不仅仅能在路上开。”
你说：“啥？”
“真的。你可以用它来做其他很多事情。例如，折叠起来它就变为一辆自行车，展开后它就变为一架飞机了。对了，沉入水中时它还能变为一艘潜水艇。另外，它还是一艘宇宙飞船！”
你可能会认为销售员是在开玩笑，但是，我们的计算机就具有这种类似的灵活性。我们可以使用同一个机器做很多的事情，例如进行飞机飞行模拟，使用电子表格来进行财务预算，用QQ软件与朋友进行聊天等等。计算机几乎与一个可变为汽车、自行车和宇宙飞船的机器一样神奇。
计算机之所以这么神奇，主要是它具有两个特征。首先，计算机是可编程的，也就是说，通过输入一系列适当的指令，我们可以改变一个计算机的行为。其次，电脑是通用的，也就是说，使用正确的程序，我们可以让计算机执行任何一种计算的具体步骤，只要机器有足够的内存和时间。其中，计算的具体步骤，用计算机术语说，叫做算法。
图灵的划时代成果
计算机的这两种特征早已被大众知晓，连一些小孩子都听说过，不过在历史上却是一个划时代的研究成果，它们是计算机科学之父阿兰·图灵在1937年发表的一篇论文中的思想结晶。论文中，图灵描述了一个通用的可编程的机器，可以执行任何一个算法。这种机器通常被称为图灵机，它可以看成现代计算机的最原始的理论模型。
图灵需要在论文中证明他的机器可以执行任何可行的算法，但这并不是一件容易的事情，因为在当时，算法这个概念的定义是非常含糊的，大家还不知道如何用严谨的数学语言来描述。当然，数学家早就发现了许多特定的算法，例如执行加法、乘法和判断一个数是否是素数等的算法。图灵用很简单的方法证明了这些已知的算法都可以在他的机器上执行。但这还不够。图灵还需要以令人信服的方式证明，他的机器可以执行任何算法，包括可能在未来发现的算法。可问题是，算法这个概念没有精确的定义。
为了克服这个问题，图灵用了多个论证方案，每一个都包含不太严谨的理由，来表明他的机器可以计算任何算法。然而，他对论文中不严谨的地方很不满意，认为“在本质上，所有的论点都来源于直觉，出于这个原因，它们在数学上是不完美的”。
超越图灵，理解算法
1985年，英国物理学家大卫·多伊奇做出了一个重要的论断，可能会帮助我们进一步理解算法的本质。
他发现，任何一个算法的执行都必然是由一个物理系统完成的。执行的方式可以是各种各样的：一个人可以用算盘来计算两个数的加法，计算机芯片可以进行飞机飞行模拟的运算。尽管它们看上去完全不同的，但是这两个例子中都是由物理系统在执行算法，而所有的物理系统都遵循相同的物理定理。有鉴于此，多伊奇提出了一个惊世骇俗的原理：任何一种物理过程，你都能够使用一个通用计算机来模拟它。听起来很了不起吧，有点“盗梦空间”的味道。一台机器可以包含一切，以及其中的所有可能的物理定律。想模拟一个超新星？还是一个黑洞的形成？甚至宇宙大爆炸？多伊奇的原理告诉我们，通用计算机可以模拟所有这些东西。所以，在某种意义上，如果你完全理解了通用计算机，你就会明白所有的物理过程。
多伊奇的原理远远超越了图灵的观点。如果他的原理是正确的，那么很自然地，你就知道通用计算机是可以执行任何算法的，因为算法的执行，从本质上来说就是一种物理过程。你可以使用通用计算机来模拟算盘在计算两个数的加法，模拟一个芯片的运行，或做其他的任何在执行某种算法的物理系统。
此外，相较于图灵的观点，多伊奇的原理更容易证明。也许，我们可以使用物理定律直接推导出这个原理。这样，图灵的观点就可以归结到物理定理之中，这最终可能会帮助我们找到给算法下准确定义的办法。
让计算机展现宇宙的一切
不过，为了完成上面的目标，我们还需要把多伊奇的原理进行改进。
首先，我们让这里计算机的概念也包含量子计算机。原则上来说，这对原来的表述并没什么影响，不过，量子计算机可以让我们快速高效地模拟量子物理过程，这一点很重要。量子物理过程是一种不可思议的过程，如果使用传统计算机来模拟的话，那过程将会非常缓慢，以至于在实际中变为一种不可能完成的任务。其次，我们必须弱化一下多伊奇的原理，不追求做到完整模拟，而是以某一精度近似地模拟。这样一来，多伊奇的原理更有可能成立。
还没有人试着从物理定律推断出改进形式的多伊奇的原理。部分原因是，我们不知道物理定律的本质究竟是什么。而且，我们还不知道如何将量子力学与广义相对论相结合在一起。所以，我们也不清楚能否用计算机来模拟出涉及到量子引力的物理过程，比如黑洞的蒸发。
但即使没有引力的量子理论，我们也可以探寻计算机能否模拟出现代物理学的最成功的理论——粒子物理学的标准模型和广义相对论。
研究人员正积极回答这些问题。在过去的几年里，美国物理学家约翰·裴士基的研究小组已经搞清楚了如何使用量子计算机模拟几个量子场论中的理论。虽然要真正在计算机里模拟出量子场论，还需要克服许多技术障碍，但从目前的研究进展来看，势头良好。
然而，广义相对论的情况就变得棘手起来。广义相对论允许奇怪的奇点存在，例如黑洞内部的奇点，而奇点撕裂时空的方式还没有被我们完全理解。虽然一些相对论研究者已经开发出许多技术来模拟特定的物理情况，但目前还没有人能做到用计算机模拟出完整的广义相对论。这仍是一个吸引人的待解问题。
两种科学的统一
美国著名学者司马贺在他的著作《人工科学》中，指出了科学可以分为两种。一种是自然科学，如物理学、生物学之类的科学；另一种则是人工科学，像计算机科学、经济学之类的科学，是由我们人类创造的研究系统。
乍一看，似乎人工科学应该是自然科学的特殊情况。但多伊奇的原理表明，人类创造的研究系统，尤其是计算机科学，可以与自然科学一样丰富多彩。我们使用计算机不仅能模拟出物理定律，也许还能模拟出一个虚拟世界。美国计算机大师阿伦·凯曾说：“在自然科学中，大自然给了我们一个世界，让我们能在其中发现定律。在计算机中，我们可以把这些定律放入其中，再创造出一个世界。”多伊奇的原理提供了一个统一自然科学和人工科学的桥梁，未来当这个桥梁真正搭建起来的时候，将会改变整个科学的面貌。