【科學松鼠會】計算的極限（一）：所有機器的機器，與無法計算的問題

計算無處不在。

走進一個機房，在服務器排成的一道道墻之間，聽著風扇的鼓噪，似乎能嗅出0和1在CPU和內存之間不間斷的流動。從算籌算盤，到今天的計算機，我們用作計算的工具終于開始量到質的飛躍。計算機能做的事情越來越多，甚至超越了它們的制造者。上個世紀末，深藍憑借前所未有的搜索和判斷棋局的能力，成為第一臺戰勝人類國際象棋世界冠軍的計算機，但它的勝利仍然仰仗于人類大師賦予的豐富國際象棋知識；而僅僅十余年后，Watson卻已經能憑借自己的算法，先“理解”問題，然后有的放矢地在海量的數據庫中尋找關聯的答案。長此以往，工具將必在更多的方面超越它的制造者。而這一切，都來源于越來越精巧的計算。

計算似乎無所不能，宛如新的上帝。但即使是這位“上帝”，也逃不脫邏輯設定的界限。

第一位發現這一點的，便是圖靈。

計算的極限（零）：邏輯與圖靈機

所有機器的機器

圖靈機非常簡單，只要明白了它的運作過程，任何一個受過足夠訓練的計算機系本科生都可以寫出一個模擬圖靈機運行的程序。只消輸入狀態轉移表和紙帶的輸入內容，程序就可以一步一步模擬相應的圖靈機在紙帶上爬來爬去的過程。對于一些熟悉圖形編程的程序員來說，做個模擬動畫也問題不大。即使不用計算機，靠人手一步步操作，也是一件小孩子也能完成的事。圖靈機就是這么簡單的一種機器。

雖然看上去簡單，但實際上圖靈機能做的事情遠遠超出一般的想象。只要有足夠長的紙帶和足夠好的耐心，今天的電腦能做的計算，一臺精心設計的圖靈機也能完成。訣竅在于，電腦中的電路是有限的，電路的狀態也是有限的，我們可以用圖靈機去模擬電腦中的電路狀態。只要有足夠長的紙帶，那就可以模擬出足夠大的寄存器、內存和硬盤；而CPU中的電路，雖然所有可能的狀態極其多，但終究是有限的，可以用圖靈機模擬，雖然這臺圖靈機的狀態轉移表將會有著令人頭痛的大小