电脑人心 之 计算机能思维吗?(二)图灵的机器(4)停机问题
已有 6914 次阅读
2010-9-28 06:20
|个人分类:电脑人心|系统分类:科普集锦|
人工智能, 认知科学, 图灵, 可能性, 电脑人心
前面说到图灵机可以做一些很有用的事情,比如咱们讨论过的奇偶校验,再比如计算圆周率。那么,图灵机究竟能做多少事情呢?
先来看看图灵机的所谓“通用性”(universality)。“通用性”是不是意味着图灵机可以做任何事情呢?不是。因为,正如我们上次说过的,“通用性”并不是说一台“通用图灵机”(universal Turing machine)能够做所有的事情,而是说它跟任何其他图灵机指令表的编码结合起来,可以做那台图灵机本来做的事情。这就意味着,如果有某个任务,我们不可能构造出任何图灵机──就是说构造出适当的指令表──来完成,那么这个任务自然也就是通用图灵机也不能完成的了。
那么,究竟是不是人们能够想到的一切计算任务,都可以构造某台图灵机来完成呢?图灵1936年的文章证明了这是不行的。就是说,存在着严格定义的计算任务或者问题,它是任何图灵机都不能完成的。图灵当时讨论了一个问题,是后来被叫做“停机问题”(halting problem)的一个变形。下面俺非正式地介绍一下停机问题。
会编程序的朋友都知道,一个程序在运行时有可能进入所谓“死循环”,就是说程序反复不停地做一些事情,一遍又一遍,没完没了,让它停止执行的条件永远得不到满足。“死循环”是程序设计中常见的“臭虫”之一。那么,大家可能会想,能不能构造一个程序,叫做“死循环检测器”,这个程序,以任何程序P及其任何输入S为输入──就像“通用图灵机”那样──然后告诉你P在S下会不会运行到一个死循环,而永远停不下来。如果能够造出这样的“死循环检测器”,那么程序调试就会方便很多。图灵证明了“停机问题”不可解,也就排除了构造出这样的“死循环检测器”的可能性。
稍微形式化一点,所谓“停机问题”是说,是否存在一个图灵机,我们可以把它叫做H,它实现这么一种判定程序:给定任何图灵机M和任何输入m,H总是会就M在m输入下会不会停机给出肯定或者否定的正确答案。
请注意,所谓“停机问题”不是说,图灵机出问题了。不是像“最近酒后驾车的问题很严重”那种问题,那种坏现象。“停机问题”就像“能不能造出‘死循环检测器’呢?”那样,是一项任务,一种期望。所谓“停机问题不可解”,就是说不存在H那样的图灵机,就像不可能造出‘死循环检测器’那样。
下面来看看如何用反证法来论证这种不可能性。
假定H存在,或者说可以构造出来,这就是说H的行为大致可以用如下的伪代码来表示:
H(M, m)
{
如果M在输入m下停机,那么
打印“停机”
否则
打印“不停机”
}
这里H(M, m)的意思就是说H接受M和m为输入。
那么,以H为基础,我们可以构造另一个图灵机,可以叫做E,它的行为如下
E(n)
{
如果H(n, n)打印“停机”,那么
反复执行
打印“不停机”
直到1等于2
否则
打印“停机”
}
由于1永远也不会等于2,所以E的构造里面有个死循环,一旦进到那里,就再也出不来,不停地打印“不停机”。而进入那个死循环的条件呢,就是H(n,n)打印“停机”。根据H的定义,这也就是说编码为n的图灵机,在以自己的编码n为输入的情况下会停机。
既然,E也是一个图灵机,那么它就可以有它相应的编码。我们讨论在通用图灵机时说过的,任何一个图灵机都可以被编码,然后该编码可以被用作图灵机的输入。那么,E也就自然有它的编码,我们把这个编码叫做e。那么,当E以e为输入时,就是执行E(e)时,情况会怎样呢?
根据E的构造,E(e)只有两种可能。要么是情况(甲):进入死循环,不停地打印“不停机”,运行永远也不结束;要么是情况(乙):打印一次“停机”然后就结束。
假定是情况(甲)或者说死循环,那么根据E的构造,H(e,e)打印的是“停机”。前面提到过,按照H的定义,这也就是说编码为e的那个图灵机──就是E!──在输入为e时会停机,或者说E(e)会停机。这就跟这里假定的(甲)刚好矛盾了。
假定是情况(乙)或者说打印一次就停机,那么根据E的构造,H(e,e)打印的是“不停机”。按照H的定义,这也就是说E在输入e下面不停机,亦即E(e)不停机,这就和这里假定的(乙)刚好矛盾了。
既然E(e)出现其仅有的两种可能行为中的任何一种都导致矛盾,那么我们最初关于H可以构造出来的假定必然是错的。这样我们就证明了不可能构造出一个H,给它任何其他图灵机M的编码和输入m,它都能告诉我们M在输入m下是否会停机。就是说,我们证明了停机问题不可解。
在说明了停机问题(的一种变形)不可解之后,图灵在论文中把判定问题规约为停机问题,从而作为图灵机理论的一个“应用”,证明了判定问题不可解,从而跟丘奇一样,否定性地回答了希尔伯特和艾克曼的问题:不存在一般性的判定过程,能够从形式化了的算术系统里的命题出发,就该命题是否为真或者是否可证给出确定的答案。
https://blog.sciencenet.cn/blog-453866-367655.html
上一篇:
暑期学校信息:圣菲(复杂系统)和维也纳(科学证据的本性)下一篇:
强烈建议媒体报道科学网博客上关于方肖之争的讨论