計(jì)算機(jī)也有“為難”的時(shí)候

李世石會(huì)告訴你，以阿爾法狗為代表的人工智能在許多方面已經(jīng)比人類強(qiáng)很多了。但是，有些問(wèn)題計(jì)算機(jī)永遠(yuǎn)也找不到答案。

比如，一個(gè)程序有沒(méi)有bug，運(yùn)行時(shí)會(huì)不會(huì)導(dǎo)致卡機(jī)？不管計(jì)算機(jī)多聰明，它們就是想破了腦袋，也解答不了這個(gè)問(wèn)題。

這就是計(jì)算機(jī)學(xué)里著名的問(wèn)題——停機(jī)問(wèn)題（the halting problem）。1936年，人工智能之父艾倫·圖靈就對(duì)停機(jī)問(wèn)題進(jìn)行了證明。

就是這個(gè)人

IBM 研究實(shí)驗(yàn)室的機(jī)器學(xué)習(xí)專家 Udi Aharoni 根據(jù)圖靈的證明方法制作了清晰易懂的動(dòng)畫，我們一起來(lái)看看吧。

請(qǐng)自動(dòng)忽略里面綠豆苗體型和金屬朋克發(fā)型的火柴人。

如何證明計(jì)算機(jī)并不能解答所有問(wèn)題。

這是計(jì)算機(jī)小A，小A會(huì)做算數(shù)題。只要把問(wèn)題打印在紙上，然后讓它掃描一下，小A就可以把答案打印出來(lái)。

而且，小A總是能得到正確的答案，比小學(xué)生靠譜多了。

這是計(jì)算機(jī)小C。小C會(huì)下象棋。只要拿棋盤讓它掃描一下，小C就可以打印出必勝的走法。

小C和阿爾法狗一樣，甚至比狗更厲害，玩象棋玩得賊溜，從來(lái)沒(méi)有輸過(guò)。

實(shí)際上，我們現(xiàn)在已經(jīng)能造出小A和小C這樣強(qiáng)大的計(jì)算機(jī)了。而且隨著人工智能的發(fā)展，計(jì)算機(jī)會(huì)變得比小A和小C還要聰明能干。

所以，最終以小A和小C為代表的計(jì)算機(jī)什么事都能干成嗎？它們可以代替人類嗎？

emmm，其實(shí)，人類已經(jīng)知道有一類問(wèn)題，計(jì)算機(jī)永遠(yuǎn)也算不出答案。

我們把一張繪制著象棋棋盤的紙讓小A掃描。因?yàn)樾的技能不是算象棋的走法，所以它會(huì)卡機(jī)。

同理，如果讓小C去算算數(shù)題，它也會(huì)卡機(jī)。

我們把小A的制造藍(lán)圖畫出來(lái)，這個(gè)藍(lán)圖包含著小A的所有邏輯電路。只要拿著這張藍(lán)圖，就可以原樣造出一臺(tái)小A出來(lái)。

現(xiàn)在，我們來(lái)做一個(gè)新的智能計(jì)算機(jī)——小H。

小H的技能就是算停機(jī)問(wèn)題。

具體來(lái)說(shuō)，只要把其他計(jì)算機(jī)的藍(lán)圖，還有那臺(tái)計(jì)算機(jī)需要掃描的問(wèn)題（輸入的信息）讓小H掃描一下，它就可以悄默默地比對(duì)藍(lán)圖和輸入信號(hào)是否匹配，然后得出那臺(tái)倒霉的計(jì)算機(jī)會(huì)不會(huì)卡頓的結(jié)論，最后把結(jié)果打印出來(lái)。

比如，讓它來(lái)算小C的藍(lán)圖和算數(shù)題，就會(huì)得出“卡”的結(jié)論。

讓它來(lái)算小C的藍(lán)圖和象棋題，就會(huì)得出“不卡”的結(jié)論。

讓它來(lái)算小A的藍(lán)圖和象棋題，就會(huì)得出“卡”的結(jié)論。

讓它來(lái)算小A的藍(lán)圖和算數(shù)題，就會(huì)得出“不卡”的結(jié)論。

真的有小H這樣的計(jì)算機(jī)存在嗎？

讓我們從邏輯上來(lái)興高采烈地證明一下，小H根本造不出來(lái)吧。

我們用反證法來(lái)試一試。

假設(shè)小H存在，而且它無(wú)戰(zhàn)不勝。那我們來(lái)把它和其他計(jì)算機(jī)組裝一下。

這是一臺(tái)處于人工智能鄙視鏈底端的復(fù)印機(jī)小P，因?yàn)樾只會(huì)復(fù)印。把問(wèn)題輸入，它就原樣輸出兩份。

把小P和小H組合起來(lái)，讓小P輸出的內(nèi)容直接變成小H的輸入內(nèi)容。像是這樣——

然后我們?cè)俑銇?lái)一臺(tái)計(jì)算機(jī)，叫做小N。

小N是個(gè)病嬌，不管人家告訴它什么，它都會(huì)說(shuō)反話。

比如，要是輸入“不卡”，它就會(huì)卡機(jī)。

要是輸入“卡”，它就輸出“不卡”。

你問(wèn)這樣的反社會(huì)計(jì)算機(jī)怎么能存在？因?yàn)槲覀儾皇羌僭O(shè)能干任何事的計(jì)算機(jī)存在嘛，所以病嬌計(jì)算機(jī)也存在咯，然后我們就用它的矛去KO它的盾咯。

好的，我們把小N和小H還有小P組合在一起，讓小P的輸出內(nèi)容變成小H的輸入內(nèi)容，讓小H的輸出內(nèi)容變成小N的輸入內(nèi)容。

好了，一個(gè)復(fù)讀機(jī)病嬌人工智障天團(tuán)就閃亮登場(chǎng)了。

我們給這個(gè)天團(tuán)取名為小X天團(tuán)，給它們包裝一下，搞個(gè)高端大氣上檔次的套子套起來(lái)。

小X天團(tuán)雖然噸位大，名字中二，但是也是一個(gè)正經(jīng)計(jì)算機(jī)來(lái)的，它有一個(gè)輸入口（小P的），還有一個(gè)輸出口（小N的）。

我們把小X的藍(lán)圖畫出來(lái)。

現(xiàn)在，如果把小X天團(tuán)的藍(lán)圖給小X自己，讓它算，會(huì)出現(xiàn)什么結(jié)果呢？它會(huì)卡機(jī)嗎？

我們一步一步來(lái)看。

小P把藍(lán)圖復(fù)印成了兩份，吐給了小H。

小H吃進(jìn)了這2份藍(lán)圖以后，假設(shè)小H輸出“不卡”。

好，那么小N就得到了“不卡”的輸入。

因?yàn)樾是病嬌嘛，所以它會(huì)卡機(jī)。所以，小X天團(tuán)就卡機(jī)了。

但是小H卻說(shuō)，小X天團(tuán)不會(huì)卡。那么小H的結(jié)論不就和事實(shí)矛盾了嘛？

好的，那么我們現(xiàn)在反過(guò)來(lái)，假設(shè)小H輸出“卡”。

那么小N就會(huì)輸出“不卡”，也就是說(shuō)小X天團(tuán)也輸出“不卡”。

最終，事實(shí)還是和小H的結(jié)論相反，小H又一次失敗了。

這么一來(lái)，我們就可以證明，小H這樣的計(jì)算機(jī)是不可能存在的。多年后，小H的死因報(bào)告顯示：存在感太低。

停機(jī)問(wèn)題說(shuō)明，計(jì)算機(jī)不是萬(wàn)能的。

類似的計(jì)算機(jī)不能解決的問(wèn)題還有很多，它們都屬于不可判定問(wèn)題。

圖靈在80多年前就給了人類一個(gè)對(duì)抗圖靈機(jī)的護(hù)身符——如果被NB的圖靈機(jī)逼到了墻角，馬上讓它算不可判定問(wèn)題，它就會(huì)開(kāi)始懷疑機(jī)生。

這一幕也在《攻殼機(jī)動(dòng)隊(duì)STAND ALONE COMPLEX》里被還原了，萌萌噠塔奇克馬盜竊團(tuán)伙順利采用不可驗(yàn)證問(wèn)題使低版本的AI宕機(jī)。

有些小朋友會(huì)問(wèn)，停機(jī)問(wèn)題就算被圖靈證出來(lái)了又怎樣啊，在現(xiàn)實(shí)生活中有應(yīng)用嘛？

當(dāng)然有啊。

比如，停機(jī)問(wèn)題可以用來(lái)證明...沒(méi)法靠計(jì)算機(jī)來(lái)驗(yàn)證哥德巴赫猜想，要證明哥德巴赫猜想還得靠人腦。

哥德巴赫猜想指的是，

4 = 2 + 2

6 = 3 + 3

8 = 3 + 5

10 = 3 + 7 = 5 + 5

12 = 5 + 7

14 = 3 + 11 = 7 + 7

…

如果存在小H這樣的計(jì)算機(jī)，那么就可以讓它來(lái)判斷，尋找哥德巴赫猜想的反例的計(jì)算機(jī)程序是會(huì)永遠(yuǎn)跑下去，還是會(huì)在某處停止。

如果小H判斷，這個(gè)程序會(huì)在某處停止，那就說(shuō)明這個(gè)程序能找到反例，那么哥德巴赫猜想就被證偽。

反之，如果小H判斷，這個(gè)程序?qū)?huì)永遠(yuǎn)運(yùn)行下去不會(huì)停止，那也就是說(shuō)永遠(yuǎn)也找不到哥德巴赫猜想的反例，那么哥德巴赫猜想就被證明了。

同理，小H還可以被用來(lái)驗(yàn)證各種數(shù)學(xué)命題是否為真，簡(jiǎn)直不要太好用，數(shù)學(xué)家從此集體失業(yè)，人類歷史上所有還沒(méi)有被證明的數(shù)學(xué)猜想都將迎刃而解。

當(dāng)然了，停機(jī)問(wèn)題還能證明，計(jì)算機(jī)自動(dòng)編程啊，計(jì)算機(jī)自己找bug啊...統(tǒng)統(tǒng)都是做夢(mèng)！做夢(mèng)！

光靠瞎想一時(shí)爽，圖靈冷水淚兩行。