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

博文

我们为什么说“确定型图灵机”不是“非确定型图灵机”的特例?

已有 5792 次阅读 2015-1-27 16:52 |个人分类:不确定性问题和算法讨论|系统分类:观点评述| 悖论, 确定型图灵机, 不确定型图灵机

将“确定型图灵机”理解为“非确定型图灵机”的特例是非常流行的观点,我们已经分析了这种情况导致“不确定性”的消失,即在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,美国哲学家、逻辑学家)的“本体论承诺”,这里可以理解为:如果你作出了一个命题,就承诺了这个命题所表达的问题是一个已经存在事实。




https://blog.sciencenet.cn/blog-2322490-863227.html

上一篇:漫谈“汉字”(4)-参观“罗塞塔碑”有感
下一篇:在贡比涅大学作报告
收藏 IP: 82.246.87.*| 热度|

2 杨正瓴 jrc

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

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

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

GMT+8, 2024-11-13 03:47

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部