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

博文

图灵1936年论文解读(3):“不停机”的circle-free

已有 4748 次阅读 2016-7-31 10:48 |个人分类:图灵论著专研与精译工作群|系统分类:科研笔记|关键词:学者| 停机问题, 判定问题, circle-free, 停机

在图灵1936年论文第二章,图灵用circle-free来定义“可计算数(Computable sequences and numbers)”,这个定义实际上是由二部份构成的,首先由circle-free来定义“可计算序列”,进一步由“可计算序列”定义“可计算数”。

按照图灵的定义:

A sequence is said to be computable if it can be computed by a circle-free machine. 一个序列被说成“可计算的”,如果能够通过一台“circle-free machine”计算而得。

A number is computable if it differs by an integer from the number computed by a circle-free machine. 一个数是可计算的,如果它与由“circle-free machine”计算的数只差一个整数。

我们以图灵所举的一个可计算序列:010101...为例来理解circle-free与“可计算序例”与“可计算数”的定义关系。图灵的意思是:一个可计算的数(A number is computable)只与circle-free计算的数(the number computed by a circle-free machine)相差一个整数,这就是指“小数”。因此,可计算序列“010101...”对应一个(可计算的)二进制无限循环小数“.010101...”,就是十进制小数:2^(-2)+2^(-4)+2^(-6)+ ...,即0.333...。

由这个实例的递进定义来理解图灵的“可计算数”是理解图灵论文的关键之一。无限循环小数表达了机器意义的“可计算数”的最大能力,这个最大能力是由(不停机的)circle-free的机器过程实现的。得到确定性的结果而“停机”只是circle-free的特殊情况,因此图灵并不是想由机器直接写出一个可计算数(而停机),“停机”是对已经存在的一台具体可计算机器而言,这正是把“停机问题”顶替“判定问题”所发生的对图灵1936年论文误读的原因。所以图灵并不关心“停机”,图灵所做的是揭示机器自身的机械步骤过程的算法性质,即机器化的“算法”——图灵机。

因此这和一般人观念中的机器的“可计算性”完全不同,通常认为,一台计算机器如果不输出最终结果而总是处于计算之中,则这台机器(算法)就进入了“死循环”,被认为是没有用的。产生这种差别的原因在于普通人只是把计算机当作一台现成的计算工具使用,而图灵是计算机器的建造师,他只有首先保证机器具有无限的运行能力(circle-free),然后才有可能让机器“停机”而得到某个解。




https://m.sciencenet.cn/blog-2322490-993665.html

上一篇:图灵1936年论文解读(2):可计算数
下一篇:介绍一个求解SAT问题的程序SatZ(2)-k-SAT实例生成器

2 杨正瓴 xlianggg

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

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

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

GMT+8, 2024-4-18 13:14

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部