|||
在2016年11月5-6日召开的中国逻辑学会第十次全国代表大会(http://www.cnlogic.net/show.php?catid=1&id=323)上,我们宣读了论文“不确定性问题(NP)研究中的层次与中国传统逻辑”,此论文阐述了我们关于千禧年难题“P versus NP”的研究工作,是对我们的NP理论工作的全面总结。
******
不确定性问题(NP)研究中的层次与中国传统逻辑
周剑铭 柳渝
摘要:计算机和人工智能研究的一个最基本也是最困难的问题,就是算法与判断的基本性质及其关系。确定性问题(P)与可计算性概念是等价的,用术语表达就是P问题=P判定;但不确定性问题(NP)不能由可计算性定义,不确定性问题与确定性问题在判断的性质上完全不同,由于对这两个不同层次的问题在概念上的混淆和表达上的混乱,造成了计算机理论中一系列基本问题的困扰。借助于中国传统逻辑中的经典案例,我们把逻辑判断放在集合论的视野中进行分析,区分了P与NP的基本关系,把层次性引入到算法理论、逻辑学和一般认知领域中。中国传统逻辑可以给现代数理逻辑涉及自身的最困难的问题带来洞察的思想。
Hierarchy in NP(Nondeterministic Problem) Research and Chinese Traditional Logic
Abstract: One of the basic and difficult problems in computer science and artificial intelligence is the nature of human judgement and that of machine decision as well as their relation. The deterministic problem (P) is consistent with the notion of computability, which is expressedby the term P-problem = P-decision. However, the nondeterministic problem (NP) can’t be defined by the computability; the nondeterministic problem and the deterministic problem are totally different in nature of judgment. Confusing these two problems as well as their concept expression at different levels result in perplexes for basic problems in computer theory. With the help of classical cases of Chinese traditional logic, we analyze the logic judgment in the field of set theory, distinguish the basic relation between P and NP, and introduce the hierarchy into algorithm theory, logic and general cognition field. Chinese traditional logic would bring insight into the most difficult problems of modern mathematical logic involving itself.
目录:
一、算法与“判定问题”
二、算法与确定性问题
三、不确定性问题
四、不确定性的消失和NP理论
五、“白马非马”
六、判断的层次
七、大象无形
“P versus NP”于2000年被美国克莱数学研究所指定为七个千禧年难题之一(可参见《紐約客》科普文章“P versus NP”[15]),此问题远远超出了引出这个问题的计算机理论领域,涉及到数学、数理逻辑、人工智能乃至哲学中的基本问题,所以Hemaspaandra在介绍Gasarch于2012年进行的第二次“P versus NP”调查时说[9] :我希望在遥远的未来,当人们读到这四篇文章,可以帮助他们了解,在“P versus NP”还没得到解决的黑暗年代里人们的思想状态(I hope that people in the distant future will look at these fourarticles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet beenresolved)。
在当前的计算机理论中,P(Polynomial time,多项式时间)指计算机在多项式时间可求解的问题,具有可计算性本质;NP(Nondeterministic Polynomial time,不确定性多项式时间)[10]用来定义与确定性问题对立的不确定性问题,我们认为NP的流行定义是对可计算性(确定性)与不确定性关系的误解,与此相关的理论观点及陈述不仅造成了在这个领域中工作者的普遍困扰,也是与此有关的逻辑、人工智能等领域隐含的困难的一个基本原因。
我们的NP(Nondeterministic Problem,不确定性问题)理论[8],基于可计算性理论的基石,揭示了这些理论领域中“不确定性的消失”的现象,借助于中国传统逻辑中的经典案例,把逻辑判断放在集合论的视野中,理清“确定性”与“不确定性”,P与NP的性质和层次上的缠绕关系,在这个基础上进一步深入分析了算法与逻辑的层次性质以及逻辑判断的基本性质和内在层次,为相关领域的基本问题理论的研究提供一个更广阔的视野。
一、算法与“判定问题”
算法(algorithm)是一个古老的概念,是人类文明的经验和知识中原初的基本部份,今天屈指数数的儿童和背九九表的小学生,都是人类基本文明在个人早期成长中的返祖,计算机的基本“算法”知识也是今天中学或大学教育中的必修课程。直觉地说,算法就是计算,按照严格的规则一步一步进行“计算”,比如欧几里德算法就是分解为基本的可执行的操作步骤,每步操作都有确定的后继操作,因此算法常被直觉地认为就是“机械步骤”。
在数学基本理论中,算法以递归函数的形式得到详细的研究,递归函数是可计算的,但这个函数的“可计算性(computability)”与直觉的“算法”概念之间,隐含有数学家称之为“能行可计算性(effectively calculability)”的一种性质。calculability源自拉丁语 calculus,指用于计数的小石子,因此calculability具有比computability更具体的操作性质,effectively calculability 译作“能行可计算性”,这个中文的“能行性”比英文的“effectively”更能表达“算法”这个概念中所隐含的机械操作性质。“能行性”表达了一种普遍性的解决问题的过程性能力,对这种过程性能力的考察被数学家隐含地表达出来,就是著名的希尔伯特第十问题[2](Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers)。这个问题实际上包含了两个更一般性的内容:一、是否所有的数学问题都存在一般性的得到答案的算法?这实质是一种对问题的难度与算法的能力之间对应性的一种普遍性判断;二、算法的能行性如何体现?图灵以论文《论可计算数及其在判定问题上的应用》( On Computable Numbers, with an Application to the Entscheidungsproblem)[1]回答了这两个问题,前者就是“‘判定问题’不可判定”,后者就是著名的“图灵机”。对图灵的工作可以简要地说,图灵首先构造了一般算法的机器模型,回答了什么是算法的能行性;在这个基础上,图灵的工作表明构造能计算所有数学函数的图灵机是不可能的。希尔伯特第十问题和图灵的解决通称“判定问题”(Entscheidungsproblem),它不仅是数学和逻辑学中的基本问题,而且具有更深刻的内容和更广泛的基础。
算法与逻辑一直是现代计算机理论和技术的不可分割、分离的根基,在系统构架上是非常分明的,比如大家非常熟悉的软件和硬件,但这两者的关系在理论上却一直处于纠绕中,硬件和软件在一定的程度上是可以互相替代的,这种缠绕实际上来自人们对“判断”这个具有人类智能意义概念的理解和分析,因此正在成为人工智能理论和人类大脑科学研究中最具基本性的问题,作为它的哲学意义,见已经开始成为“智能哲学”的主要内容。
二、算法与确定性问题
图灵的工作表明,一类数学问题可以通过确定性的方法得到确定的解答,即问题与相应的算法这两个方面具有某种同一性,这种同一性展开来说,就是问题的困难程度与解决问题的方法是相适应的,或者说,算法的能力与问题的难度是相适应的。这种对应性基于两者都具有确定性的本质,一方面,一个具有确定性的问题一定有确定性的答案;另一方面,这个确定性的答案可以通过确定性的机械步骤得到,图灵机就是这种机械步骤过程的机器化模型。这种“确定性”的性质或关系在理论上是以“多项式时间”(Polynomial Time)这个概念精确地表达的,“多项式”(polynomial)具有“线性”性质,这是相对“指数”(exponential)这种“非线性”性质来说的,因此“多项式时间”实际上就代表了一般性的线性性质。
“多项式时间”用来表达算法或机器的能力与问题的困难程度是线性相适应的,即问题的规模增长与机器的能力之间是线性关系,这种性质保证了机器对要解决的问题能提供确定性的答案,这实际上也就是“算法”这个概念作为“能行可计算性”本质的机器化表达,因此,(能行可计算性)算法与图灵机是等价的,这就是“丘奇-图灵论题”所表达的意义。
因此“多项式时间”并没有具体时间的意义,不是指计算机求解问题的时、空规模,而是指问题的规模和机器的能力之间的比较性质,即指问题的困难程度与机器的能力在增长性质上的对等性,这种对等性是由两者都是线性性质保证的:一方面,算法的确定性和解的确定性具有等价性;另一方面,具有确定性答案的问题是由能得到确定性的答案的算法定义的——这就是NP理论中基于“可计算性理论”的(能行可计算性)“算法”定义的“确定性”概念。
三、不确定性问题
很明显,“不确定性问题”是与“确定性问题”对应对立的,但与“确定性问题”完全不同,对“不确定性问题”的认识和定义充满了不确定性。
“可计算性”这个概念是由算法定义的,或者说它们是同义的,但作为算法的“可计算性”的这种一般“能力”性质首先受到数学家的质疑,这就是由著名的希尔伯特第十问题所揭示的,希尔伯特第十问题大体上就是要求对存不存在能解决所有的数学问题的算法这样一个问题的判定,这个问题实际上包含了很多的层次,所以具有远超过这个问题的提出所具有广泛性和深刻性的意义。
图灵对希尔伯特第十问题并没有以Yes或No回答,就是说图灵并没有对希尔伯特第十问题提出一种一般性的判定方法,而是否定了一般性的判定方法的存在——回答No也就是一种确定性的判断!图灵是以拒绝式的方式回答了希尔伯特第十问题,即著名的“‘判定问题’不可判定”,就是说“‘判定问题’不可判定”这个回答不是“存在(Yes)或不存在(No)的一个‘判定’”——存在(Yes)或不存在(No)都是对希尔伯特第十问题的一个确定性的回答,图灵却是拒绝——对希尔伯特第十问题“无法判定”,就是说图灵不是回答了希尔伯特所提出的第十问题的内容,而是拒绝了希尔伯特第十问题本身,即是对“判定‘判定问题’”这个更高层次否定。用这种层次分别上理解,可以明显地看出,“‘判定问题’不可判定”不是由机器产生的确定性的回答,而是图灵的工作所得到判断,是基于人的认知能力产生的判断。
我们可以用不同的术语区别地表达,希尔伯特第十问题的内容的是“判定”问题(Decision Problem),希尔伯特第十问题本身是“判断”问题(Judgment Problem)。图灵对希尔伯特第十问题拒绝式的回答包含了“希尔伯特第十问题”所隐含的更丰富、更深刻的内容和价值,因此统称“判定问题”(Entscheidungsproblem)。
由于希尔伯特第十问题隐含了多个层次,所以希尔伯特第十问题和图灵的解答常常被误解并被进一步误导,由此产生很多的困惑并带来新的困难问题,其中最主要的一个就是所谓的“不可计算性”,表面看,“确定性”与“不确定性”是对应对立的,所以“可计算性”与“不可计算性”的对应对立就很自然,但这里面存在的层次上的缠绕所带来的误解和误导却是难以克服的。从对图灵工作的研究中可以看到,“可计算性”或“能行可计算性”这个概念对应的是“判定问题”而不是“不可计算性”,“不可计算性”相对应的倒是后来流行的“停机问题”(Halting Problem)(大体就是“不能停机的问题”),我们已经分析过了,这种误解的严重后果导致对“可计算性”这个概念的损害[16][17]。
更广泛因而更严重的是对“不确定性问题”的误解,实际上造成了在理论上的认知错误,我们深入地研究了计算机理论中有关NP问题和NP完全性问题的来龙去脉,基于可计算性理论和对希尔伯特第十问题的研究以及对图灵的原论文解读,我们认为“不可计算性”这个术语在算法定义上不能成立,与“确定性问题(P问题)”对立的是“不确定性问题(NP)”,与“确定性问题(P)”对应的是“多项式时间”或“(可计算性)算法(P算法)”,而与“不确定性问题(NP)”对应的是应用非常广泛的最优近似算法,我们称之为NP算法(NP-algorithm,defined as the optimal approximative algorithm to get the best fit value of NP)。
“‘判定问题’不可判定”与真正的“不确定性问题(NP)”是等价的,即不存在P算法。虽然对“不确定性问题”不存在确定性算法,但人们总可以追求最优近似解(NP算法)。
对图灵工作的解读表明,正与“‘判定问题’不可判定”一样,“不可计算性”不能算法定义(自悖)。这种隐含的意义的误读产生了对图灵工作的另一个广泛的误解,这就是“停机问题(HaltingProblem)”,这里的“停机”与“可计算的”意义相同,“停机问题”是以悖论方式证明的,“‘停机问题’不可判定”这样的悖论方式虽然“证明”了“‘停机问题’不可判定”,但却否定了“可计算性”这个基本概念本身,造成了基本理论和认知上的诸多混乱,流行的NP问题和等价的“不确定性图灵机”(Nondeterministic Turing Machine, NDTM )、“停机问题”等都是对图灵工作的误读产生的,所以真正的NP不是机器的问题,而是人所面对的问题,因此“不确定性问题”的本质是人的问题。
四、不确定性的消失和NP理论
莫里斯·克莱因(Morris Kline)在“数学:确定性的丧失”一书中探讨了以确定性和精确性的内容为骄傲的数学发展过程中面临的自身的危机,伊利亚·普利高津(Llya Prigogine)的“确定性的终结——时间混沌与新自然法则”,费曼(Richard Phillips Feynman)的“科学的不确定性”等,都在一般科学理论中提出了“确定性”本身的问题,反映了现代人对知识和人类认知的全面反省,但另一方面,在代表现代科学技术的计算机理论领域中却存在着一种更为隐含和普遍性的实际困惑,就是我们称之为“不确定性的消失”的严重问题[14]。
在算法和计算机理论中,确定性的问题就是有确定性算法解决的问题,但是确定性问题在我们所面对的事物中只是相对少数,而相对的不确定性问题一直是人类认知和知识领域中隐含得很深的一种困惑,计算机强大的解决问题的能力给人们带来了一种观念上的错觉:(所有的)不确定性问题总是可以确定性地解决的,用术语来说,就是P=NP,或者称之为“NP完全性”(NP-completeness),而且这种观点在理论上有系统性的表述并被普遍性地接受,但即使这样,人们并不能排除“不确定性问题”与“确定性问题”在本质上完全不同的直觉,即P≠NP,这两种观点的对立就是“P versus NP”这样一个“世纪难题”。
我们认为,不确定性问题(Nondeterministic Problem, NP)的定义是这类问题不存在确定性算法。在大量的计算机求解的实践中,人们会有“不确定性问题总是可以由计算机解决的”这样的印象,但实际上人们总是事先约定或隐含地约定了将不确定性问题转化为最优近似求解的问题(也就是我们定义的NP算法,NP-algorithm),而不是说,通过计算机求解不确定性问题的不确定性本质消失了。“不确定性问题理论(NP理论)”研究通过揭示流行的NP问题类和等价的非确定型图灵机(NDTM)等概念中所隐含的“不确定性的消失”问题,以及对“不确定性”是如何从“不确定性问题”中消失的研究,揭示了P与NP的真正关系。
与“确定性问题”由确定性算法(P算法)定义这种等价性不同,“不确定性问题”的本质是判断问题,而且不是所谓的“Yes or No的问题”,前文已指出Yes或No都是确定性的判定,“不确定性问题”是指“能否判定:对一切问题都能回答Yes or No”,正如我们对图灵工作的解读,这个问题是不可判定的,所以NP的真正定义是与“判定问题”(Entscheidungsproblem)等价的。
对不确定性问题的求解实际是“判断如何成为算法”的问题,正如大量实际问题的算法解决,这就是在事先约定对不确定性问题求解可以接受的條件下,将不确定性问题转变为最优近似求解问题。在这个前提下,已经发明和成功地应用的各种最优近似求解的算法,就是“如何判定成为算法”的问题。“判断如何成为算法”与“如何判定成为算法”是对不确定性问题最优近似求解普遍方法,是本质的人、机关系。判断与判定对人和对机器具有不同的意义和性质,具有复杂纠缠的相互关系,这是由人和机器具有不同的本质决定的。“P vs. NP”就是这种缠绕复杂性的集中表现,我们认为:“P≠NP, because they are disparate”。研究这两类问题的性质,特别是这两类问题的关系,就成为NP理论的主要内容。
五、“白马非马”
我们用中国传统逻辑的经典“白马非马”解析了流行的NP问题的两个定义中所隐含的层次上的混乱和对“停机问题”所存在问题的分析,理清了逻辑学和算法理论中一直存在两大困扰(NDTM 和“停机问题”),这些问题仅仅在算法理论或逻辑学中是无法解决的,因为与人的认知紧密相关,但又无法在一般的认知理论中解决。图灵工作的启示是把算法放在逻辑层次解决,因此把逻辑放在集合论层次研究,能够得到一种高层次的解决视角。
逻辑学是西方思想的基石,逻辑学给中国传统学术带来的几乎是全新的视野,中国传统学术理论中只留下很少的与逻辑学有关的内容,但中国传统学术思想的“鲁棒性”(Robust)是无容置疑的,借助一个中国传统逻辑的经典案例“白马非马”,我们完全解析了算法与逻辑缠绕的困难。
从现代集合论的观点看,“马”与“白马”是集合与子集合的关系,“马”(“形”或“象”)是马类不同于牛、羊等类的本质认知,“白马”则是在“马”这个大类中不同颜色马的子类。普通人(案例中的城门守兵)具有白马属于马类的常识认知而不自觉,所以认定“白马是马”(以枚举替代判断),智者公孙龙则从逻辑的严格上认为“马”与“白马”是不同的层次,坚持“白马非马”,以现代集合论的观点理解,“白马非马”具有逻辑层次上的不同。因此我们可以重新阐释“白马非马”。
《公孙龙·白马论》原文摘录:
“白马非马”,可乎?
曰:可。
曰:何哉?
曰:马者,所以命形也;白者所以命色也。命色者非命形也。故曰:“白马非马”。
曰:有白马不可谓无马也。不可谓无马者,非马也?有白马为有马,白之,非马何也?
曰:求马,黄、黑马皆可致;求白马,黄、黑马不可致。使白马乃马也,是所求一也。所求一者,白者不异马也。所求不异,如黄、黑马有可有不可,何也?
可与不可,其相非,明。故黄、黑马一也,而可以应有马,而不可以应有白马,是白马之非马,审矣!
解读:
反方:“白马非马”,可以这样说吗?
正方:可以。
反方:为什么?
正方:“马”,指称形状;“白”,指称颜色。颜色不同于形状,所以说:“白马非马”。
反方:既然说有白马,就不能说“没有马”。既然不能说“没有马”(承认事实上有马),怎么还说“非马”(说“没有马”)呢?(这就是“说”与“事实”相违背。)有白马就是有马,只是白色的马而已,为什么说“非马”呢?
正方:如果是找“马”,黄马、黑马都可以;但如果是找“白马”,黄马、黑马就不可以了。若说“白马乃马”,是着眼于它们具有同一性本质,本质相同,白马与马就没有什么区别了。既然在“马”的本质上没有区别,为什么现在又有黄马、黑马对应于“马”的不同分别呢?这里的对应与不对应,是针对不同的层次(相)而说的,(马与色马)层次的不同是很明确的。所以,黄马、黑马具有马的共同本质,符合“马”的个大概念层次,但不符合“白马”(色马)这个二级概念,故白马与马层次不同,现在可以分析很清楚了!
在这段精彩的对话中,公孙龙阐释了“形状”(“象”)与“颜色”二个层次的不同:当用“形状”(“象”)作为判断标准时,是为了在一群混杂着别的动物(比如牛羊等)中找“马”,所以“马”的定义只关心“形状”(“象”),并不关心诸如“颜色”等较具体的属性,也就是说,马这个大类中包含了各种不同的颜色的马(“白马”是马类中的一类),在这种情况下,黄马、黑马都是所找的对象。但是当用“颜色”作为判断标准,是为了在马类中找比如说颜色为白色的“白马”子类,那么黄马、黑马就不是所找的对象了。
流行的计算机理论中,所谓的NP问题类在表达上有两种定义方式(“求解”和“验证”),但本质上都是以“非确定型图灵机”(NDTM)定义的,我们分析了NDTM实质是TM(即我们所说的“不确定性的消失”)。流行的NP问题类和NDTM是P和NP的层次混淆的产物,这不同于一般的概念外延或内涵上的混淆,所以造成非常缠绕的认知上的困扰,NP问题类的两个流行定义在认知层次上已经暗含了NP=P,致“P versus NP”成为世纪难题(见博文[14]:NP二个流行定义与“白马非马”)。
“停机问题”(Halting Problem)是计算机理论中流行的对“判定问题”(Entscheidungsproblem)的替代,在图灵的相关概念中,并没有“停机”这个术语,因为图灵机是一般意义上的算法模型,图灵只关心机器具有可计算性的本质,并不关心具体的计算机的时空能力,但从常识上说,“停机”就意味着得到确定性的答案,这就使“停机”实际上替代了严格的“可计算性”概念,从而使“停机问题”作为悖论形式隐含了对“可计算性”这个根本性概念的否定。“NP问题类”和“NP完全问题”就是由这些算法和逻辑层次上的误导产生的。
六、判断的层次
从现代集合论的观点看,“白马非马”是合理的,“白马非马”不是悖论,“白马非马”是中国传统逻辑提出的判断层次上的问题,揭示了“判断”具有的自身的层次性质,这种层次性质决定于人在判断中的作用或地位。
判断的层次可以用“判断(judgement)”与“判定(decision)”两个不同的术语分别(不在此论域时可以不加分别),判断是人的智能,判定则是判断的工具化,人的日常行为大部份是无意识的工具性行为,这种工具化可以节约人最宝贵的智能,是人类生存的高级进化方式。在日常环境中,人的行为大部份是不自觉,人的无意识行为不需要判断,“习以为常”,“不假思索”,但这只是判断在人的身上工具化了,在这种情况下,判断的对象和人作为判定的工具都是确定的,这也是人类日常生活的基要保证,“白马非马”案例中的卫兵就是以枚举代替判断,这是人的机器化行为,就是说人只是作为算法机器在使用自己,这种认识来源已久,笛卡儿(Decarte, 1596 -1650)、拉美特里(La Mettrie,,1709—1751)就说人是机器,以同在的专业术语说,就是P算法与P判定的同一。
但对于不确定性问题来说,首先就需要正确认识不确定性问题(NP)与确定性算法(P)之间的关系,这正是希尔伯特第十问题和图灵解决的真正价值,图灵正是通过构造一般算法的机器模型而得到这种不可能的判定的,“‘判定问题’不可判定”这个结论是图灵的判断而不是机器的判定,——这是理解“判定问题”(Entscheidungsproblem)的关键,但对这点的误读已经造成了一系列严重的后果,主要原因就是混淆了人的判断与算法判定的层次关系。
判断的性质和判断的内在层次不仅是认知问题,更有关人的认知的自身性质,对它们的性质的混淆和表达上的混乱不仅已经造成了计算机基本理论中的困惑,而且越来越成为与计算机理论紧密相关的人工智能、网络及并行性等基本问题的理解和深入研究上障碍,形式逻辑、数理逻辑、集合论和中国传统逻辑的互补性研究,是打开人文和科学技术研究新领域的必要和挑战。
七、大象无形
内容与形式、语义与语法、分析与综合、经验与理性……,一直是西方学术思想和理论最基本的体系框架,这一方面给西方学术理论带来了庞大、复杂的理论体系和极丰富的内容,但这种体系框架自身的分布性和分裂也是这种体系框架无法克服的致命弱点,因此一次又一次地给各种学术体系带来难以克服的危机,对危机的克服一方面带来了思想范式和理论的创新与发展,但最终仍以人自身不可克服的困惑和不安而成为西方文化最深刻的阴影。
中国传统逻辑虽然没有产生自己专业化的理论体系,但正是由于它植根于日常生活和自然语言之中,所以以内在的深刻性和隐喻方式与中国传统文化共体存在,成为中国传统文化的一种特质。
日常语言与逻辑形式语言的不同和对这两者不同的认识现在已成为了一种常识,西方的知识系统特别地发展了形式化的方法体系,这是近代以来科学技术的客观性和确定性的基础。在中国语言环境中,中国传统逻辑重视判断的主体意识,比如“白马非马”就突出了人的判断在逻辑中的主动地位,所以中国传统逻辑不分离于日常语言,也没有产生专门化的逻辑学,而是存在于中国文化本质中,中国传统逻辑始终深入在中国思想与中国思维方式中,以一种完全不同于西方逻辑学发展的道路深深植根于中国传统文化之中。中国文化典籍中的传统逻辑以经典案例形式传承不绝,中国传统逻辑与中国传统文化的关系也就是中国文化本质的表现,用中国文化中最具传统特色的一句哲学语言来表达,就是“大象无形”。
以集合论的观点看,“白马非马”建立在“形”、“色”相异基础上,以现代语言来说,就是本质与形式的区别,但这种区别不是建立在形式化的基础上。“白马非马”中“形”、“色”相异,但不是对立,所以不会发展为悖论,也不是诡辩,因此与“质”、“量”等辩证对立的范畴不同,“白马非马”是逻辑的层次的不同,这是现代集合论的基本思想。在西方现代逻辑理论中,如何打通集合论和逻辑学,是一个自近代开始而远未能有效展开的艰难课题,实际上,集合论与逻辑学的鸿沟就是现代谓词逻辑中最困难的部份。在数理逻辑中,集合论与逻辑学是并例分别的,它们是数理逻辑四大构成部份中的具有更基本意义二个理论体系,但是集合论自康托尔之后已经停滞在“连续统假设”前无法前进,而谓词逻辑实际上已经以“现代逻辑”的不同发展方向而处于分裂分化之中。
中国传统逻辑与中国文化的特质是一致的,“大象无形”背后是清晰的层次思想,这正是西方思想和现代逻辑遍历不得的,中国传统逻辑吸收西方逻辑学丰富成果而得到清晰的体系化,中国传统逻辑可以给现代数理逻辑涉及自身的最困难的问题带来洞察的思想。
参考资料:
[1] A. M. Turing: On ComputabilityNumbers, with an Application to the Entscheidungsproblem. http://www.abelard.org/turpap2/tp2-ie.asp .
[2] David Hilbert: MathematicalProblems, http://aleph0.clarku.edu/~djoyce/hilbert/problems.html
[3] Martin D. Davis and Elaine J.Weyuker, Computability, Complexity, and Languages. Academic Pries, Inc. 1983.
[4] Michael Sipser. Introduction tothe Theory of Computation. PWS Publishing company.
[5] Michael R. Garey & David S.Johnson: Computers and Intractability, Bell Telephone Laboratories, Incorporated,1979.
[6] Stephen A. Cook, The Complexity ofTheorem-Proving Procedures, 1971. http://4mhz.de/download.php?file=Cook1971_A4.pdf.
[7] Stephen A. Cook, The P versus NPproblem, 2000. http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf
[8] Zhou, Jian-Ming: Computability vs.Nondeterministic and P vs. NP, http://arxiv.org/abs/1305.4029 .
[9] Yu Li, What is NP? - Interpretation of a Chineseparadox white horse is not horse, http://arxiv.org/abs/1501.01906
[10] JianMing ZHOU,Yu LI, Whatis Cook’s theorem? http://arxiv.org/abs/1501.01910
[11] 周剑铭:算法理论与中国理性,网文。
[12] 周剑铭:“智能”哲学——人与人工智能,网文。
[13] 周剑铭,柳渝:机器与“学习”——寻找人工智能的幽灵,网文。
[14] 柳渝:不确定性的困惑与NP理论,http://blog.sciencenet.cn/u/liuyu2205。
[15] 最深刻的数学问题http://blog.sciencenet.cn/blog-2322490-995211.html(译文)。 The New Yorker, A Most Profound Math Problem http://www.newyorker.com/tech/elements/a-most-profound-math-problem(原文)
[16] “不停机”的circle-free——图灵1936年论文解读(3)http://blog.sciencenet.cn/blog-2322490-993665.html
[17] NP理论的基本概念(2):“判定问题”与“停机问题”http://blog.sciencenet.cn/blog-2322490-991454.html
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 11:12
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社