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

博文

辨析“circle-free”与“halting” - 定性分析与定量分析

已有 4039 次阅读 2016-8-7 12:44 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 停机问题, 判定问题, circle-free

在图灵1936年的论文中,我们看到了图灵并没有提出所谓的“停机”这个概念,而是一个至今仍然被人们忽视和误解的“circle-free”。这里,我们从认知的角度来进一步辨析“circle-free”与“停机”。  

一般而言,认知事物有“定性、定量”之分,我们先追究一下“性、量”的汉字字源(汉字基因):

性者,心生,人認知之起始,事物之本質;

量者,旦里,白天可知距離者,事物外在之差异。

也就是说,认识起始于定性分析,通过分析事物的内在结构、变化因果,来对未知事物进行分类界定;然后观察、衡量其表象进行定量分析,进一步准确认知事物。

于“可计算性”的认知,图灵在论文中强调“可计算数”一定要由机器打印下来,由此揭示了“机械步骤”的实时(the Actual Time)性本质,这样的机器图灵称之为“circle-free”机器,指没有“死循环(circular)”而能将计算的数打印出来,以此界定“可计算性(computability)”。所以,可以认为“circle-free”是对“可计算性”的定性分析,故作为机器模型的图灵机无须作时空方面的量化限制,而具有“无限长的纸带”,允许“不停机”的circle-free,但是这并不意味着具体的机器没有时空的限制(http://blog.sciencenet.cn/blog-2322490-979317.htmlhttp://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=993665)。

再来看替代“circle-free”的“停机”。若要判断机器是否停机,必须给出一个时间的量化标准,比如说计算的时间等,然而在能界定讨论的对象是否“可计算”之前,是无法给出这样一个量化指标的,因为对一个正在运行的具体机器,还无法辨别其工作状态是circular或circle-free。

可见,针对“可计算性”,“circle-free”旨在定性分析,而“停机”则是定量分析。然而,“停机”的定量分析无法度量不可度量的问题,这正是“停机问题”自己否定自己的悖论形式证明,如我们在博文(http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=991454)中所说:由于把“circle-free”换成了“停机”,就把“判定问题”偷换成了“停机问题”,如此就隐含了“所有的算法都具不可判定的性质”,这是一个观念上的大错误,如果一台计算机或算法不能肯定自己,就推翻了“可计算性”这个概念本身,“‘停机问题’不可判定”意味着——“可计算的”机器不能肯定自己的“可计算性”!就是说,“停机问题”这种悖论式的解释“判定问题”的代价,只是将问题推进到一个更深的缠绕层次。

是故,只有当界定了“可计算性”之后,方可对其进行定量分析,这就是后来计算复杂性的“多项式时间(Polynomial time)”的来由和意义,。。。




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

上一篇:关于“概念”的对话(2)
下一篇:点评《紐約客》科普“P versus NP”-流行的NP定义
收藏 IP: 82.246.87.*| 热度|

2 杨正瓴 zjzhaokeqin

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

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

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

GMT+8, 2024-12-23 17:25

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部