機械性計算的直觀
涂靈有下午長跑的習慣。根據後來他告訴好友甘迪(Robin Gandy, 1919~1995)的說法, 1935 年的初夏,在一次長跑途中暫時休息時,他躺在Grantchester 的草地上突然靈光一閃,想出一種「機械程序」解決希爾伯特的第三個問題。他把這項劃時代的創見寫成著名的論文“On computable numbers,with an application to the Entscheidungsproblem”(以下簡稱〈論數〉)。
涂靈在〈論數〉第一節就引進後人稱為「涂靈機」的定義,並且作了一系列的推導。用他的機器計算出來的數,當然符合直觀認為是可計算的數。到了第9節,涂靈提出一個一般性的問題:「有哪些可能的程序可以用來計算數?」他要用三類論述法說明自己設計的機器足夠計算所有直觀認為可算的數:
(a) 直接訴諸直觀。
(b) 如果有任何別的方法更形直觀,則證明與涂靈機等價。
(c) 盡量給出實例,顯示大量的數都是可用涂靈機計算的。
涂靈針對(a)所作的論述,風格與一般數學論文大相逕庭。他模擬兒童的算術作業簿,把紙面劃分成方格,只不過把方格改成一直線排列開。方格內允許書寫的符號只准有限種,因為他說「如果我們允許無窮多種符號的話,則有些符號之間的差異會任意的渺小。」然後涂靈分析任何一個計算者(他當時用的稱呼是computer)的行為,應該會取決於當下看到方格裡的符號,以及計算者的「心靈狀態」(state of mind)。涂靈認為心靈狀態也只有有限多種,因為「如果我們允許有無窮多種心靈狀態,有些就會『任意地接近』,以致於產生混淆。」涂靈在此節的末段,還說計算者可隨時離開去做別的事,但是如果他還想回來繼續工作,他就必須寫下一張記錄表,記好當時機器的整體狀態,以便可以依照指示重新啟動計算。總之,這些生動的直觀式分析,讓我們理解涂靈定義他的機器的動機。
在涂靈之前,對於數學系統裡機械化的過程,已經有別人提出各種模式。譬如,哥德爾提出一般遞迴函數(general recursive function),丘奇(Alonzo Church,1903~1995)提出蘭布達演算(lambda calculus)。這些外貌差異甚大的各種模式,其實都計算出同樣的自然數的函數。丘奇甚至在1935 年4 月19 日美國數學會的研討會上公開宣稱,所有直觀上認為可以明確計算的函數,都已歸屬於一般遞迴函數了。這就成為有名的丘奇論點(Church ‘s Thesis)。這個論點不屬於一般數學裡的猜想(conjecture),因為它涉及無法嚴格定義的直觀概念,所以也無從加以證明,只能盡量舉出實例當做證據,這種狀況類似自然科學裡須用大量的實驗來支持定律。