Skip to content
Published on

作为普遍概念的计算 — 什么是坚实的，什么是夸大的

🇰🇷KO🇺🇸EN🇯🇵JA🇨🇳ZH
Split View필사 모드
分享
Authors

引言 — 一句话里藏着的两个不同主张

Tim Roughgarden 讲授的“作为普遍而根本的概念的计算(Computation as a universal and fundamental concept)”这门简短的课程，最近成了热门话题。标题诱人做出一种宏大、近乎形而上学的解读：仿佛计算就是宇宙以某种方式由之构成的材料，从星系到神经元，其实都是一个个正在运行的程序。

然而读一读实际内容，你会发现它要克制得多，说实话也更坚实。这是一门从容概览可计算性与复杂度理论的课程。图灵 1936 年的结果、停机问题、为什么有些问题会在一个巧妙的算法面前土崩瓦解而另一些却顽强抵抗，以及 P 对 NP。Roughgarden 是一位复杂度理论学家(他先后任教于斯坦福和哥伦比亚，如今在高等研究院(Institute for Advanced Study))，课程自始至终都停留在坚实的数学地基之上。不需要任何预备知识。

所以，“普遍而根本”这句话其实包含着两个截然不同的主张。一个是精确的、可证明的，而且真正深刻。另一个是迷人却滑不留手的形而上学命题。把这两者切分开来，就是本文的全部。

这门课实际讲了什么

课程以一个貌似简单的问题拉开序幕：有没有计算机做不到的事？然后，它用 1936 年图灵的工作来回答——那是真正的计算机问世十年之前。图灵想象中的机器还带来了一个令人震惊的事实：无论你投入多少时间和硬件，总有一些问题是任何算法都永远无法解决的。停机问题——追问某个程序究竟会在某一刻停下，还是永远运行下去——已经被证明是任何计算机都无法解决的。

“已被证明”这一点很重要。这不是“太慢了”或“内存不够”，而是一堵与哥德尔不完全性同属一脉的数学之墙。课程把从希尔伯特、哥德尔到冯·诺伊曼一脉相承的谱系当作历史而非传说来讲述，展示了追问算法能做什么的传统，与追问其极限的传统，如何缓缓收敛于同一点。

接着，课程转向一个更微妙的问题：在计算机 能够解决 的问题当中，哪些能被快速解决？有些问题会在一个巧妙的想法面前崩塌，比如迪杰斯特拉的最短路径，或卡拉楚巴的快速乘法。另一些问题，比如旅行商问题，则顽固地抵抗。而一个惊人的发现，把成千上万个这样的难题捆到了一起：通过 NP完全性，它们不过是穿着不同衣裳的同一个问题。

这一切都收敛于 P 对 NP。课程恰如其分地称之为计算机科学中最重要的未解难题，也是数学的伟大谜题之一。其中一段以“我们或许身处的两个世界”为框架来呈现：一个是看似困难的问题其实很容易的世界，另一个则是我们大概正身处其中、并非如此的世界。课程在追问这个答案对密码学、AI 和量子计算意味着什么中收尾。

“普遍”一词真正名副其实之处

剥去夸大的成分之后，仍然有真正的理由把计算称为普遍。而它们以两种形式到来。

第一是 模型无关性。图灵机、丘奇的 λ 演算、寄存器机，以及其他所有合理的“有效过程”模型，最终都被证明计算的是完全相同的那一组函数。丘奇和图灵在 1936 年从截然相反的方向出发，却抵达了同一个地方。这一巧合正是丘奇-图灵论题的内容，也是计算之所以不是一台装置、而是一个概念的原因。同一份计算既能在硅片上运行，也能在纸上、在多米诺骨牌上，甚至在像沃尔弗拉姆的规则 110 那样简单的元胞自动机上运行。规则 110 是图灵完备的。底层用什么材料无关紧要。这是一个深刻而绝非不言自明的事实。

第二是 NP完全性，这是一种存在于计算自身内部的另一类普遍性。调度、芯片布局、解谜等无数看似互不相干的问题，被证明是等价的。对其中任何一个找到真正快速的算法，就等于对它们全部找到了快速算法。这不是比喻，也不是类比。这是定理，而世界竟然如此构造，本身就令人惊叹。

而不可计算性，则让“根本”这个词守住了诚实，而非浮夸。停机问题划出了一条线，未来任何硬件、任何量子把戏、任何预算都永远无法越过。一个能够证明——而不只是猜测——自身永久极限的领域，才配得上使用这个词。

从哪里开始变成夸大

上面这些，没有任何一条说宇宙是一台计算机，或者你的心灵是软件。那些是另外的、大得多的主张，而课程两者都没有做。恰恰是在从可证明的版本滑向形而上学版本的那一刻，审慎的思考往往就死了。

最宽泛的版本是数字物理学，它有着悠长的谱系。康拉德·楚泽的“计算的空间(Rechnender Raum)”(1969)、约翰·惠勒的“it from bit”、沃尔弗拉姆的计算等价性原理，以及更晚近的、把宇宙建模为重写系统的他的物理项目。这些都是严肃而富于想象力的构想。但“一切皆计算”有一个失效模式：如果任何可以设想的观测，都同样地能与“宇宙在计算”这一主张相容，那么这个主张就什么也没预测、什么也没排除。一个无法出错的陈述不是理论，而只是一个框架。

诚实的中间地带是物理版丘奇-图灵论题：任何物理过程都可以用图灵机来模拟。这一主张是真正 可证伪 的。只要造出一台能计算不可计算之物的物理装置，也就是真正的超计算机，这条论题就死了。值得注意的是，量子计算机做不到这一点。量子计算机计算的，正是图灵机所能计算的同一批函数，只不过有时快得惊人。这是关于效率的主张，而不是关于可计算性的主张。多伊奇 1985 年的工作把这个物理版本搬上了舞台，也正因为它敢于冒险，才受到尊重。

同样的纪律也适用于心灵。计算是审视认知的一副强大透镜——也就是心灵的计算理论——这是一个富有成果的研究纲领。而大脑在字面意义上除了计算之外什么都不是，则不是定理，而是一个仍在争论中的哲学立场。多重可实现性是一个很好的想法，即同一个函数可以在不同的硬件上运行，但它并不许可“生物学和心灵只不过是计算”这样的跳跃。一副能揭示许多东西的透镜，并不等同于“实在就是由这副透镜构成的”这一主张。

结语

真正站得住脚的“计算是普遍而根本的”版本，正是课程所讲授的那个：模型无关性、绝对的不可计算性、难题之间隐藏的等价性，以及 P 对 NP 这个未解之问。作为开发者，这值得铭记在心，因为它告诉我们哪些墙是永久的(不可计算的问题，以及几乎可以肯定 NP困难的问题)，哪些墙不过是当下的。

实在本身就是计算这个更大的故事，值得手里攥着一个问题去读：这个版本会做出有风险的预测，还是一个能伸缩到吸收任何结果的比喻？物理版丘奇-图灵论题通过了这场考验。“宇宙是一台计算机，就这样”大多通不过，而这个差别并不小。

Roughgarden 的课程之所以值得花时间，恰恰因为它容易被低估。它停留在坚实的地基之上，在有人向宇宙伸手之前，就已经展示了究竟有多少东西是真正在那里的——模型无关性、确凿的极限、深刻的等价性。

参考资料

Discuss on Twitter • View on GitHub