初等數論中的一個不可解問題
有些是非問題，任何程序都永遠答不出。
有些問題聽起來再清楚不過——是，還是否？——可邱奇卻證明了：沒有任何配方、任何機器、任何程序，能夠回答得了它們。
核心想法
在你能問出「是不是每個問題都能照著配方解出來」之前，你得先把「配方」究竟是什麼釘死。邱奇造出了一門盡可能小的「配方語言」——λ-演算，它只有一個動作：拿一個函數，餵給它一個輸入，然後替換。接著他提議：凡是我們直覺上會稱作「可計算」的東西，恰恰就是這門小語言所能表達的。這個大膽的等式，如今被稱為「邱奇論題」。
當「計算」終於被說清楚，他就能問出一個更鋒利的問題——並得到一個驚人的答案。他找到了一個用純粹數學語言陳述的問題，它的答案總是非是即否，然而沒有任何程序，能在每一種情形下都給出正確的答案。不是「我們還沒找到」，而是「它不可能存在」。這是真正嶄新的東西：一個被證明超出一切方法之外的問題。
它是如何誕生的
1920 年代，偉大的數學家大衛·希爾伯特立下了一份綱領：把全部數學安放在一個穩固到——原則上——可以用一套機械程序去判定任何命題真假的根基之上。那是一個對「整潔、可被徹底知曉的數學」滿懷信心的夢。然後，1930 年代把它拆了個稀爛。1931 年，庫爾特·哥德爾證明：沒有任何一致的系統能證明關於算術的全部真理。幾年後，在普林斯頓工作的阿隆佐·邱奇，瞄準了希爾伯特那夢想的剩餘部分——「判定問題」。
為了攻它，邱奇和他的學生斯蒂芬·克萊尼、J·巴克利·羅瑟，花了多年發展 λ-演算。克萊尼證明它所計算的函數，與另一種對手定義（「遞迴」函數）所計算的恰好相同，這份吻合，給了邱奇底氣去宣布「可計算性」究竟是什麼。數月之後，一位名不見經傳的英國年輕人——艾倫·圖靈——從一個全然不同的方向撞上了同一堵牆：他設想出一台讀紙帶的簡單機器；而兩邊的答案，結果竟是同一個。他們合起來的裁決，便是邱奇–圖靈論題。
它為何重要
這裡，正是電腦科學拿到其根基之處——比第一台電子計算機還早了幾十年。透過把「計算」究竟意味著什麼說清楚，邱奇讓人得以嚴格地證明：電腦能做什麼、又不能做什麼。而被證明的頭一件事，便是一道極限：有些問題提得明明白白，卻沒有任何程序能夠了結它們。每當一個工具說，它一般而言無法判斷你的程式會不會崩潰、會不會陷入死迴圈，它撞上的，正是邱奇在 1936 年劃下的那道邊界。
一個可以想像的畫面
想想一份菜譜：一串有限的、毫不含糊的步驟，一位有耐心的廚師無須任何機靈就能照做，每次都做出同一道菜。邱奇的主張是：「可計算」恰恰意味著「有這樣一份菜譜」。現在，想像一個問題：「照著這份菜譜做下去，到底會不會真正做完？」對某些菜譜，你一眼就看得出答案；但邱奇證明了：不存在一份「萬能菜譜」，能在拿到任意一份菜譜時，總是正確地告訴你它會不會做完。這位檢查者得勝過每一份菜譜，包括那些巧妙地自我指涉的——而沒有任何菜譜辦得到這一點。
它的位置
邱奇的這篇論文，是一組非凡三重奏的一角。哥德爾（已在本館中）證明了真理跑在證明之前；邱奇證明了「可解性」自有其堅硬的極限；而艾倫·圖靈，在同一年，用他設想的機器重鑄了同一道邊界——那是此後每一台計算機的藍圖。把這三者合起來讀，1930 年代的它們，描繪出了「推理與機械所能為」的外緣。從香農的資訊論到今天的軟體，一切都活在它們圈出的那片空間之內。
引言——這個問題
那個定義（邱奇論題）
We now define the notion, already discussed, of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a lambda-definable function of positive integers).