博文
电脑人心 之 计算机能思维吗？（二）图灵的机器（4）停机问题
|||
前面说到图灵机可以做一些很有用的事情，比如咱们讨论过的奇偶校验，再比如计算圆周率。那么，图灵机究竟能做多少事情呢？
先来看看图灵机的所谓“通用性”（universality）。“通用性”是不是意味着图灵机可以做任何事情呢？不是。因为，正如我们上次说过的，“通用性”并不是说一台“通用图灵机”（universal Turing machine）能够做所有的事情，而是说它跟任何其他图灵机指令表的编码结合起来，可以做那台图灵机本来做的事情。这就意味着，如果有某个任务，我们不可能构造出任何图灵机──就是说构造出适当的指令表──来完成，那么这个任务自然也就是通用图灵机也不能完成的了。
那么，究竟是不是人们能够想到的一切计算任务，都可以构造某台图灵机来完成呢？图灵1936年的文章证明了这是不行的。就是说，存在着严格定义的计算任务或者问题，它是任何图灵机都不能完成的。图灵当时讨论了一个问题，是后来被叫做“停机问题”（halting problem）的一个变形。下面俺非正式地介绍一下停机问题。
会编程序的朋友都知道，一个程序在运行时有可能进入所谓“死循环”，就是说程序反复不停地做一些事情，一遍又一遍，没完没了，让它停止执行的条件永远得不到满足。“死循环”是程序设计中常见的“臭虫”之一。那么，大家可能会想，能不能构造一个程序，叫做“死循环检测器”，这个程序，以任何程序P及其任何输入S为输入──就像“通用图灵机”那样──然后告诉你P在S下会不会运行到一个死循环，而永远停不下来。如果能够造出这样的“死循环检测器”，那么程序调试就会方便很多。图灵证明了“停机问题”不可解，也就排除了构造出这样的“死循环检测器”的可能性。
稍微形式化一点，所谓“停机问题”是说，是否存在一个图灵机，我们可以把它叫做H，它实现这么一种判定程序：给定任何图灵机M和任何输入m，H总是会就M在m输入下会不会停机给出肯定或者否定的正确答案。
请注意，所谓“停机问题”不是说，图灵机出问题了。不是像“最近酒后驾车的问题很严重”那种问题，那种坏现象。“停机问题”就像“能不能造出‘死循环检测器’呢？”那样，是一项任务，一种期望。所谓“停机问题不可解”，就是说不存在H那样的图灵机，就像不可能造出‘死循环检测器’那样。
下面来看看如何用反证法来论证这种不可能性。
假定H存在，或者说可以构造出来，这就是说H的行为大致可以用如下的伪代码来表示：
这里H(M, m)的意思就是说H接受M和m为输入。
那么，以H为基础，我们可以构造另一个图灵机，可以叫做E，它的行为如下
由于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
上一篇：暑期学校信息：圣菲（复杂系统）和维也纳（科学证据的本性）
下一篇：强烈建议媒体报道科学网博客上关于方肖之争的讨论
先来看看图灵机的所谓“通用性”（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下停机，那么
打印“停机”
否则
打印“不停机”
}
{
如果M在输入m下停机，那么
打印“停机”
否则
打印“不停机”
}
这里H(M, m)的意思就是说H接受M和m为输入。
那么，以H为基础，我们可以构造另一个图灵机，可以叫做E，它的行为如下
E(n)
{
如果H(n, n)打印“停机”，那么
反复执行
打印“不停机”
直到1等于2
否则
打印“停机”
}
{
如果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
上一篇：暑期学校信息：圣菲（复杂系统）和维也纳（科学证据的本性）
下一篇：强烈建议媒体报道科学网博客上关于方肖之争的讨论
