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

博文

NP理论(3):层次与中国传统逻辑

已有 3369 次阅读 2016-8-30 12:57 |个人分类:NP理论|系统分类:科研笔记| 层次, 白马非马, 中国传统逻辑, NP理论

我们曾用中国传统逻辑的经典“白马非马”解析了流行的NP问题的两个定义中所隐含的层次上的混乱:基于“求解”,NP是NDTM(Non-Deterministic Turing Machine)多项式时间可求解的问题;基于“验证”,NP是DTM(Deterministic Turing Machine)多项式时间可验证解的问题。这二个定义被认为等价地表达了NP问题类。

我们认为,这两个定义具有不同层次的性质,“求解”定义基于算法层次,“验证”定义基于判断层次,之所以发生层次上的混乱,是因为流行的NDTM这个概念对TM(Turing Machine)和NTM(Non Turing Machine)的混淆,我们借用“白马非马”这个经典案例分析了这种混乱在人认知上产生的原因。

“马”(形或象)是马类不同于牛、羊等类的本质认知,“白马”则是在“马”这个大类中不同颜色的马的子类。普通人(守城门兵)具有白马属于马类的常识认知而不自觉,所以认定“白马是马”(以枚举替代判断),智者公孙龙则从逻辑的严格上认为“马”与“白马”是不同的层次,坚持“白马非马”的认知(逻辑判断)。仿此分析,对于NP问题类的“验证”定义,是以算法进行的判断(DTM只不过是TM的别名),这就相当于“白马是马”;另一方面,这个“求解”的定义,是以NDTM求解,我们分析了,NDTM实质是TM(我们所说的“不确定性的消失”),NDTM是P和NP的层次混淆的产物,NP问题的两个定义暗含着NP=P,致“P versus NP”成为世纪难题(见博文:http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&quickforward=1&id=888485)。

这篇文章中,我们仍用“白马非马”的逻辑分析方法对“停机问题”所存在的问题予以进一步的分析。

图灵定义的“可计算数”就是circle-free可计算的(circle-free就是以后称之为图灵机的一般算法模型),在图灵的这些相关概念中,并没有“停机”(halting)这个术语,因为图灵机是一般意义上的算法模型,图灵只关心机器具有可计算性的本质,并不关心具体的计算机的时空能力,所以,即使机器不停止,机器仍然可以无限计算下去而具有可计算性的意义,比如有理数1/3在机器上就是可计算的,机器可以无限地输出无限循环小数0.3333333……,这正是图灵机具有无限长的纸带这个构造的重要性。

具体的机器并不等于图灵机,具有图灵机性质的具体机器如冯·诺意曼机,总是时空能力有限的,我们一般认为任何一台具体的计算机都能计算出1/3,这是因为我们实际上已经约定了以某个近似值去代替这个真正的无限循环小数,也就是说是事前约定了停机條件而“停机”。从常识上说,“停机”就意味着得到确定性的答案,这就使“停机”实际上替代了严格的“可计算性”概念,从而使“停机问题”作为悖论形式隐含了对“可计算性”这个根本性概念的否定(见博文:http://blog.sciencenet.cn/blog-2322490-991454.html)。

实际上, 图灵心目中的机器“可计算性”(circle-free)与“停机”(halting)是完全不同层次的概念,借用“白马非马”的方法分析,图灵的机器“可计算性(circle-free)”相当于“马”的“形”,这种本质属性使马区别于非马(如牛、羊等),对应于circle-free区别于circular的本质,而“停机”相当于马(形)这个基本概念下的二级分类(色),“白马非马”就是说白马类与马类是完全不同的层次,这相当于circle-free与halting具有完全不同的层次,因此以“停机”代替“可计算性”就是层次上的混淆和表达上的混乱。

附:《公孙龙·白马论》原文摘录及解读

一,《公孙龙·白马论》原文摘录

“白马非马”,可乎?

曰:可。

曰:何哉?

曰:马者,所以命形也;白者所以命色也。命色者非命形也。故曰:“白马非马”。

曰:有白马不可谓无马也。不可谓无马者,非马也?有白马为有马,白之,非马何也?

曰:求马,黄、黑马皆可致;求白马,黄、黑马不可致。使白马乃马也,是所求一也。所求一者,白者不异马也。所求不异,如黄、黑马有可有不可,何也?

可与不可,其相非,明。故黄、黑马一也,而可以应有马,而不可以应有白马,是白马之非马,审矣!

二,解读

反方:“白马非马”,可以这样说吗?

正方:可以。

反方:为什么?

正方:“马”,指称形状;“白”,指称颜色。颜色不同于形状,所以说:“白马非马”。

反方:既然说有白马,就不能说“没有马”。既然不能说“没有马”(承认事实上有马),怎么还说“非马”(说“没有马”)呢?(这就是“说”与“事实”相违背。)有白马就是有马,只是白色的马而已,为什么说“非马”呢?

正方:如果是找“马”,黄马、黑马都可以;但如果是找“白马”,黄马、黑马就不可以了。若说“白马乃马”,是着眼于它们具有同一性本质,本质相同,白马与马就没有什么区别了。既然在“马”的本质上没有区别,为什么现在又有黄马、黑马对应于“马”的不同分别呢?这里的对应与不对应,是针对不同的层次(相)而说的,(马与色马)层次的不同是很明确的。所以,黄马、黑马具有马的共同本质,符合“马”的个大概念层次,但不符合“白马”(色马)这个二级概念,故白马与马层次不同,现在可以分析很清楚了!

在这段精彩的对话中,公孙龙阐释了“形”(象)与“色”二个层次的不同:当用“形”(象)作为判断标准时,是为了在一群混杂着别的动物(比如牛羊等)中找“马”,所以“马”的定义只关心“形”(象),并不关心诸如“色”较具体的属性,也就是说,马这个大类中包含了各种不同颜色的马(“色马”是马类中的一类),在这种情况下,黄马、黑马都是所找的对象。但是当用“色”作为判断标准,是为了在马类中找比如说颜色为白色的“白马”子类,那么黄马、黑马就不是所找的对象了!



https://wap.sciencenet.cn/blog-2322490-999674.html

上一篇:点评《紐約客》科普“P versus NP”-流行的NP定义
下一篇:前驻法国大使吴建民引用“郑和下西洋”反驳“中国威胁说”

4 郑小康 杨正瓴 wangbin6087 zjzhaokeqin

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

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

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

GMT+8, 2022-5-28 05:51

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部