这个问题，计算机就算想破了脑袋也解决不了
李世石会告诉你，以阿尔法狗为代表的人工智能在许多方面已经比人类强很多了。但是，有些问题计算机永远也找不到答案。
比如，一个程序有没有 bug，运行时会不会导致卡机？不管计算机多聪明，它们就是想破了脑袋，也解答不了这个问题。
这就是计算机学里著名的问题——停机问题（the halting problem）。1936 年，人工智能之父艾伦·图灵就对停机问题进行了证明。
就是这个人
IBM 研究实验室的机器学习专家 Udi Aharoni 根据图灵的证明方法制作了清晰易懂的动画，我们一起来看看吧。
请自动忽略里面绿豆苗体型和金属朋克发型的火柴人。
如何证明计算机并不能解答所有问题。
第一幕：一些问题计算机处理起来得心应手。
这是计算机小A，小A会做算数题。只要把问题打印在纸上，然后让它扫描一下，小A就可以把答案打印出来。
而且，小A总是能得到正确的答案，比小学生靠谱多了。
这是计算机小C。小C会下象棋。只要拿棋盘让它扫描一下，小C就可以打印出必胜的走法。
小C和阿尔法狗一样，甚至比狗更厉害，玩象棋玩得贼溜，从来没有输过。
实际上，我们现在已经能造出小A和小C这样强大的计算机了。而且随着人工智能的发展，计算机会变得比小A和小C还要聪明能干。
所以，最终以小A和小C为代表的计算机什么事都能干成吗？它们可以代替人类吗？
emmm，其实，人类已经知道有一类问题，计算机永远也算不出答案。
第二幕：停机问题
我们把一张绘制着象棋棋盘的纸让小A扫描。因为小A的技能不是算象棋的走法，所以它会卡机。
同理，如果让小C去算算数题，它也会卡机。
我们把小A的制造蓝图画出来，这个蓝图包含着小A的所有逻辑电路。只要拿着这张蓝图，就可以原样造出一台小A出来。
现在，我们来做一个新的智能计算机——小H。
小H的技能就是算停机问题。
具体来说，只要把其他计算机的蓝图，还有那台计算机需要扫描的问题（输入的信息）让小H扫描一下，它就可以悄默默地比对蓝图和输入信号是否匹配，然后得出那台倒霉的计算机会不会卡顿的结论，最后把结果打印出来。
比如，让它来算小C的蓝图和算数题，就会得出“卡”的结论。
让它来算小C的蓝图和象棋题，就会得出“不卡”的结论。
让它来算小A的蓝图和象棋题，就会得出“卡”的结论。
让它来算小A的蓝图和算数题，就会得出“不卡”的结论。
真的有小H这样的计算机存在吗？
让我们从逻辑上来兴高采烈地证明一下，小H根本造不出来吧。
第三幕：小H根本不存在。
我们用反证法来试一试。
假设小H存在，而且它战无不胜。那我们来把它和其他计算机组装一下。
这是一台处于人工智能鄙视链底端的复印机小P，因为小P只会复印。把问题输入，它就原样输出两份。
把小P和小H组合起来，让小P输出的内容直接变成小H的输入内容。像是这样——
然后我们再搞来一台计算机，叫做小N。
小N是个病娇，不管人家告诉它什么，它都会说反话。
比如，要是输入“不卡”，它就会卡机。
要是输入“卡”，它就输出“不卡”。
你问这样的反社会计算机怎么能存在？因为我们不是假设能干任何事的计算机存在嘛，所以病娇计算机也存在咯，然后我们就用它的矛去 KO 它的盾咯。
好的，我们把小N和小H还有小P组合在一起，让小P的输出内容变成小H的输入内容，让小H的输出内容变成小N的输入内容。
好了，一个复读机病娇人工智障天团就闪亮登场了。
我们给这个天团取名为小X天团，给它们包装一下，搞个高端大气上档次的套子套起来。
小X天团虽然吨位大，名字中二，但是也是一个正经计算机来的，它有一个输入口（小P的），还有一个输出口（小N的）。
我们把小X的蓝图画出来。
现在，如果把小X天团的蓝图给小X自己，让它算，会出现什么结果呢？它会卡机吗？
我们一步一步来看。
小P把蓝图复印成了两份，吐给了小H。
小H吃进了这 2 份蓝图以后，假设小H输出“不卡”。
好，那么小N就得到了“不卡”的输入。
因为小N是病娇嘛，所以它会卡机。所以，小X天团就卡机了。
但是小H却说，小X天团不会卡。那么小H的结论不就和事实矛盾了嘛？
好的，那么我们现在反过来，假设小H输出“卡”。
那么小N就会输出“不卡”，也就是说小X天团也输出“不卡”。
最终，事实还是和小H的结论相反，小H又一次失败了。
这么一来，我们就可以证明，小H这样的计算机是不可能存在的。多年后，小H的死因报告显示：存在感太低。
停机问题说明，计算机不是万能的。
类似的计算机不能解决的问题还有很多，它们都属于不可判定问题。
图灵在 80 多年前就给了人类一个对抗图灵机的护身符——如果被 NB 的图灵机逼到了墙角，马上让它算不可判定问题，它就会开始怀疑机生。
这一幕也在《攻壳机动队 STAND ALONE COMPLEX》里被还原了，萌萌哒塔奇克马盗窃团伙顺利采用不可验证问题使低版本的 AI 宕机。
有些小朋友会问，停机问题就算被图灵证出来了又怎样啊，在现实生活中有应用嘛？
当然有啊。
比如，停机问题可以用来证明......没法靠计算机来验证哥德巴赫猜想，要证明哥德巴赫猜想还得靠人脑。
哥德巴赫猜想指的是，
任一大于 2 的偶数，都可表示成两个素数之和。
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7
…
如果存在小H这样的计算机，那么就可以让它来判断，寻找哥德巴赫猜想的反例的计算机程序是会永远跑下去，还是会在某处停止。
如果小H判断，这个程序会在某处停止，那就说明这个程序能找到反例，那么哥德巴赫猜想就被证伪。
反之，如果小H判断，这个程序将会永远运行下去不会停止，那也就是说永远也找不到哥德巴赫猜想的反例，那么哥德巴赫猜想就被证明了。
同理，小H还可以被用来验证各种数学命题是否为真，简直不要太好用，数学家从此集体失业，人类历史上所有还没有被证明的数学猜想都将迎刃而解。
当然了，停机问题还能证明，计算机自动编程啊，计算机自己找 bug 啊......统统都是做梦！做梦！
光靠瞎想一时爽，图灵冷水泪两行。
本文来自公众号：把科学带回家（ID：steamforkids），作者：Udi Aharoni 等，编译：七君