科学网 › 标签 › circle－free

标签: circle－free

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

辨析“circle－free”与“halting” －定性分析与定量分析: 热度 2 liuyu2205 2016-8-7 12:44; 在图灵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=spaceuid=2322490do=blogid=993665 ）。再来看替代“circle－free”的“停机”。若要判断机器是否停机，必须给出一个时间的量化标准，比如说计算的时间等，然而在能界定讨论的对象是否“可计算”之前，是无法给出这样一个量化指标的，因为对一个正在运行的具体机器，还无法辨别其工作状态是circular或circle－free。可见，针对“可计算性”，“circle－free”旨在定性分析，而“停机”则是定量分析。然而，“停机”的定量分析无法度量不可度量的问题，这正是“停机问题”自己否定自己的悖论形式证明，如我们在博文（ http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=991454 ）中所说：由于把“circle－free”换成了“停机”，就把“判定问题”偷换成了“停机问题”，如此就隐含了“所有的算法都具不可判定的性质”，这是一个观念上的大错误，如果一台计算机或算法不能肯定自己，就推翻了“可计算性”这个概念本身，“‘停机问题’不可判定”意味着——“可计算的”机器不能肯定自己的“可计算性”！就是说，“停机问题”这种悖论式的解释“判定问题”的代价，只是将问题推进到一个更深的缠绕层次。是故，只有当界定了“可计算性”之后，方可对其进行定量分析，这就是后来计算复杂性的“多项式时间（Polynomial time）”的来由和意义，。。。; 个人分类: 不确定性问题和算法讨论|3770 次阅读|11 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: circle－free

相关帖子

相关日志

关闭安全验证