网络维护网站建设培训,wordpress自带的会员中心,事业单位网站建设的作用,上海网站建设网页设来源#xff1a;图灵人工智能转自 http://blog.sciencenet.cn/u/liuyu2205P vs NP世纪难题显示出在现有的计算机理论中存在着令人不安的困惑#xff1a;一方面#xff0c;书本中的NP问题理论部份无论是学习或教学都感到困难#xff0c;以至于人们不得不一次又一次回头去重新… 来源图灵人工智能转自 http://blog.sciencenet.cn/u/liuyu2205P vs NP世纪难题显示出在现有的计算机理论中存在着令人不安的困惑一方面书本中的NP问题理论部份无论是学习或教学都感到困难以至于人们不得不一次又一次回头去重新学习或思考但或者失望而返或者强迫自己服从这些权威论述另一方面现有的NP问题理论与实际工作几乎完全脱节甚至有人说完全可以不用此理论。进一步包含现有的NP问题的计算机理论无法与正蓬勃发展的人工智能理论衔接。自2015年开设博客“不确定性的困惑与NP理论”以来特别是2020年困难而特殊的一年承蒙大家的热情支持和慷慨的帮助这里我们与大家分享关于P vs NP问题研究工作总结性的文章“NP问题是可计算的吗”- 从“可计算性”的角度审视NP希望对理清P vs NP问题的认知纠缠有所帮助并祝大家新年愉快来年顺利。。。题目 “NP问题是可计算的吗”- 从“可计算性”的角度审视NP周剑铭 柳渝yu.liu-picardie.frMIS, Université de Picardie Jules Verne, 33 rue Saint-Leu, 80090 Amiens, France一引言二NP定义溯源三现有的“可计算性”“NP问题是穷举法可计算的”1NP的形式定义2分析NP的形式定义3现有的“可计算性”所隐含的矛盾“图灵机”与“可计算问题”四图灵的“可计算性”“NP问题是穷举法可计算的吗”1Entscheidungsproblem溯源2基于“可计算序列”的“判断问题”3“可计算序列”“计算机器”与“可计算问题”4“NP问题是穷举法可计算的吗”五案例研究现有的“图灵机” vs 图灵的“计算机器”六“判定问题”与“判断问题”判断的主体七结语一引言在现有的计算机理论中PPolynomial time指“图灵机在多项式时间可判定的问题类”但是对NPNondeterministic Polynomial time情况却复杂得多首先有一个教科书式的定义“NP是不确定性图灵机在多项式时间可判定的问题类” NP is the class of problems decidable by Non-Deterministic Turing Machine (NDTM ) in polynomial time - 定义1后来又发展出一个更通俗化的定义“NP是图灵机在多项式时间可验证的问题类”NP is the class of problems verifiable by TM in polynomial time - 定义2。于是P vs NP问题被一般性表达为NPP即多项式时间可验证的问题NP是多项式时间可判定的问题吗P [1][2]P vs NP问题成为计算机理论的重大的未解难题还被Clay Mathematics Institute收录为七个千禧年难题之一。Gasarch于2002年2012年和2019年对P vs NP问题的前途进行了三次调查 [3]表明人们为寻找求解NP问题的多项式时间算法付出了巨大的努力以求一举解决P vs NP难题但是迄今为止并没有出现有价值的进展方向。Hemaspaandra在介绍Gasarch的第二次调查时说 我希望在遥远的未来当人们读到这四篇文章指介绍P vs NP问题的四篇文章可以帮助他们了解在“P vs 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) [4]。P vs NP问题的难点集中在对NP的认知上表达为NP定义关于NP的定义缠绕了计算机基本理论几十年比如Scott Aaronson在博客“The Scientific Case for P≠NP”说似乎有一个“看不见的电围栏”把P问题与NP完全的问题区分开(there seems to be an invisible electric fence separating the problems in P from the NP-complete ones) [5]。由流行的NP定义得出“NP问题是穷举法可计算的”也就是说NP定义的本质是对NP问题的“可计算性”的判断。然而“可计算性的判断”是可计算性理论的核心议题整个计算机理论由此展开可是对于“NP问题的可计算性的判断”如此重要的议题却几乎未见学术界展开讨论过。本文追本溯源回到图灵1936年那篇奠基可计算性理论的论文《论可计算数及其在判定问题上的应用》On Computable Numbers, with an Application to the Entscheidungsproblem[6]对比现有的“可计算性”与图灵的“可计算性”解读流行NP定义探讨其对NP问题的“可计算性”判断的有效性我们将看到对此质疑“NP问题是穷举法可计算的吗”二NP定义溯源NP作为概念“Non-deterministic Polynomial time”的提出源于柯克1971年那篇奠基性的论文文中柯克提出后人称之的“柯克定理”即论文中的定理1 [7]定理1如果一个符号串集合S被某种不确定性图灵机在多项式时间内接受那末S可以被P-归约到{析取重言式}。Theorem 1 If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.由此得出NP的第一个流行定义定义1 : NP is the class of problems decidable by NDTM in polynomial time。在柯克的论文中NDTM原指由“神谕机Oracle Machine”与“图灵机Turing Machine” 混合而成的“查询机Query Machine”查询机的计算行为被解释为对于一个NP问题实例神谕机“可解”此“解”可由图灵机多项式时间“验证”。然而由于神谕机不是构造性的机器模型在现实中并不存在为了将神谕机从NDTM中排除学界遂将NDTM的计算行为解释为“猜测验证” [8] 即对于一个NP问题实例NDTM在多项式时间“猜测”出一个候选解并能在多项式时间“验证”。经过这样的解释NDTM就从“查询机”变成了现在的“多选择的NDTM”即相对于在计算的下一步只有“唯一的选择”的TMNDTM可以有“多选择” [9]。于是得到NP的第二个流行定义定义2 : NP is the class of problems verifiable by TM in polynomial time。定义1与定义2被认为等价 [10]NDTM又被解释为与TM等价“Every nondeterministic Turing machine has an equivalent deterministic Turing machine”Sipser书Theorem 3.16 于是有了一个非形式的“承认”TM在指数时间内模拟NDTM的计算。 由此人们很快就认可NDTM的计算行为与“穷举法”等同这样NP又被解释为“NP是穷举法可计算的问题类”毕竟P与NP不同于是就有了“NP问题是可计算的但难计算的”这样的流行观念。不管以后的解释如何在直觉认知上NP与P是不同的但是NP的定义又给人NP与P等价的指望这就是P vs NP问题的困难之源。三流行的“可计算性”“NP问题是穷举法可计算的”首先我们讨论NP的形式定义。1NP的形式定义这里我们考虑Papadimitriou的书“计算复杂性”的第9章给出的NP的形式定义 [11]Cook在为Clay Mathematics Institute介绍P vs NP问题时也给出了类似的定义 [1]- 令R为二进制字符串的关系 即让R为一组有序对(x,y)的集合其中x和y是二进制字符串。 如果存在确定性图灵机在多项式时间内判定给定的(x,y)是否在R中我们则说R是“多项式可判定”。如果 k 1 使得对于R中的所有(x,y)y的长度我们写为| y |最大为|x|^k则R是“多项式平衡”。(Let R be a relation on binary strings; i.e., let R be a set of ordered pairs (x,y) where x and y are binary strings. We say that R is polynomially decidable if there is a deterministic Turing machine that decides in polynomial time where a given (x,y) is in R. We also say that R is polynomially balanced if there is some k 1 such that for all (x,y) in R, the length of y (which we write as |y|) is at most |x|^k.)- 现在我们准备定义NP。 语言L在NP中当且仅当存在多项式可判定且多项式平衡的关系R使得语言L {x : (x,y)在R中存在y}时。(Now we are ready to define NP. A language L is in NP if and only if there is a polynomially decidable and polynomially balanced relation R such that L {x : (x,y) is in R for some y}.)2分析NP的形式定义NP的形式定义涉及集合L和R让我们以SAT典型的NP问题为例从解读L和R开始。2.1 集合L和R考虑2个SAT实例f1 (x1 ∨x2 ∨x3)∧(x1 ∨x2 ∨x3)∧(x1 ∨x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)f1有3个变元共2^38个变元赋值组合其中4个是f1的解R {(f1,(0 1 0)), (f1,(0 1 1)), (f1,(1 0 1)), (f1,(1 1 1))}。f2 x1 ∧¬x1, 1个变元共有2个变元赋值的组合f2无解R Ø。对于Lf1可满足在L中f2不可满足不在L中故L { …, f1, …}。所以R是SAT的给定实例的所有解的集合而L是SAT的所有可满足的实例的集合- R {(x,y) : x是SAT的实例y是x的解}- L {x : 存在某个y使得(x,y) 在R中} 下面我们按照这个方法定义SAT很快能看到P面向“判定问题”而NP面向“判断问题”。2.2 “判定问题”与“判断问题”记集合A {x G(x)表示x满足某种性质}表达元素x与集合A的所属关系即“整体中个体”而判断x是否在A中即判断元素x是否具有性质G(x)。从这个理解出发SAT呈现出二个层次上的定义- 判定问题穷举法判定SAT问题的给定实例x是否可满足。这相当于穷举法判定x的给定候选解y是否在R中。- 判断问题如果穷举法可以判定SAT实例R那么穷举法是否可以判定SAT问题L可见“判定问题”面向“实例”个体R而“判断问题”面向“问题”整体L所以NP的形式定义是基于对“判断问题”的回答。实际上我们也能看到这个回答才是造成现有的NP定义的困难的根源。对于“判定问题”通过枚举SAT实例x的所有候选解y重复调用多项式时间验证解的图灵机M就可以在指数时间判定x是否可满足所以穷举法对判定SAT实例x具有可计算性。但要注意这个意义上的“穷举法”并没有产生一个新的图灵机与之对应就是说不过是重复调用多项式时间验证解的图灵机M因此这里的“指数时间”只是表达重复调用M是一个由“人”暗中定义了的“指数时间复杂度”。所以“判定问题”的本质是“P问题”。根据NP的形式定义“语言L在NP中当且仅当存在多项式可判定且多项式平衡的关系R使得语言L {x : (x,y)在R中存在y}”就是说“穷举法”判定SAT实例与“穷举法”判定SAT问题等价换句话说在“判定问题”与“判断问题”之间建立起了越界的等价关系这也正是NP的非形式定义1与定义2“等价”所表达的意义“NP is the class of problems verifiable by TM in polynomial time”与“NP is the class of problems decidable by NDTM in polynomial time”等价。所以流行NP定义是对NP问题的“可计算性”的直接肯定而非论证实例与问题的关系从“整体中的个体”变成了“个体即整体”“判断问题”因此被取消了从而失去了揭示NP本质的可能性暗含NPP。下面我们从现有的“可计算性”观念中追究更一般性的原因。3流行的“可计算性”所的隐含的矛盾“图灵机”与“可计算问题”在现有的计算机理论中“可计算问题”被解读为“可计算问题是由’停机’的图灵机计算的问题”图灵机的“无限长的纸带”被解读为“无限的时空”所以图灵机的计算被解释为“不计时空开销”。这样的“可计算问题”在“理论上”似乎是可计算的但“物理上”却不一定是可计算的。“图灵机模型使用无限长纸带作为其无限内存有一个读写头。最初输入字符串被放置纸带上纸带的其他方格均为空白。机器将继续计算直到决定产生输出为止。 通过进入指定的接受和拒绝状态来判断是否接受和拒绝输入如果图灵机不进入接受或拒绝状态则将永远持续下去永不停止。[10]Sipser书Theorem 3.16”- The Turing machine model uses an infinite tape as its unlimited memory. It has a tape head that can read and write symbols and move around on the tape. Initially the tape contains only the input string and is blanc everywhere else. If the machine needs to store information, it may write this information on the tape. To read the information that it has written, the machine can move its head back over it. The machine continues computing until it decides to produce an output. The outputs accept and rejet are obtained by entering designated accepting and rejecting states. If it doesn’t enter an accepting or a rejecting state, it will go on forever, never halting. 既然图灵机的计算“不计时空开销”那么“穷举法”计算NP问题的实例与计算NP问题任意实例就没有区别这就是“判定问题”与“判断问题”之间越界的等价关系的来源现在让我们追本溯源回到图灵的可计算性理论考察“NP问题是穷举法可计算的”有效性。四图灵的“可计算性”“NP问题是穷举法可计算的吗”作为计算机理论的核心概念“可计算性”表达了“算法”普遍性的解决问题的过程性能力对这种过程性能力的考察被数学家隐含地表达出来这就是著名的希尔伯特David Hilbert 1862─1943的Entscheidungsproblem是否存在“通用过程”来判定任何可定义的数学问题可解。Entscheidungsproblem 这一词由于历史时间不同具有不同的具体表达形式。1Entscheidungsproblem溯源Entscheidungsproblem源于希尔伯特1900年所作的《数学问题》的著名讲演其中提出了数学理论中的23个最困难的问题第10问题是这样说的[13]: 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 in a finite number of operations whether the equation is solvable in rational integers. 作为一个大数学家希尔伯特并没有用“数学方法”、“函数”或“形式方法”这样现成的术语而是问能否“设计一个过程”To devise a process来“判定”determine任何一个丢番图方程问题是否可解在1936年的文章中图灵证明不存在“通用过程”判定任何一阶谓词公式可证。2基于“可计算序列”的“判断问题”为此图灵理解性说[6] 对这样一个“通用过程”的问题可以表达为通用过程判定给定的整数n是否具有性质G(n)的问题比如G(n)可能表示“n是可满足的’’或“n是一个可证明公式的Godel表达这相当于计算一个数如果G(n)为真其第n个数字为1如果G(n)为假其第n个数字为0。”For each of these general process problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n) [e.g. G{n) might mean n is satisfactory or n is the Godel representation of a provable formula], and this is equivalent to computing a number whose n-th figure is 1 if G(n) is true and 0 if it is false.与上述基于“语言”的NP的形式定义相比图灵引入了“可计算数序列”computable numbers/sequence概念表示机器写下的所有实例的计算结果而将给定实例的计算结果置于此序列中表达了实例与问题的“整体中个体”的关系也就是说“判定问题”包含在“判断问题”中。“可计算数序列”成为图灵工作的红线贯穿于整个论文中正如 Charles Petzold在其书The Annotated Turing所说[12]:- “尽管解决Entscheidungsproblem确实是图灵写这篇文章的动机但是这篇长篇大论本身讲的却是’可计算数’。在图灵的定义中可计算数就是可以使用机器计算的数。论文前面60%的内容都是对可计算数的探索。”让我们考察图灵是如何从“可计算数序列”出发定义“可计算性”的。3“可计算序列”“计算机器”与“可计算问题”图灵在论文开篇提出“可计算数”computable numbers强调是由机器写下来的 [6] - 按照我的定义一个数是可计算的如果它的十进制的表达能被机器写下来。According to my definition, a number is computable if its decimal can be written down by a machine. 接着图灵将人计算实数与机器计算过程进行比较构造出作为现代计算机模型的“计算机器”computing machine写下“可计算数序列”computable number/séquence)- 如果一台机器打印两类符号第一类称为数字全是0和1其它被称为第二类符号则机器将被称为“计算机器”。如果给机器装置一条空白纸带让它运动起来从正确的初始m格局出发机器打印的第一类符号的子序列称作机器计算的序列在表达为二进制的十进制实数前放上小数点称作机器计算的数。If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.图灵进一步区分Circular machine和Circle-free machine- 如果计算机器只写下第一类有限数目的符号被称作“Circular”否则被称作“circle-free”。If a computing machine never writes down more than a finite number of symbols of the first kind it will be called circular. Otherwise it is said to be circle-free.然后再用Circle-free machine的计算过程明确定义“可计算数序列”Computable sequences/numbers- 一个序列被说成“可计算的”如果能够通过一台“circle-free machine”计算而得。一个数是“可计算的”如果它与由“circle-free machine”计算的数只差一个整数。A sequence is said to be computable if it can be computed by a circle-free achine. A number is computable if it differs by an integer from the number computed by a circle- free machine.并且说- 为了避免混淆我们更经常说可计算序列而不是可计算数。We shall avoid confusion by speaking more often of computable sequences than of computable numbers. 这样“可计算序列”在“算法计算机器”与“问题”之间建立起可能存在的某种“实质性”的联系“可计算问题是计算机器写下可计算序列的问题”。由此图灵的“可计算性”表达了“通用性”“整体性”和“实时性”。对比上述流行的“可计算问题”图灵定义的“可计算问题”不仅在“理论”上是可计算的而且在“物理”上也是可计算的4“NP问题是穷举法可计算的吗”从图灵的“可计算性”的角度SAT表达为“判断问题”: - 判断问题是否存在计算机器判定SAT的给定实例fn可满足这相当于计算序列αL G(f1)G(f2)G(f3)... G(fn)…G(fn)表示fn是可满足的实例如果G(fn)1fn是可满足的否则fn是不可满足的所以考察“穷举法”对SAT问题是否具有可计算性就是考察“穷举法”能否写下SAT问题的可计算序列αL G(f1)G(f2)G(f3)…G(fn)…。如以上分析“穷举法”判定SAT的给定实例是通过重复调用多项式时间验证解的计算机器M而具有“指数时间复杂度”所以“穷举法”的本质就是计算机器M而“穷举法”的指数增长的计算开销能否胜任SAT的实例规模的增长即能否计算αL G(f1)G(f2)G(f3)…G(fn)…成为了“问题”换句话说多项式时间验证解的计算机器M对SAT问题是否具有可计算性成为了“问题”是有问题“SAT是穷举法可计算的吗”实际上对“SAT是穷举法可计算的吗”的判断进入了计算复杂性理论的论域而对SAT的“可计算性”的一般性判断则与图灵论文的主题希尔伯特的Entscheidungsproblem密切相关需要专门讨论不是本文的主题。五案例研究现有的“图灵机” vs 图灵的“计算机器”为了进一步理解现有的“可计算性”与图灵的“可计算性”的区别我们以判定任意自然数的奇偶性为例对比“图灵机”与图灵的“计算机器”。1“图灵机” 判定问题判定所有的自然数n的奇偶性这相当于判定任意的自然数n是否在偶数集合A中A {n : mod(n, 2)0}。比如n2mod(2, 2)0故2在A中n3mod(3, 2)/0故3不在A中。这里假设输入的自然数用“真数”表示112113111。。输出1表示偶数输出0表示奇数。图灵机M1的规则表q1, 1, #, R, q2q2, 1, #, R, q1q1, #, 1, R, qYq2, #, 0, R, qNq1表示“初始状态”qYt表示“接受状态”, qN表示“拒绝状态”qY与qN都是“停机状态”。模拟M在输入n2的运行开始的纸带放置11 Rule 1 1 # # # …内态的变化q1 q2 q1 qY.纸带的变化# # 1 # # …模拟M在输入n3的运行开始的纸带放置任给的一个自然数 1 1 1 # # …内态的变化q1 q2 q1 q2 qN.纸带的变化# # # 0 # …2图灵的“计算机器”根据图灵对“判断问题”的表达判断问题判定所有的自然数n的奇偶性G(n)表示n是偶数n mod 2 0这相当于计算序列010101…如果G(n)为真偶数序列的第n个数字为1如果G(n)为假 (奇数)序列的第n个数字为0。其可计算序列记为α G(1)G(2)G(3)…G(n)。。。 010101…G(1)0 (n1, 奇数G(2)1 n2, 偶数G(3)0 (n3, 奇数)。。。图灵在论文中给出的第一个“计算机器”的例子就是计算序列010101…但图灵是将此序列作为十进制数0.333…的二进制数表示所以没有考虑输入数据纸带的输入只是空白符号“#”blank其对应的“计算机器”的规则表如下q1, # , 0, R, q2q2, # , # , R, q3q3, # , 1, R, q4q4,# , # , R, q1模拟此机器的运行# # # # # # …q1 q2 q3 q4 q1 q2 …0 # 1 # 0 # …我们将序列010101…作为对所有自然数1,2,3,…奇偶性的判断结果纸带上的输入数据是用“真数”表示的所有自然数112113111。。输出1表示偶数输出0表示奇数。所以需要上述计算机器M1的规则表略作修改成M2q1, 1, #, R, q2q2, 1, #, R, q1q1, #, 1, R, q1q2, #, 0, R, q1此机器的初始状态是q1没有停机状态。在q1状态下遇空白符“#”写下“1”表示输入的自然数是偶数然后回到初始状态q1q2状态下遇空白符“#”写下“0”表示输入的自然数是奇数然后回到初始状态q1继续判断纸带上的下一个自然数。模拟此“图灵机”的运行开始的纸带1 # 1 1 # 1 1 1 # …内态的变化q1 q2 q1 q2 q1 q1 q2 q1 q2 q1, …纸带的变化# 0 # # 1 # # # 0 …可见现有的“图灵机”M1与图灵的“计算机器”M2之间存在着微妙的差别“计算机器”计算完一个实例然后回到初始状态“不停机”继续计算下一个实例“无限长的纸带”对应“无限长的可计算序列”circle-free machine表达计算机器的计算能力的“通用性”。所以“计算机器”虽然没有对计算一个实例的时空开销进行规定但是并非指计算一个实例“不计时空开销”。而现有的“图灵机”加入了“停机状态”计算完一个实例就“停机”接受与拒绝遂将“无限长的纸带”解读为计算一个实例“不计时空开销”。六集合与判断判断的主体如上述分析NP定义的本质是对NP问题的“可计算性”的判断但是流行的NP定义将“判定问题”等价于“判断问题”直接得出“NP问题是可计算的”判断。我们从集合与判断的角度进一步分析其原因。康托最初给出的集合定义 [14]- 集合是“我们感知或思想到的”不同的对象的聚集而成的整体这些对象称为集合的元素。- A set is a gathering together into a whole of definite, distincts objects of our perception [Anschauung] or of our thought - which are called elements of the set.就是说集合表达的是对元素与集合的所属关系即“整体中个体”的“判断”。判断涉及到“判断的主体”在一般情况下“主体”指“人”人运用感知或思想进行判断。当人借助于数学和逻辑进行判断论域是“数学”但是人当借助于“算法”来进行判断时判断的“主体”成了“机器”论域就从“数学”转移到了“算法”。虽然数学和算法都使用符号但其组织性质完全不同数学是纯粹的形式关系与“物理”无关而算法则一定是“实时”Actual Time过程与时空有关。在流行的NP定义中“判定问题”指“穷举法判定NP问题的给定实例x是否可满足”判断的主体是“图灵机”算法算法与时空有关然而在现有的可计算性理论中图灵机的“无限长的纸带”被解释为“不计时空”“图灵机”因此失去了算法的“物理”性质实际上成为了“神喻机”也就是说判断的主体从“图灵机”偷换成了“神喻机”所以“穷举法”判定NP问题的实例与判定NP问题就没有了区别直接得出“NP问题是可计算的”判断从而取消了“人”作为判断的主体的“判断问题”流行NP定义暗含NPP。可见在现有的“可计算性”理论中存在着判断“主体”的混淆导致对个体与整体关系认知的混淆暗中用“个体即整体”替代了“整体中个体”这正是流行NP定义所隐藏的认知错误的来源所谓“数学家的误解” [15]。七结语我们追本溯源回到图灵1936年那篇奠基可计算性理论的论文《论可计算数及其在判定问题上的应用》解读流行的NP定义质疑“NP问题是穷举法可计算的”流行观点。通过对比分析我们指出现有的“可计算性”与图灵的“可计算性”之间有出入。首先体现在对NP问题的二种表达中- 基于“语言”的NP问题- 基于“可计算序列”的NP问题。然后是“图灵机”与图灵定义的“计算机器”之间存在着微妙的差别- “图灵机”完成对一个实例的计算而“停机”“无限长的纸带”被解释为计算一个实例“不计时空开销”- 图灵的“计算机器”完成对一个实例的计算后回到初始状态然后“不停机”继续计算下一个实例。由此导致关于“可计算问题”的二种观点- 现有的“可计算问题是图灵机不计时空开销计算但能停机的问题”在“物理”上不必是可计算的。- 图灵的“可计算问题是计算机器能写下可计算序列的问题”在“理论”和“物理”上的可计算性是一致的。我们从集合与判断的角度分析在现有的“可计算性”理论中存在着判断“主体”的混淆导致“判定问题”与“判断问题”的混淆。我们认为欲解决P vs NP问题需要正视对NP问题的“可计算性”的“判断问题”这就意味着需要追本溯源审视对“图灵机”“可计算性”“计算复杂性“停机问题”等计算机理论的基本议题的认识。本文所介绍的工作就是这方面的初步尝试。我们的工作提示图灵的著作和工作虽然已经近百年了尽管在技术实践上取得了巨大的成就但在图灵的主要理论基础上并没有取得跨越性的进步甚至已经被作为计算机理论圣经的“图灵机”仍然蒙着一层神秘的面纱比如问 - 为什么现在的“图灵机”与图灵的“计算机器”之间存在着微妙差别- 为什么“可计算序列数”的概念从现有的计算理论中消失了图灵处在世界格局重构的年代数学和科学理论的大厦己经耸立工业技术与纯粹理论正在融汇而走向一个全新的信息时代图灵有幸成为了这个转折点我们並不期望直接从图灵的论著中找到现成的答案而是希望通过他的著作去理解他深刻而隐秘的思想从中获取灵感用我们的智慧去参与和回应时代面临的挑战比如P vs NP问题的挑战。。。参考文献[1] Stephen Cook, P vs NP Problem (http://www.claymath.org/millennium-problems/p-vs-np-problem)[2] A Most Profound Math Problem (http://www.newyorker.com/tech/elements/a-most-profound-math-problem)May 2 2013, the New Yorker.[3] Guest Column: The Third P ? NP Poll William I. Gasarch (https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf)[4] William I. Gasarch, The P?NP poll. SIGACT News Complexity Theory Column 74.http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf[5] S. Aaronson. The Scientific Case for P≠NP (https://www.scottaaronson.com/blog/?p1720)[6] Turing, A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2 (published 1937), 42 (1), pp. 230–65 (https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf)[7] Stephen Cook, The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151-158 (1971). (http://theory.stanford.edu/~trevisan/cs172-07/cook.pdf)[8] Garey Michael R., David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and company (1979) [9] Michael Sipser. Introduction to the Theory of Computation, Second Edition. International Edition (2006) [10] JianMing Zhou, Yu Li, Inquiry of P-reduction in Cook’s 1971 Paper -from Oracle machine to Turing machine. http://arxiv.org/abs/1905.06311 [11] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley Edition (1994). [12] Charles Petzold, The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine. John Wiley Sons, Inc. (2008). [13] Hilberts tenth problem (https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem)[14] https://en.wikipedia.org/wiki/Set_(mathematics)[15] David Deutsch, Constructor Theory David Deutsch. https://arxiv.org/pdf/1210.7439.pdf未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市云脑研究计划构建互联网城市云脑技术和企业图谱为提升企业行业与城市的智能水平服务。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
