|||
在图灵1936年的论文中,我们看到了图灵并没有提出所谓的“停机”这个概念,而是一个至今仍然被人们忽视和误解的“circle-free”。这里,我们从认知的角度来进一步辨析“circle-free”与“停机”。
一般而言,认知事物有“定性、定量”之分,我们先追究一下“性、量”的汉字字源(汉字基因):
性者,心生,人認知之起始,事物之本質;
量者,旦里,白天可知距離者,事物外在之差异。
也就是说,认识起始于定性分析,通过分析事物的内在结构、变化因果,来对未知事物进行分类界定;然后观察、衡量其表象进行定量分析,进一步准确认知事物。
于“可计算性”的认知,图灵在论文中强调“可计算数”一定要由机器打印下来,由此揭示了“机械步骤”的实时(the Actual Time)性本质,这样的机器图灵称之为“circle-free”机器,指没有“死循环(circular)”而能将计算的数打印出来,以此界定“可计算性(computability)”。所以,可以认为“circle-free”是对“可计算性”的定性分析,故作为机器模型的图灵机无须作时空方面的量化限制,而具有“无限长的纸带”,允许“不停机”的circle-free,但是这并不意味着具体的机器没有时空的限制(http://blog.sciencenet.cn/blog-2322490-979317.html,http://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)”的来由和意义,。。。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-23 04:10
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社