這個問題，計算機就算想破了腦袋也解決不了
李世石會告訴你，以阿爾法狗為代表的人工智能在許多方面已經比人類強很多了。但是，有些問題計算機永遠也找不到答案。
比如，一個程序有沒有 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 等，編譯：七君