不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

“不确定性问题”(Nondeterministic Problem,NP)与"哥德尔不完全定理“ 精选

已有 3758 次阅读 2020-1-1 05:36 |个人分类:不确定性问题和算法讨论|系统分类:论文交流| 哥德尔不完全定理


“不确定性问题”(Nondeterministic Problem,NP)与“哥德尔不完全定理”

- 周剑铭,柳渝


1931年哥德尔证明:任何无矛盾的公理体系,只要包含初等算术的陈述,则必定存在一个不可判定命题,用这组公理不能判定其真假。


虽然哥德尔不完全定理只是针对包含数论的公理体系而言的,由于人们相信公理形式系统是人类知识的纯粹性与抽象性的精粹(数学和逻辑),所以哥德尔不完全定被看成是知识和人类理性的灾难。完全性这个观念隐含了人类对自己的知识系统的希望或信仰,也是人类对自己的理性能力的最大期望,但这两者之间的一致性被打破了。作为纯粹形式系统自身的纯粹性质可证性完全性与作为人类理性能力的抽象性,即作为人类理性工具的自身的能力与人类的理性能力之间的不一致性被理性工具自己完全揭露,但这种理论的深层性和思想的深刻并未被完全理解,因此哥德尔不完全定理的意义在各种不同层次和深刻性的解读上充满了分歧和论争。


哥德尔第一定理:任意一个包含一阶谓词逻辑与初等数论的形式系统,都存在一个命题,它在这个系统中既不能被证明为真,也不能被证明为否。

哥德尔第二定理:如果系统S含有初等数论,当S无矛盾时,它的无矛盾性不可能在S内证明。


哥德尔第一定理是就公理系统的自身能力而言,揭示公理系统中存在本系统无法证明的命题,就是说,公理系统自身的完全性无矛盾(相容性)不能同时满足。这实际上也就是公理系统的基本工具性能力——可证性或演绎能力在自己的所有对象上的失效。


哥德尔第二定理是个元性质, 公理系统自身的资质无矛盾性相容性不能由它自己证明。


一般情况下由于混含地理解了哥德尔不完全定理的层次性,哥德尔不完全定理广泛地理解为数学和逻辑的形式系统中存在真的但不可判定的命题,在这种表述中,层次的深刻性被这个本身就存在很大争议的术语替代了。这种表达实际上是把数论的混用于逻辑(这也是哥德尔不完全定理包含数论的原因),数学和逻辑的形式系统中存在真的但不可判定的命题实际上就是存在数论上是真的但逻辑上不可判定的命题


如果我们把形式这个术语理解为字母或语言这种符号表达形式,可计算性算法图灵机(模式)就是这样一个数学和逻辑的形式系统。因此在我们看来,存在真的但不可判定的命题这种表达,也可以表达为算法或图灵机中存在不可判定问题,例如停机问题(一般所理解的不可判定问题”undecidable problem是以停机问题方式作证明或解释的,我们认为,这种以悖论方式定义的方法,损害了可计算算法或图灵机的本质,是不可取的。)


我们已经指出,停机问题这种悖论性证明是以牺牲可计算性本身为代价的。因此我们提出与不可判定问题Undecidable Problem)等价的NP定义。我们一方面坚持,算法或机器可判定的问题,也就是算法或机器可计算的问题(P判定即P计算),这样就把经典可计算理论作为基石而替代了对的定义;另一方面,也就是相对于PNP,我们定义,存在着没有算法或机器能进行判定或计算的问题,即不确定性问题Nondeterministic Problem, NP)。这个定义是相对设定的。这样我们的NP定义区别于以往的基于不确定性图灵机NDTM)所定义不确定多项式时间Nondeterministic Polynomial Time),流行定义的NP问题仍是本质上的P问题,但我们的NP是在本质上与P相区别的,即在本质上相对于PNP


在严格的意义上,我们认为NP本质就是图灵对希尔伯特第十问题的解决。希尔伯特第十问题和图灵对希尔伯特第十问题的解决,我们合称为Entscheidungsproblem判断问题”—— “判断的确定性或不确定性,是基于人的立场;判定的确定性Yes or No基于算法或机器)。P既是算法可计算的,也就是算法可判定的,即求解这类问题的算法同时也是对这类问题的可计算性的算法判定(P判定=P计算),在一般意义上也是可判断的。因此,EntscheidungsproblemNP的本质。


在这种理解上,对于P问题,算法与逻辑是一致的,即P问题是算法可以判定的问题,是可以算法判定的存在或不存在可以确定性求解的算法的那一类问题,存在确定性求解的问题的算法也就是对这个问题可以算法求解的算法判定。相对应地,NP则是与P问题这个本质不同的问题,即在对P本质的否定性上的定义,也就是说,NP是不存在可以判定存在算法或机器求解的算法’”的那些问题。


结合Entscheidungsproblem哥德尔不完全定理哥德尔不完全定理与我们的NPNondeterministic Problem)的概念具有内涵的一致性,可以说,我们的NP概念是Entscheidungsproblem哥德尔不完全定理之间特殊等价形式。一方面,我们可以说:存在数论上是真的问题的陈述但无法以数论形式去进行逻辑判断(其真假),或者,存在算法语言表达的问题是不可以算法去判定(它是否是可计算的)。


NP理论看哥德尔不完全定理,可以将哥德尔不完全定理表达为,一个公理系统内不存在可以判定一个语法合适的命题是否是这个系统内的定理的这样一个定理。这个表述与Entscheidungsproblem 具有一致性。


NP的本质是不可判断的,这个定义似乎容忍了可能存在确定算法,但现在没有找到这样一种流行的观念,这种观念错误与P定义是不相容,因为只要你承认可能存在确定性算法,就已经承认了这是P!流行的NP问题的定义都隐含了这种讫题循环定义的错误,无法跳出事先暗中肯定NP=P的旋涡。(——这种陈述中所说的可能存在……这种超出经典逻辑的实在性和图灵机无限长纸带的观念,已经不在经典理论范围内了。)


  包括哥德尔本人在内的理论界对哥德尔不完全定理的意义和地位问题(即哥德尔不完全定理的哲学性质)一直存在难以梳理的论争,实质上这是在把形式系统等价于最基本的语言知识(形式)的本质问题这个层次上的论争,这也就是最古老的哲学问题的延续,从柏拉图的实在论到中世纪的唯名论、唯实论,近现代以来的语言哲学、语法与语义关系,以及当前的人工智能基本问题等的论争的延续,这一切都深刻地与哲学上的潜无穷实无穷的关系相关联。所有这些都是我们的NP理论后面的哲学背景。





http://blog.sciencenet.cn/blog-2322490-1212338.html

上一篇:寻访顾赛芬的故乡瓦雷纳斯(Varennes)
下一篇:写在“世界逻辑日”

7 吕建华 杨正瓴 牛广锋 文端智 黄永义 王安良 张鹰

该博文允许注册用户评论 请点击登录 评论 (7 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-9-30 08:37

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部