这篇短文既可以看作是研读图灵著作工作( 图灵论著专研与精译工作群告白书 )的基本思想,也可以看作是对我们NP理论和智能哲学的思想来源的一个解释。 ****** 解读图灵:层次关系中的一致性 对图灵的著作研读,有三个基本层次,第一是图灵说了什么,第二是图灵是如何说的,第三是图灵为何这样说。第一层次主要就是对图灵的文本的整理和直接阅读,第二层次可以较精确地体现在对图灵文章的翻译上,第三层次就是对图灵的思想、思路的追踪,理解图灵的态度和认知中的秘密。 在对图灵的研读中,人们大多为图灵论述的内容的跨界精深所吸引,往往忽视了他作为一个技术专家的特别身份。实际上,图灵的立场和态度始终是一致的,他始终是作为功能机器的创造者进行思考和设计,这在他作为密码专家和计算机专家的工作的一致性上得到明显的表现。 图灵的这种态度和立场在他的文章中是深层和全面地体现出来的,而他深刻的思想总是隐含在他复杂的内容表述之中,图灵并不像理论家一样,在术语的使用和文本表达上十分讲究,他只在他的工作对象和目的上保持严格的一致。图灵的文风显得有些捉模不定,并不是由于文本晦涩而是由于读者难于跟随他的思路的多层次性,难于把握他不多但多方面的研究工作后面的全局性。他思想的深刻性在于他始终将他的对象和目标放在不同的层次关系中,读者难于理解这些交织在不同的层次中的逻辑一致性,所以对图灵论文的阅读并不容易,图灵工作的意义和价值远没得到充分的解读。 基于图灵思想的丰富和复杂的层次性,我们在专研图灵1936年论文中( 图灵1936年论文解读(1):可计算性 ),就把难于理解的三个主要概念Circle、 Circle-Free和 C-machine三个术语放在不同的层次上而不是作为相对概念进行分析,结合图灵同时期的数学家,计算机理论家的工作,我们认为,Circle来源于(不同于计算机的)自动机,而Circle-Free就是能行可计算意义的计算,Circle-Free表明计算机高于自动机的层次性,结合乔姆斯基的语言分级理论,就可以看到这种分层次的思想在逻辑上是严格一致的。图灵的1936年论文主要论述如何去构造Circle-Free,而对C-machine只是简单地说:For some purpose we might use machines (choice machines or C-manhines ) whose motion is only partially determined by the configuration,就是说,这种C-machine需要机器“内态”之外的控制性界入,虽然图灵没有进一步指明C-machine是什么,但我们可以在上述层次的观念上理解图灵的直觉,这种机器与人的因素密切相关,实际上,这也就是指我们在NP理论中所说的NP-algorithm,即有人的因素界入的“启发式”算法,这种理解成为了我们NP理论的主要内容之一。图灵的思想进一步给予我们理解今天的人工智能区别于计算机的灵感,以及机器与人工智能在不同层次上的一致性:自动机(Circle)— 计算机(Circle-Free)— NP-algorithm(C-machine)—人工智能(Agent)。 基于对图灵思想这种深层次和全面性的解读,对1936年论文中最困难的问题论述的理解也就有了清晰的思路。今天人们一般将Circle理解为计算机进入“死循环”,并不全错,但无法以此理解图灵的Circle-Free的真正意义和价值,也无法追随图灵的思路去读通论文中一些最困难的表达,特别是图灵的构造性思想与机械步骤的所表现的算法实时性的重要意义,以及1936年论文对希尔伯特第十问题的“拒绝式”解决(Entscheidungsproblem)在数学和逻辑学中的地位等等,没有对图灵这些最基本思想的理解,图灵的工作和图灵机就永远蒙着一层神秘的面纱。这里特别指出,对图灵的误读正是造成今天P vs. NP困境的根源。 在图灵的思想中,人始终是机器的发明者或发现者,无论是作为密码专家还是作为计算机专家,图灵始终考虑的是如何去设计一种功能机器,或者说,人如何去构造一种机器具有某种功能。因此图灵与计算机专家或程序专家不同,他并不关注机器或程序如何运行或运行得更好(前提是机器是可以运行的),图灵关注的是机器如何构造以实现算法的一般性质(前提是我们还没有这样的机器或尚不知道机器与算法的等价性)。——这正如我们所关注的“不确定性问题”(NP)一样,我们不是在承认现有的NP或NDTM的概念的前提下去讨论P vs. NP问题,而是质疑这个问题本身,把问题的困难性归结到问题的前提上,即错误的NP概念,—— 这是我们从图灵的工作中得到的最重要的启示之一。 图灵的工作、他的论著所包含的意义随着时间的推移而变得越来越有价值,但对图灵的论著的阅读和理解远不是全面和深刻的,虽然图灵的工作已经过去了近百年,仍然没有较完整、准确的全部中文译本,对图灵论著的专研和以中文翻译方式理解和重新表达他的思想在今天具有重要的意义和价值,这不是一个人或数个人可以完成的工作,这应当成为所有这个时代的学者的共识。
“P versus NP”是计算机领域中一个平凡又不凡的问题。说“平凡”,是因为此问题缘起于探讨有效求解大量的应用问题,诸如:旅行商问题,图染色问题,作业调度问题等等;说“不凡”,是因为此问题是计算机理论的核心问题,又是Clay Mathematics Institute收录的七个千禧年难题之一,虽然学术界已投入了巨大资金和人力,至今却没有实质性的进展。 Bill Gasarch于2002年和2012年(http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf),对100和152计算机理论前沿的研究者,进行了关于“P versus NP”前途的调查,是对该问题现状的很好解读。Hemaspaandra在介绍2012的调查时,悲观地说: -我希望在遥远的未来,人们读到这四篇文章,可以帮助他们了解,在P versus NP还没得到解决的黑暗年代里人们的思想状态。 ( I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved. ) 我们的“NP理论”工作就是针对此问题的探索,我们认为此问题实际上隐含着一直未被人们重视的认知偏差,以致于成了名副其实的「皇帝的新衣」,我们希望借此工作能引起人们对认知基本问题的重视,以及对中西文化互补性的实践和思考,。。。 文章“什么是NP?- 解读中国哲学悖论“白马非马(What is NP? - Interpretation of a Chinese paradox white horse is not horse)”,就是我们工作的第一阶段的一个总结,希望与感兴趣的同事切磋交流。此外,这里出现的一些观点、术语等,会与流行的有所不同,以后逐步介绍。
1993年,我在法国贡比涅大学(Université de Technologie de Compiègne)完成了计算机博士论文,步入了法国儒尔-凡尔纳大学(Université de Picardie Jules Verne)的教学和研究之路。法国大学的教学和科研体制,一方面,以其注重合作、富于个性的风格,使自己受益匪浅;另一方面,其强调程序性的教学模式,又让自己极不适应,加之语言的障碍,不禁困难重重,由此,却开启了自己重新认识中西方文化、实则认识自己之旅。那么,“NP理论”(这个概念以后再说明)的研究就是这段心路历程的写照。 具体说来,从事“NP理论”的研究,首先缘起于“计算复杂性理论(Computational Complexity Theory)”教学的“奇怪”经验。“计算复杂性理论”是众多的计算机基础课程的一部分,但是这部分的讲授,却令自己困惑不已,因为每次讲完后不久,首先是自己,就把讲授的内容几乎忘得一干二尽,只剩下几个形式化的定义:P,NP,NP-完备性,。。。 于研究,缘起于“启发式算法求解NP-hard问题”的困惑,虽然各种启发式算法层出不穷,呈百花齐放的景象,但却与“计算复杂性理论”隔山隔水,理论与实践严重脱节,自己不禁问为什么?。。。 直觉把自己引向了文化、思维认知,开始了寻师访友,。。。这一路走来,已是二十年!今天来到这里,是想和大家分享这段心路历程,同参共学,。。。