这个问题,计算机就算想破了脑袋也解决不了

OPEN编辑 2年前

这个问题,计算机就算想破了脑袋也解决不了

  李世石会告诉你,以阿尔法狗为代表的人工智能在许多方面已经比人类强很多了。但是,有些问题计算机永远也找不到答案。

  比如,一个程序有没有 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 等,编译:七君