手机网站如何推广,荣耀手机全部型号,杭州企业标志设计,毕业设计用PHP做旅游网站来源#xff1a;柳渝科学网博客1931年哥德尔证明#xff1a;任何无矛盾的公理体系#xff0c;只要包含初等算术的陈述#xff0c;则必定存在一个不可判定命题#xff0c;用这组公理不能判定其真假。虽然哥德尔不完全定理只是针对包含数论的公理体系而言的#xff0c;由于… 来源柳渝科学网博客1931年哥德尔证明任何无矛盾的公理体系只要包含初等算术的陈述则必定存在一个不可判定命题用这组公理不能判定其真假。虽然哥德尔不完全定理只是针对包含数论的公理体系而言的由于人们相信公理形式系统是人类知识的纯粹性与抽象性的精粹数学和逻辑所以哥德尔不完全定理被看成是知识和人类理性的灾难。“完全性”这个观念隐含了人类对自己的知识系统的希望或信仰也是人类对自己的理性能力的最大期望但这两者之间的一致性被打破了。作为纯粹形式系统自身的纯粹性质“可证性”与“完全性”与作为人类理性能力的抽象性即作为人类理性工具的自身的能力与人类的理性能力之间的不一致性被理性工具自己完全揭露但这种理论的深层性和思想的深刻并未被完全理解因此哥德尔不完全定理的意义在各种不同层次和深刻性的解读上充满了分歧和论争。哥德尔第一定理任意一个包含一阶谓词逻辑与初等数论的形式系统都存在一个命题它在这个系统中既不能被证明为真也不能被证明为否。哥德尔第二定理如果系统S含有初等数论当S无矛盾时它的无矛盾性不可能在S内证明。哥德尔第一定理是就公理系统的自身能力而言揭示公理系统中存在本系统无法证明的命题就是说公理系统自身的“完全性”和“无矛盾”相容性不能同时满足。这实际上也就是公理系统的基本工具性能力——可证性或演绎能力在自己的所有对象上的失效。哥德尔第二定理是个元性质 公理系统自身的资质“无矛盾性”或“相容性”不能由它自己证明。一般情况下由于混含地理解了哥德尔不完全定理的层次性哥德尔不完全定理被广泛地理解为数学和逻辑的形式系统中“存在真的但不可判定的命题”在这种表述中层次的深刻性被“真”这个本身就存在很大争议的术语替代了。这种表达实际上是把数论的“真”混用于逻辑“真”这也是哥德尔不完全定理包含数论的原因数学和逻辑的形式系统中“存在真的但不可判定的命题”实际上就是 “存在数论上是真的但逻辑上不可判定的命题”。如果我们把“形式”这个术语理解为字母或“语言”这种符号表达形式“可计算性算法”或“图灵机”模式就是这样一个“数学和逻辑的形式系统”。因此在我们看来“存在真的但不可判定的命题”这种表达也可以表达为“算法或图灵机中存在不可判定问题”例如“停机问题”一般所理解的“不可判定问题”undecidable problem是以“停机问题”方式作证明或解释的我们认为这种以悖论方式定义的方法损害了可计算算法或图灵机的本质是不可取的。我们已经指出“停机问题”这种悖论性证明是以牺牲可计算性本身为代价的。因此我们提出与“不可判定问题”Undecidable Problem等价的NP定义。我们一方面坚持算法或机器可判定的问题也就是算法或机器可计算的问题P判定即P计算这样就把经典可计算理论作为基石而替代了对“真”的定义另一方面也就是相对于P的NP我们定义存在着没有算法或机器能进行判定或计算的问题即“不确定性问题”Nondeterministic Problem, NP。这个定义是相对设定的。这样我们的NP定义区别于以往的基于“不确定性图灵机”NDTM所定义“不确定多项式时间”Nondeterministic Polynomial Time流行定义的NP问题仍是本质上的P问题但我们的NP是在本质上与P相区别的即在本质上相对于P的NP。在严格的意义上我们认为NP本质就是图灵对希尔伯特第十问题的解决。希尔伯特第十问题和图灵对希尔伯特第十问题的解决我们合称为Entscheidungsproblem“判断问题”—— “判断”的确定性或不确定性是基于人的立场“判定”的确定性Yes or No基于算法或机器。P既是算法可计算的也就是算法可判定的即求解这类问题的算法同时也是对这类问题的可计算性的算法判定P判定P计算在一般意义上也是可“判断”的。因此Entscheidungsproblem是NP的本质。在这种理解上对于P问题算法与逻辑是一致的即P问题是算法可以判定的问题是可以算法判定的存在或不存在可以确定性求解的算法的那一类问题存在确定性求解的问题的算法也就是对这个问题可以算法求解的算法判定。相对应地NP则是与P问题这个本质不同的问题即在对P本质的否定性上的定义也就是说NP是不存在“可以判定‘存在算法或机器求解的算法’”的那些问题。结合Entscheidungsproblem和哥德尔不完全定理哥德尔不完全定理与我们的NPNondeterministic Problem的概念具有内涵的一致性可以说我们的NP概念是Entscheidungsproblem和哥德尔不完全定理之间特殊等价形式。一方面我们可以说存在数论上是真的问题的陈述但无法以数论形式去进行逻辑判断其真假或者存在算法语言表达的问题是不可以算法去判定它是否是可计算的。从NP理论看哥德尔不完全定理可以将哥德尔不完全定理表达为一个公理系统内不存在“可以判定一个语法合适的命题是否是这个系统内的定理”的这样一个定理。这个表述与Entscheidungsproblem 具有一致性。NP的本质是不可判断的这个定义似乎容忍了“可能存在确定算法但现在没有找到”这样一种流行的观念这种观念错误与P定义是不相容因为只要你承认“可能存在确定性算法”就已经承认了这是P流行的NP问题的定义都隐含了这种“讫题”或“循环定义”的错误无法跳出事先暗中肯定NPP的旋涡。——这种陈述中所说的“可能”存在……这种超出经典逻辑的实在性和图灵机无限长纸带的观念已经不在经典理论范围内了。 包括哥德尔本人在内的理论界对哥德尔不完全定理的意义和地位问题即哥德尔不完全定理的哲学性质一直存在难以梳理的论争实质上这是在把“形式系统”等价于最基本的“语言”或“知识形式”的本质问题这个层次上的论争这也就是最古老的哲学问题的延续从柏拉图的实在论到中世纪的唯名论、唯实论近现代以来的语言哲学、语法与语义关系以及当前的人工智能基本问题等的论争的延续这一切都深刻地与哲学上的“潜无穷”与“实无穷”的关系相关联。所有这些都是我们的NP理论后面的哲学背景。原文链接http://wap.sciencenet.cn/blog-2322490-1212338.html?mobile1未来智能实验室是人工智能学家与科学院相关机构联合成立的人工智能互联网和脑科学交叉研究机构。未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市云脑研究计划构建互联网城市云脑技术和企业图谱为提升企业行业与城市的智能水平服务。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
