如何通俗地解释图灵停机问题？

2020-05-21 11:01 作者:图灵社区 0人读过 | 我要投稿

昨天小编一如既往地在刷知乎，忽然刷到一个问题：

有哪些悖论一下子就吸引了你？

悖论嘛，大家都知道的，就是无解的问题嘛，于是小编作为“好奇心少年”果断点开了那个问题。

果然不出所料，第一个悖论就深深地吸引了我——色盲悖论。

这个悖论主要讲述的是：假如一个人属于色盲，无法分出蓝色和绿色，别人眼中的“蓝天”他看起来是“绿色”的，别人眼中的“绿色”草原，他看起来是“蓝色”草原，但是他和别人的叫法却都相同，依旧喊他们各自为“蓝天”和“绿草”，那么你是如何确定你不是这个人呢？？

看完这个悖论，我对自己深深地产生了怀疑！！

继续往下看，小编发现里面竟然还有一个悖论是罗素悖论！！！

众所周知，天才的罗素是个奇葩，他是数学出身居然凭借逻辑特长获得了诺贝尔文学奖，而这个天才提出的“罗素悖论”更是被称为“数学的一场严重危机”。

罗素悖论

注意：以下内容过于干货，非战斗人员请跳过直接看“理发师悖论”

罗素悖论，简单来说就是对一个集合而言，有两种不同的类别，一种是集合的全体元素里包含有集合自己。比如集合T定义为“全体非正方形物体组成的集合”，由于T本身是一个集合，不是正方形，所以T自己也应该作为一个元素包含在T中，这类集合叫做本身集合。另一种集合在其所有元素中不包含集合自身。这样的集合最为常见，例如全体整数组成的集合，全体女人组成的集合等等都不允许集合自身成为元素。此类集合叫做非本身集合。

如果假定S是自身的一个元素，则根据分类规定S是一个本身集合，而刚刚说过S的定义是全体非本身集合的集合，既然S是本身集合，所以S应该不是自身元素。这就出现了矛盾。这个两难问题便是罗素悖论。

怎么样？看完之后是不是觉得自己现在一头雾水，有没有一种大佬果然是大佬的拜服感？！

其实，罗素悖论还有一个简单通俗的描述方式：理发师悖论。

理发师悖论

在一座小岛上有位理发师, 有一天他做出一项规定: 他给岛上所有不自己理发的人理发，并且只给那些不给自己理发的人理发。

最初, 这个规定并没什么问题, 后来, 随着这个理发师自己的头发越来越长, 他发现自己陷入了一个两难的境地: 他该不该给自己理发?

如果他不为自己理发，按照他自定义的规则，他属于自己的服务客户范围，因此可以给自己理发；

如果他选择为自己理发，同样按照规则，他便不属于自己的服务对象，因此他又不能给自己理发。

综合以上两种情况, “他为自己理发”当且仅当“他不为自己理发”, 这成为了一个悖论。面对这个困惑的理发师究竟应该何去何从呢？To be or not to be, that is a question!

罗素悖论在很多领域有都普遍存在, 在计算机领域就有一个非常出名的例子——图灵停机问题。

图灵停机问题

写过程序的人一定知道一种痛苦，就是程序写好开始运行后等了半天毫无反应，既没有报错，又没有停止，让人不知所措。出现这种情况，一般有两种成因。一是程序运行的时间的确比较耗时，而编程人员又忘记编制任何运行中的动态提示功能，导致机器好像毫无反应。如果是这种情况，很好解决，只要增加运行中的屏幕提示，比如打印某个变量的状态或计算某种进度即可。但另一种情况会比较麻烦，就是程序执行陷入了死循环，永不停止。如果是这样，那么就必须跟踪查找死循环发生的位置并修改相应程序代码。

因此程序员们都期望能够有理论大牛发明一个判断程序来提前预报死循环是否会在程序中出现。把一段即将运行的代码作为字符串序列输入到该判断程序中，判断程序直接通过某种算法分析被输入程序的结构，并给出预报结果：该程序可以或不可以在有限时间内完成计算停止。这就是有名的停机判定问题。

这里说的有限时间是一种纯理论概念，一个算法即使所需执行时间要200亿年，超过宇宙的寿命，它在理论上也被认为是可停机的，也就是说“有限时间”无论是1秒还是100亿年，只要有终止的时候就可以称之为“在有限时间内结束运行”。

不失一般性, 假设我们想要测试的代码是一个函数

其中 t 是一个字符串, 我们可以用一个字符串表示任意输入, 包括 int, double, 及复合数据类型; 当 f 不需要输入时, t 是一个空字符串。停机问题是指对给定任意的一个函数 f 和输入 t, 判断f对t是否会永远运行下去; 如果程序的运行时间是有限长的, 我们称 f 对 t 停机。

遗憾的是, 不存在这样的一个工具使得其能判断任意 f 的停机问题, 即停机问题不可判定。

以下我们用反证法证明这个断言。假设存在这样的一个函数可用于判断停机问题：

其中 f_code 是我们要进行测试的函数 f 的 ASCII 源代码, 我们可以认为对 f_code 进行编译得到了函数 f。当 f 对 t 停机时, halts(f_code, t) 返回 true; 当 f 对 t 不停机, halts(f_code, t) 返回 false。

我们构造这样一个函数：

即当 f 对 f_code 停机时, 我们让 modified_halts 不停机; 当 f 对 f_code 不停机时, modified_code 停机。

假设 modified_halts 这个函数的 ASCII 源代码是 modified_halts_code, 如果我们把 modified_halts_code 作为 modified_halts 的输入会是什么情况?

若modified_halts对modified_halts_code停机, 说明halts(modified_halts_code, modified_halts_code)返回false, 说明modified_halts对modified_halts_code不停机;

若modified_halts对modified_halts_code不停机, 说明halts(modified_halts_code, modified_halts_code)返回true, 说明modified_halts对modified_halts_code停机。

综合以上两种情况, "modified_halts 对 modified_halts_code 停机"当且仅当 "modified_halts 对 modified_halts_code 不停机", 这是一个矛盾, 说明不存在这样一个 halts 函数可用于判断任意函数的可停机性。

以上这个证明利用的就是理发师悖论, modified_halts 函数就像是那位小岛上的理发师, 他对并且只对那些不停机的函数停机。当 modified_halts 函数面对他自己的函数代码时, 就像理发师该不该给他自己剪头发一样, 将陷入两难境地。

其实无论是停机问题，还是罗素悖论，亦或是理发师悖论，其本质上都是不可解问题，都属于数学中的内容。而数学在程序员编程的过程里一直都扮演着极为重要的作用。

程序员的数学

网上有一句话说的是“稍微扯上一点数学，现在的码农队伍起码缩水90%，大部分互联网码农都是欠缺数学知识的，与其称呼他们为码农，倒不如称呼他们为‘HTML文本构造文员’”。一个程序员想要获得更深的行业发展，数学知识是必不可少的！毕竟编程的基础是计算机科学，计算机科学的基础是数学。

最近比较火的AI/深度学习的编程，如果没有比较好的数学基础，你连理解什么是神经网络的基础都会有困难，更不要提如何去理解神经网络的优化等等问题了。因为你没有搞懂编程背后的数学底层逻辑，也就看不透问题背后的本质结构。

智力从来不是最重要的因素，思维才是。在一般的编程中，程序员通常不需要掌握很深奥的数学知识。但每一个程序员都要有此觉悟：我们是沟通人类世界和机器世界的翻译者，每一个问题，每一个需求的到来，最初的解决思路就是化繁为简，化不规则为规律，这样我们才能将人类世界的问题转换为机器世界能够理解和解决的问题，认清并简化问题结构，总结出具有一致性的规则等，透过现象看本质才是程序员真正的立身之本。

当然小编给你们介绍这些也不是让大家每个人都去再学习线性代数和微积分，数学的学习毕竟是一个循序渐进的过程，谁都不可能一口气吃个大胖子，但如果你想要补齐数学思维，那么建议大家可以先从《程序员的数学（第2版）》这本书开始学习。