编者按：艾伦·图灵预言，“一旦机器的思想方法开始运行，它将很快超越人类羸弱的力量”。身处“数据革命”时代，如何审视机器的本质？它背后的原理又是什么？逻辑为我们提供了怎样的视角？本期“周一谈治学”中，我们将以“哲学+计算机”为切入点，专访“计算复杂性”（数理逻辑学程课程）授课教师，计算机科学技术学院陈翌佳教授，从学科关联、课程探索、修读建议等方面，一同走进数理逻辑的“跨界”之路。

陈翌佳：上海交通大学计算机科学博士（计算机软件与理论方向）、德国弗莱堡大学数学博士（数理逻辑方向）。现任复旦大学计算机科学技术学院教授。主要研究领域为逻辑、计算复杂性和算法图论，特别是参数复杂性和有限模型论。他的结果发表在计算机科学一流国际期刊Journal of the ACM、SIAM Journal on Computing、Information and Computation，一流国际会议LICS、FOCS、ICALP，数理逻辑一流国际期刊The Journal of Symbolic Logic、Annals of Pure and Applied Logic等。陈翌佳教授曾获微软青年教授奖，理论计算机国际会议ICALP’10及图论国际会议WG’17最佳论文奖，四次担任计算机科学中的逻辑研究旗舰国际会议LICS程序委员。

Q1、部分观点认为，计算机帮助人类将思想转为代码，而逻辑完成的就是解码过程。您如何看待逻辑对计算机发展起到的作用？

艾伦·图灵（Alan Turing）被公认为计算机科学的先驱,而他最重要的贡献之一就是创造了图灵机模型。图灵机是第一个以数学方式定义的计算模型，现在被视为计算机科学，特别是理论计算机科学的基石。从历史的角度来看，图灵建立图灵机模型的初衷是解决十九世纪末二十世纪初大数学家大卫.希尔伯特提出的判定问题。这个问题来自逻辑。简单来说，如果我给你一个一阶逻辑写下来的数学命题，是不是有一个程序可以自动告诉你它是否成立。图灵借助他引入的图灵机模型证明了这样的程序是不存在的。

计算机科学早期的发展很多都与逻辑紧密相关，逻辑的很多分支在计算机里也都有其应用。上面提及的判定问题及其变种对早期的算法设计起到了巨大推动作用。此外，证明论和类型理论为程序语言提供了理论基础，阿伦佐.丘奇提出的lambda演算可以视为第一个函数式程序语言。模型论在数据库也有着广泛的应用，一个具体的例子就是数据库查询语言设计，著名的SQL（structured query language）语言本质上就是一阶逻辑，而它的扩充Datalog就是所谓的不动点逻辑。目前计算机科学和工程研究的一个重要前沿邻域-形式化方法-有两个重要技术，定理证明和模型检测，前者源自证明论，后者可以视为模型论的算法化。

Q2、一种观点认为，人工智能的产生离不开数理逻辑，您如何看待这一观点？

还是回到历史的角度来看，图灵的另一个贡献是图灵测试，也就是在什么情况下认为一种机器具备人的智能。换言之，我们能否定义一个严格的标准来证明某个机器达到了人工智能。这个测试具体来说，就是通过一系列问题和对方进行问答，如果相当长时间内，他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个计算机具有同人相当的智力。这是一个外在的检验，它不关心这个机器的内部，不在乎对方是怎么回答这个问题的——这个测试本身不关心内涵，只关心外延。而在这其中我们似乎看不到什么逻辑。但回到人工智能早期，我们会发现，当时运用的大量的方式是基于逻辑的推理方法，而这个就是纯粹的逻辑，试图通过逻辑推理来模拟人的思考过程。70、80年代所研制的“专家系统”，就是试图把知识建立成一个逻辑推理的过程，这就如同看病一样，透过哪些症状结合在一起我们可以判断他得了什么病。

但“专家系统”的发展也面临了一些问题，尤其是在大数据处理上。而现在的自然语言处理和图像识别运用的并不是逻辑推理，而是统计方法，包括前一阵子最火的AlphaGo，它最初的想法是模仿人的神经元，也就是将决策过程转换成一个神经网络，通过神经元的处理来模拟学习过程。但这种基于统计或者说神经网络的方法也有一个很大的问题——没有理论解释。

有个比喻说现在人工智能像炼金术，大家凑数据、调参数，但对于背后的原理、如何运作知之甚少。大概两年前，人们开始研发通过胸透照片自动诊断肺炎的机器学习算法，并乐观地认为这样的算法能很快取代X光医师。但经过一段时间，这样的乐观情绪已经没有了。机器告诉你肺部有问题，却没有一个逻辑的解释过程。我不知道为什么，只知道它应该是“对”的。但在非常精密的领域中应用时，哪怕是10%的错误率，都是绝不能容忍的。尤其是医疗方面，不容许有任何差错。所以基于统计或者神经网络的方法的问题就在于，它是一个黑盒。但想象一下，如果我们能够完全地刻画出一个医生从胸透照片中发现问题的全部推理过程，建立一个完备的知识体系，每一步都能有迹可循的话，机器就可以复现这整个过程，这样人就有把握了。至少我能复查，知道机器所显示的问题是什么原因导致的，而神经网络则无法告知，你甚至也不能理解它的内部是怎样运算出来的。

所以，目前主流的成功的人工智能方法并不是逻辑的方法，但也因此导致了它无法解释的疑难，如果要打破现状，或许我们仍需要呼唤逻辑方法和统计方法结合。因为技术总是会有瓶颈的，而最重要的在于理解。

Q3、本次数理逻辑学程开设了“计算复杂性”，这门课教授的是怎样的内容？又会在何种程度上解读计算机世界的奥秘？

我们会通过写程序来解决问题，但这个程序是有好有坏的。什么叫好？什么叫坏？最重要的标准之一就是“算得快”，也就是越快越好。如何设计“快”的程序？这就是算法要研究的问题。但是，到底有没有最快的算法？或者说最快的算法应该是什么样子？这就是计算复杂性要回答的问题。换言之，它不取决于具体的算法，而是说，我想研究这个问题本身的某些特性，这些特性就决定了我设计的算法最快是有多快。所谓的“计算复杂性”，不是研究具体算法的复杂性，而是问题本身的复杂性。这是一方面。

第二，在现在这个大数据时代，一个突出的问题是“存储”。我们不可能将如此庞大的数据都存储下来，因此需要一个方法尽可能少地占用我的存储空间，这也是复杂性所关心的问题。也就是如何设计一套算法尽可能少占用我的存储空间。这两方面，一个是时间，一个是空间。实际上，“计算复杂性”所要回答的，就是在计算给定问题时，最少需要多少资源（包括时间和空间等因素），它不是指具体计算过程，而是指在所有可能的计算过程中，最好的效率到底是什么，或者说我想证明有些东西不可能在这样的效率中算出来。所以“计算复杂性”这门课也并不是一门代码课，很多时候给出的是数学的想法或者证明。

Q4、您如何看待P vs.NP问题

*P vs.NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”在千禧年大奖难题中收录。

P是指计算机程序在多项式时间（polynomial time）可解的计算问题，而NP是在非确定多项式时间（nondeterministic polynomial time）可解的计算问题。P vs.NP问题问是否每个非确定多项式时间可解的问题也能在（确定）多项式时间可解。P vs.NP问题是现在计算机科学领域最重要的问题，也被公认是数学领域最重要的问题之一。它和黎曼猜想、庞加莱猜想（目前已经解决）并列21世纪七大数学问题。在某种意义上，有了像P vs.NP这样的问题，数学家才承认计算机是一门深刻的科学，而不仅仅是一个工程学科。

举个简单的例子，一张世界地图上相邻国家的着色一定是不一样的。而如果将这些颜色拿掉，只有一张划分边界的空白地图，现在让你只能用三种颜色涂色并且保证相邻国家的颜色不一样，那么有没有一个程序能很快解决这个问题呢？在颜色已经给定的情况下，辨认相邻国家是否颜色不一样的程序是很简单的，这就是P的问题，是一个很容易就可以被验证的问题。但是难点在于，如果不给定颜色，是否程序可以给出答案呢？这就是NP问题。你或许会想到暴力枚举所有可能的着色方案，但是这样枚举的可能性的数量级是相当庞大的，相应的程序可能会跑数年。所以，P vs.NP问题本质上是要回答：如果问题的答案可以很快被判断或者验证，其答案是否也可以很快被计算？实际上这个问题和哲学有密切联系，在某种意义上它想回答创造性是否可以通过机器实现。作为一个普通人，我们能够欣赏米开朗基罗的《大卫》、贝多芬的《英雄》、莫奈的《睡莲》，但我们也知道欣赏这些艺术品的美和有能力创造它们是两回事情。前者可以视为一个P问题，而后者是NP问题。

事实上，P vs.NP问题也与我们的日常生活息息相关。我们每天使用的手机通讯和支付的安全性都建立在P不等于NP的假设之下。一个可能不是非常恰当的比喻，如果P=NP，那就计算机就能很快地猜出任何一个手机密码。

Q5、您如何看待计算机科学和哲学研究的交织？它们面对哪些共同的问题领域？

从我自己来说，读本科的时候对分析哲学很感兴趣。作为一个理工科学生，我希望将思辨过程转变成数学推导。以“奥卡姆剃刀”为例，在计算机科学里可以将其严格数学化，比如PAC（probably approximately correct）learning，它是人工智能里面很重要的一个方法，它能解释“奥卡姆剃刀”为什么在数学上是对的。原来我们只是觉得假设越少越好，但这在某种意义上只是一个信仰或者说是一种美学选择，很难从数学上证明，但PAC learning做到了。从我个人理解来看，计算机科学可以将一些哲学问题具体化，具体到我们可以把它当成一个数学问题来研究。我最早看分析哲学的时候，它的一个想法是试图将哲学消解到用数学严格地分析问题。计算机也可以提供一个新的视角，一个很好的例子就是“奥卡姆剃刀”和“PAC learning”的关系。还有包括之前提到的P/NP问题,所面对的也是创造性是否可以被机械化过程取代。

我自己的一个研究领域是描述复杂性，这个领域能和维特根斯坦有一句名言“语言的边界就是世界的边界”建立起联系。在计算机科学中，我们就可以设计程序语言，这个程序语言设计程序的能力，恰巧是这个语言预先已经框定的东西。我要看更大的世界的话，就要增强语言的能力。这就如同你讲中文看到的就是中文世界的东西；讲英语看到的就是英语世界的东西。随着语言的扩张，你能够看到的东西、在程序中能够运算的东西就会越来越大。语言的界限就是程序能力的界限。

Q6、对修读本学程的同学有哪些建议？

计算机科学这些年来发展很迅速，但其中有很多悬而未决的问题，例如P vs.NP问题以及人工智能领域的诸多问题。从计算机专业学生的角度看，如果只学计算机的课程，纯粹只做一些技术上的问题，就不太会触及更深刻、更本质的问题，从这个角度来说数学问题和哲学思考的注入是有必要的。

而对于“文科”同学来说，最重要的就是“不要害怕”。在我看来数理逻辑是零基础也可以修读的，只是可能很多时候会被上课的内容“吓住”，而忽视了本质的数学结构等内容。我认为文科同学学习数理逻辑能帮助大家建立一个支点，也就是数学化。一旦数学化以后，很多争论是可以避免的。我们先讨论能够接受的公理是什么，当我们接受同样的公理的时候，我们继续讨论，如果不能接受，那我们就知道彼此关于这个世界认识的假说在什么地方是不一样的。进一步如果接受同样的公理，再来看我们是否能接受同一个推理规则。所有的问题都可以一步步推理。如果我们接受的公理是一样的，接受的推理规定是一样的，那么我们在所有的问题上只有一个答案，就可以减少不必要的争论。而计算机里面重要的，就是能否将哲学中的一些问题以计算机科学的方式描述，就比如它至少能够给彼此一个可操作的关于人工智能的定义。

本文采访者：隋艺菲、岳泽民、刘勤