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

博文

不确定性图灵机(NDTM)与“不确定性”

已有 5778 次阅读 2015-4-14 13:28 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 不确定性, versus

在NP完备理论(NP-completeness theory)中,把“不确定性图灵机”(NonDeterministic Turing Machine,NDTM)因一个问题存在多算法或多解而具有的“多选择”,当作了“不确定性问题(Nondeterministic Problem)”的“不确定性”,遂有用NDTM定义NP一说,这种观点的理论表达就是教科书中的流行概念:NP=不确定性多项式时间(Nondeterministic Polynomial time) 。

我们认为,存在多算法或多解与存在唯一算法或解,在图灵机的意义上是等价的,图灵机并不关心具体的算法或解的多少,有算法就是“确定性”;这种情况与图灵机并不关心具体的计算时间长短一样。图灵机是(所有可计算性)算法的模型:图灵机就是算法可计算性 — “图灵-丘奇论题”。正是在这个意义上,算法理论中的“确定性”就是“可计算性”。

由此可见,NDTM因多算法或多解而具有的“多选择”,仍然是“确定性”意义的,但真正的问题在于,这种确定性意义的“多选择”的解释混入了日常的价值选择,此价值选择不是算法或机器性质的,而是人的选择性。通常情况是,暗中假定了对多算法或多解的选择是自然数顺序、字典顺序或随机性,就是说暗中将人的选择性以自然条件形式附加给了机器,在这种情况下,人的价值选择所具有的似是而非的“不确定性”与NDTM具有确定性意义的“多选择”混淆了,从而导致与“不确定性问题(NP)”本身的“不确定性”混淆。

所以,这里存在双重的混淆,一方面,不确定性图灵机(NDTM)混淆为确定性图灵机(DTM),另一方面,这种具有确定性实质的机器(DTM)又被混淆为真正的“不确定性”意义。

为了理清混乱,在概念的定义上作如下的清理是必要的:

1,NDTM,译作“不确定性图灵机”,即文献中的“非确定型图灵机”或“非确定性图灵机”,NDTM相对于DTM(确定性图灵机),而DTM就是TM(图灵机)。

2,NTM(Non Turing Machine),直译为“非图灵机”,也就是“非机器”,相对于“图灵机(TM)”,这是图灵本来意义上的,但在语言表达上不通顺,所以图灵才有“神喻机”这个不得已的用法。

3,NP(Nondeterministic Polynomial time),译作“不确定性多项式时间”,这个流行术语指存在(多个)多项式时间算法或解,与上述对NDTM的解释一致,本质是“确定性”的。

如我们以前的论述,把多算法或多解的“多选择”当作“不确定性”,就是NP的“不确定性的消失”。  




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

上一篇:NP理论中几个术语的约定
下一篇:“问题”的系统观(整体观)

5 姜咏江 杨正瓴 邹晓辉 icgwang nextvisionary

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

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

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

GMT+8, 2022-1-25 10:53

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部