初等数论中的一个不可解问题
有些是非问题，任何程序都永远答不出。
有些问题听起来再清楚不过——是，还是否？——可丘奇却证明了：没有任何配方、任何机器、任何程序，能够回答得了它们。
核心想法
在你能问出「是不是每个问题都能照着配方解出来」之前，你得先把「配方」究竟是什么钉死。丘奇造出了一门尽可能小的「配方语言」——λ-演算，它只有一个动作：拿一个函数，喂给它一个输入，然后替换。接着他提议：凡是我们直觉上会称作「可计算」的东西，恰恰就是这门小语言所能表达的。这个大胆的等式，如今被称为「丘奇论题」。
当「计算」终于被说清楚，他就能问出一个更锋利的问题——并得到一个惊人的答案。他找到了一个用纯粹数学语言陈述的问题，它的答案总是非是即否，然而没有任何程序，能在每一种情形下都给出正确的答案。不是「我们还没找到」，而是「它不可能存在」。这是真正崭新的东西：一个被证明超出一切方法之外的问题。
它是如何诞生的
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).