|||
将“确定型图灵机”理解为“非确定型图灵机”的特例是非常流行的观点,我们已经分析了这种情况导致“不确定性”的消失,即在NP完备理论(NP-completeness theory)中始终存在着事先暗中肯定:NP=P,这种认知上的错误。只要你“认为”非确定型图灵机包含了确定型图灵机,就意味着事先“承诺(注)”了非确定型图灵机与确定型图灵机具有相同的性质,也即NP与P具有相同的性质。图灵机和P算法都有严格的定义,这就造成了以“确定型图灵机”来定义“非确定型图灵机”(http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine),用我们的话说,就是“不确定性”消失了。
更引起我们兴趣、更为难解的是:人们为什么会顽固地坚持这种视而不见的错误? 我们认为,这是因为认知层次上的交叉混乱所致,也是人们所熟知的“悖论”的来源。在对“白马非马”这个中国古代著名的逻辑难题再解释中,我们已经讨论过了流行观点中P与NP的层次混淆,这里再结合非确定型图灵机与确定型图灵机的关系和“白马非马”的逻辑分析方法,予以更详细的分析。
为了方便解读,我们取“白马”和“色马”两个集合,定义“色马”为所有非白色的马(这里不涉及色觉区别上的技术问题),这种外延性质的分类没有任何技术上的困难,具体的马总是有颜色的,都是可以一一枚举进行分类。
如果现在有人提出,“白马”可以“认为”是“色马”的特例,人们几乎难以反驳,一方面,“白马”类确实可以被包括在“色马”类之中,另一方面,任何一匹具体的白马也可以计算在色马类中,这种情况正像“P问题包括在NP问题内”和“确定型图灵机包括在非确定型图灵机内”一样。
但是,前一种情况,“白马“、“色马”是两个并列集合,后一种情況,“白马”是“色马”的子集,兄弟关糸与母子关系,本质完全不同。换句话说,前后之“色马”所指不同!
我们认为,上述命题在各自的层次都是对的,但将不同层次混淆就造成了一种普遍性的认知困难,尽管如此,这还是比较容易分别出来的,而真正难以察觉的困难在于不同层次的交叉混乱,这种混乱是顽固的、被坚持的。比如,P和NP、“确定型图灵机”和“非确定型图灵机”不同层次的交叉混乱,就是认知层次上命题、概念与技术层次上的方法、对象混淆在一起,随时发生概念偷换而不自觉,因此不得不一次次去重新澄清概念,一次次从头开始,但又总是一次次不知不觉地发生概念偷换,陷入难以摆脱的自我缠绕、自相矛盾中。
理论上的自相矛盾是悖论的一般情况,比如,如果“认为”P和NP不同,“确定型图灵机”和“非确定型图灵机”不同,人们才会普遍性地接收这两种不同性质的概念;但你如果又“认为”NP包含P,“确定型图灵机”是“非确定型图灵机”的特例,就意味着事先承认了两者具有相同的性质,这就是自相矛盾。然而,很少有人对此质疑,一些人坚持这种错误,大多数人则持回避、拒绝探究的态度。
如果现在弄清了这两种层次的混淆和混乱,就可以简单地说,“认为”“确定型图灵机”是“非确定型图灵机”的特例,等于“承诺”了“非确定型图灵机”具有“确定型图灵机”的性质,也就是取消了“非确定型图灵机”这个概念。
所以,我们认为“确定型图灵机”不是“非确定型图灵机”的特例, 不是指将“确定型图灵机”看作是“非确定型图灵机”的特例这样的子母集合关系是错误的,而是说用这种子母集合关系来讨论“非确定型图灵机”的本质、定义NP是错误的,这个根源性错误导致现有NP完备理论中一系列理解和定义上的错误。
注:“承诺” 一词出自奎因(Quine,1908-2000,美国哲学家、逻辑学家)的“本体论承诺”,这里可以理解为:如果你作出了一个命题,就承诺了这个命题所表达的问题是一个已经存在事实。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-25 00:06
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社