這個問題，計算機就算想破了腦袋也解決不了
本文由公眾號 「把科學帶回家」 提供
給孩子最好的科學教育
作者 Udi Aharoni等
編譯 七君
李世石會告訴你，以阿爾法狗為代表的人工智慧在許多方面已經比人類強很多了。但是，有些問題計算機永遠也找不到答案。
比如，一個程序有沒有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
給孩子最好的科學教育
轉載請聯繫 kids@huanqiukexue.com
長按二維碼關注我們
圖片非特別註明均來自網路。
為保護原創，參考資料儲存於石墨：
https://shimo.im/docs/GHOrdqgBHxMQS9PD/
TAG:把科學帶回家 |