计算机科学的精髓并非机器本身，而是可计算性的边界与算法的极限。这门学科的两个根源，一为数学，一为工程，恰是这种双重血统，催生了超越任何具体硬件的深刻洞见。在这里，纯粹的逻辑结构足以揭示跨越世纪的奥秘，其深度远超芯片的物理速度。理论发现的丰饶，正源于对计算过程本身的迷恋，可以脱离实体而存续。
内容由AI智能生成
有用
（来源：图灵人工智能）
转自哲学园，仅用于学术分享，如有侵权留言删除报道
计算机科学需要计算机吗？
这个领域的理论部分并不需要计算机这种机器。但如果没有计算机，许多问题可能根本不会被提出。
Qualia
这位计算机科学先驱埃兹赫尔·戴克斯特拉（Edsger Dijkstra）是 1972 年 A.M. 图灵奖（在新标签页打开）得主，也是整个计算领域中最具标志性的算法之一的发明者；要说他有什么最鲜明的特点，那就是极有主见。例如，某些编程语言就曾招致他的猛烈抨击：他曾把 Fortran 称为“幼儿期疾病”，并声称，“使用 COBOL 会使人的头脑残废；因此，教授 COBOL 应当被视为一种犯罪行为。”在解释自己为什么鄙视在工作中使用计算机时，他写道：“医学研究人员并不需要亲自患上他们所研究的疾病。”
计算机科学研究的是计算机吗？如果不是，那么它究竟研究什么？
我第一次接触到戴克斯特拉那些尖锐而著名的观点，是将近四年前，那时我刚加入 Quanta，担任报道计算机科学的专职撰稿人。这个领域对我来说是新的——此前我是物理学记者，再之前则是一名物理学家——而且我很快就发现，大多数人其实不知道该如何理解“计算机科学记者”这个说法。在更广泛的公共讨论中，计算机科学实际上几乎就是编程（programming）或编码（coding）的同义词；但在 Quanta，我们报道的是这个领域较少为人理解的理论一面。后来，我偶然看到了一句据说出自戴克斯特拉、也是他众多令人难忘的断言中我最喜欢的一句：计算机科学之于计算机，就像天文学之于望远镜。
后来我才发现，这个类比可能并不是戴克斯特拉最早提出的，不过他大概会赞同其中的意思。对我来说，这句话提供了一种简洁、有挑衅意味的方式，可以把我的报道与科技新闻区别开来。而且我也不能否认，这句话多少让我感到受用：按照它的暗示，我所报道的这个领域研究的是某种深刻、永恒、超越单纯技术创新的东西。
我渐渐养成了经常引用这个类比的习惯——包括在 一期Quanta 播客中——但同时，我也开始对它产生一些疑虑，只是自己一时说不清原因。我是不是仅仅因为这句话暗暗贬低了那些制造望远镜的前同事而感到内疚？还是说，这个类比确实遗漏了某种重要的东西？
我决定试着把这件事弄个明白。计算机科学研究的是计算机吗？如果不是，那么它究竟研究什么？
我一头扎进的是一场由来已久的争论。研究人员在 20 世纪 30 年代开始发展关于计算的数学理论。工程师则在 20 世纪 40 年代制造出了第一批通用电子计算机。在随后的几十年里，当数学与工程学的研究传统汇合在一起时，计算机科学作为一个独立的学术领域逐渐形成，而围绕这个新领域究竟是什么的争论也很快随之而来。1967 年，著名计算机科学家艾伦·纽厄尔（Allen Newell）、艾伦·佩利斯（Alan Perlis）和赫伯特·西蒙（Herbert Simon）在 Science 杂志上一封措辞激烈的致编辑信中明确表明了自己的立场。他们写道——语气中或许还带着一点不耐烦：“凡是存在现象的地方，就可以有一门科学来描述和解释这些现象。”“计算机是存在的。因此，计算机科学就是研究计算机的科学。”
在哲学中，“感受质”（qualia）指的是我们经验中的主观性质：比如爱丽丝看到蓝色时究竟是什么感觉，或者鲍勃感到愉悦时究竟是什么感觉。正如已故哲学家丹尼尔·丹尼特（Daniel Dennett）所说，感受质就是“事物在我们看来呈现出来的样子”。在这些文章中，我们的专栏作者追随自己的好奇心，探索那些重要、但未必能够得到答案的科学问题。
纽厄尔、佩利斯和西蒙写那封信，部分是在回应这样一类批评者：他们认为，任何真正配得上“科学”之名的学科，都必须研究自然现象。三人则以一些人工现象为例加以反驳——这些人工现象在化学等早已建立起来的科学中同样被认为值得研究。在西蒙 1969 年出版的《人工科学》（The Sciences of the Artificial）一书中，他走得更远，干脆拥抱了这一差别：他认为，恰恰是对那些经过有意设计的人造系统的关注，构成了计算机科学的独特之处。
1974 年，计算机科学家唐纳德·克努特（Donald Knuth）提出了另一种关于这个领域的看法。他强调的是计算的过程，而不是计算机本身。他把计算机科学定义为对算法的研究，也就是研究那些精确的、一步一步执行的程序，而计算机正是依靠这些程序完成任务。算法可以用不同的编程语言来实现，就像同一个思想可以用英语、普通话或阿拉伯语表达一样。人类也会使用算法，而且并不只是用它来解决数学问题，我们在给物品排序之类的任务中同样会使用算法。从这个角度看，计算背后的数学才是核心；计算机本身之所以重要，只是因为它们让我们能够处理那些凭我们人类自己的时间和耐心根本无法完成的问题。
克努特的定义对我很有吸引力，但西蒙及其同事给出的定义所具有的那种简单明了，也很难否认。然而，无论是这些定义，还是其他任何定义，似乎都没有在研究人员中获得普遍认同。为什么会这样？我去问了威廉·拉帕波特（William Rapaport）。他是布法罗大学计算机科学与哲学荣休教授，曾经对人们提出的各种计算机科学定义做过极为详尽的梳理。他认为，这种分歧最终源于这个领域异常明显的跨学科起源。
“计算机科学有两个父母，”他告诉我。“一个父母是数学，另一个父母是工程，而计算机科学实际上就是这两者的混合体。”
不过，拉帕波特仍然认为这个领域存在某种思想上的统一性——它并不只是数学和工程披上一件风衣假扮成一门学科。在他看来，计算机科学研究的是两个核心问题，而不同的子领域分别以自己的方式回答它们：“什么东西是可计算的，以及你怎样计算它？”
我觉得这个框架很有帮助。显然，计算机科学中有一些分支，计算机硬件和软件是不可或缺的，比如操作系统设计或内存管理研究。但我最终最感兴趣的，还是这个领域的理论一面；在这里，研究人员甚至根本不需要碰一台真实存在的实体计算机。那么，在这些理论研究中，计算机是否扮演着不可或缺的概念性角色？如果我要弄清自己为什么对戴克斯特拉那句话怀有这种复杂感受，这正是我必须调查的问题。
先从拉帕波特的第一个问题开始：什么东西是可计算的？ 要想从理论角度开始回答这个问题，你首先就必须给“计算”建立一个数学形式化——研究人员称之为计算模型（model of computation）。20 世纪 30 年代，研究人员提出了若干彼此不同的计算模型，并开始研究这些模型各自意味着什么。
随后，在一篇著名的 1937 年论文中，数学家艾伦·图灵（Alan Turing）构造了一种基于假想机器的模型。这种机器可以按照一组简单规则，在一条无限长的纸带上读取和写入符号。图灵以及其他研究人员很快证明，这个后来产生巨大影响的“图灵机”模型，在数学上与其他研究人员提出的计算模型是等价的。突然之间，研究人员不再面对若干彼此不同的定义，而是拥有了一套统一的、普适的计算理论。
然而，图灵的计算理论其实并不是关于计算机的——至少一开始不是。图灵撰写那篇奠基性论文时，不仅手头没有通用计算机，甚至推动他研究这个问题的动机也不是想理解未来这种机器究竟可能怎样工作。相反，他是在试图解决数学基础中的一个核心问题。他把自己的机器看作一种方式，用来模拟一个人进行计算时的心智活动。
更进一步说，计算理论还可以广泛应用于许多我们根本不会称之为“计算机”的事物。研究人员经常把自然过程建模为计算过程，然后对其进行数学分析。他们利用这种计算视角来揭示物理系统中的不可预测行为、分析演化动力学，以及攻克量子引力中的难题等等。颇具讽刺意味的是，西蒙在 20 世纪 60 年代曾高度称赞为“人工科学”的这个领域，如今反而已经成为我们理解自然世界的一种核心工具。
“你可以透过计算来看待其他科学，”剑桥大学理论计算机科学家汤姆·古尔（Tom Gur）说。“这里存在着一种底层的逻辑模式，而这种模式几乎无处不在地显现出来。”
对于拉帕波特的第一个问题，这个答案似乎很好地维护了戴克斯特拉那句话。接下来还有拉帕波特的第二个问题：一旦你决定要计算某样东西，你究竟该怎样去计算它？对理论计算机科学家来说，答案存在于算法的数学之中。在 20 世纪 60 年代末和 70 年代初，他们开始建立一套框架，用来量化算法解决不同问题所需要的时间，而且是在一种抽象的数学层面上进行的，从而避开了计算机硬件的一切具体细节。
他们很快意识到，在那些可能出现在实际应用中的问题之间，存在着重要的质的差异，比如在网络中规划路线和对整数进行因数分解。从原则上说，这些问题都可以用算法解决。然而，只有其中一些问题存在巧妙的算法，可以迅速给出答案；对于另一些问题，已知的算法却慢得令人痛苦。为了追究这些差异究竟源自何处，人们由此开创了计算复杂性理论（computational complexity theory）。这是理论计算机科学的一个子领域，研究不同问题所固有的难度，同时也构成了现代加密方案的理论基础。
“数学问题具有一种基本结构，正是这种结构使它们在性质上变得更容易或更困难，”圣菲研究所理论计算机科学家克里斯托弗·摩尔（Cristopher Moore，在新标签页打开）说。“这与你的计算机究竟有多快无关，也与你究竟有多聪明无关。”
如果说数学在某种意义上是现实的语言，那么描绘出这种隐藏结构，就会让人产生一种“仿佛正在发现宇宙定律”的感觉。几年前，我为了写一篇关于复杂性理论中最著名开放问题的烧脑文章，采访了加拿大西蒙弗雷泽大学的复杂性理论研究者瓦伦丁·卡巴涅茨（Valentine Kabanets），这就是他当时的说法。
复杂性理论后来的发展，又指向了一些看起来与“计算”更加没有关系的方向。古尔举了一个例子：20 世纪 80 年代和 90 年代，人们从复杂性理论中发展出了关于数学证明的新观念。理论计算机科学家通过把“证明”重新设想为一种交互式过程，发现我们有可能证明某个命题是真的，却完全不泄露它为什么是真的；他们还发现，对某些证明，只检查极少数几个很小的片段，就有可能验证整个证明是否正确。
“我们突然提出了一整类全新的问题，”古尔说。“我们所谈论的东西远远超出了计算本身。”
在我看来，把这些事情合在一起，就形成了一幅极具说服力的图景：一种没有计算机的计算机科学。 “这里有一些非常基础的问题，几百年前的人其实就完全可以提出来，”得克萨斯大学奥斯汀分校的理论计算机科学家、同时也是 Quanta 顾问委员会成员的斯科特·阿伦森（Scott Aaronson）说。“只不过，那时候没有人想到要问这些问题。”
当然，这马上又引出了另一个问题——为什么没有？
至少有一个人确实想到过要问这些基础问题。19 世纪的博学家查尔斯·巴贝奇（Charles Babbage）构想过一种通用计算机器，并把它称为“分析机”（Analytical Engine）。他曾在自传中推测，这种新机器将要求人们为它发展出一套与之配套的新算法理论。他写道：“每当人们试图借助它获得某个结果时，就会产生这样一个问题——机器究竟应当采取怎样的计算过程，才能在最短时间内得到这些结果？”
巴贝奇最终没有完成他的分析机，而且我们也不清楚，他当初究竟打算怎样回答这个重要问题。也许他设想，机器设计上的具体技术细节会导致某些计算方法比另一些方法更快；没有任何证据表明，他曾预见到后来复杂性理论研究者发现的那种丰富数学结构。
但在我看来，这恰恰就是关键所在。复杂性理论的核心问题——为什么某些问题似乎不存在快速算法——乍看之下，也许并不像一个多么深刻的问题。只有当你真正开始探索它时，它的深度才会逐渐显现出来——而直到 20 世纪 60 年代，研究人员开始真正摆弄现实中的计算机之后，这个问题才显得值得深入研究。
我认为，这最终正是那种淡化计算机作用的计算机科学图景中所遗漏的东西：从历史记录来看，深刻的理论问题往往与怎样制造出更好的机器这一类实践问题纠缠在一起。
东芬兰大学计算机科学家、一本讨论这个领域学科身份的著作的作者马蒂·泰德雷（Matti Tedre），并不喜欢人们通常理解的那句戴克斯特拉名言。不过即使如此，他认为计算机科学与天文学的那个比较，在另一层意义上或许仍然是恰当的。
“[戴克斯特拉]完全是对的；只不过，他错在低估了望远镜对于天文学的重要性，”泰德雷说。“如果没有望远镜，我们对宇宙根本不会知道任何东西。”
超出计算机科学这个领域本身，这段历史也能让我们重新思考科学进步通常是怎样发生的。一种常见的看法认为，纯科学中的突破会推动技术进步：比如量子物理最终带来了晶体管，相对论则使 GPS 成为可能。计算机科学的历史提示我们，深刻理论与现实实践之间存在着一种更加微妙的相互作用，而这种关系在其他学科中同样可以找到对应。阿伦森举出了热力学第二定律作为例子。这条定律说，熵——一种对无序程度的度量——会随着时间推移而趋于增加。
“这也许是关于整个宇宙如何演化，你所能说出的最基本的事情之一，”他说。“然而，在人们开始制造蒸汽机之前，却从来没有人想到过这件事。”
或者，正如麻省理工学院的复杂性理论研究者瑞安·威廉姆斯（Ryan Williams）所说：“实践中足够有趣的问题，会孕育出伟大的理论问题。”