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

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

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

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

就是這個(gè)人

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

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

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

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

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

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

小C和阿爾法狗一樣，甚至比狗更厲害，玩象棋玩得賊溜，從來沒有輸過。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我們用反證法來試一試。

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

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

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

然后我們再搞來一臺計(jì)算機(jī)，叫做小N。

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

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

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

你問這樣的反社會計(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)就閃亮登場了。

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

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

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

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

我們一步一步來看。

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

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

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

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

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

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

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

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

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

停機(jī)問題說明，計(jì)算機(jī)不是萬能的。

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

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

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

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

當(dāng)然有啊。

比如，停機(jī)問題可以用來證明...沒法靠計(jì)算機(jī)來驗(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ī)，那么就可以讓它來判斷，尋找哥德巴赫猜想的反例的計(jì)算機(jī)程序是會永遠(yuǎn)跑下去，還是會在某處停止。

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

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

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

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

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