早在17世纪，数学家莱布尼兹就认为大量的人类推理可以被归约为某类运算，这一思想可能是人工智能的最早起源。他曾思考过这么一个问题：“是否存在一种有效的计算方法，可以判断一个逻辑表达式的真或假？”这一问题后来被希尔伯特和阿克曼于1928年形式化为一个判定问题（Entscheidungsproblem ），即给定一个公理系统和逻辑演算规则，是否存在一个有效可计算的程序，可以对一个逻辑表达式的真假进行判定。
图1：戈特弗里德·莱布尼茨（Gottfried Leibniz），德意志哲学家、数学家。
要想回答这个问题，首先要定义什么样的程序是“有效可计算的（effectively calculable ）”。直观上，一个有效可计算的程序应该可以在有限步骤内得到确定的、预期的结果，但如何把这一直觉用严格的数学语言定义下来并不容易。1930年左右，数学家邱奇（Church）和他的学生克莱尼（Kleene）引入了λ-演算，并证明数论中经常遇到的几大类函数都可以用λ-演算来表示。随后，哥德尔（Godel）提出了通用递归函数，而克莱尼则证明了λ-演算与通用递归函数是等价的。
图2：阿隆佐·邱奇（Alonzo Church），美国数学家
1936年，邱奇的另一个学生，大名鼎鼎的图灵（Turing）提出了图灵机模型[2]，这是现代计算机的数学抽象。随后，在导师邱奇的建议下，图灵很快证明了他的图灵机和λ-演算是等价的，即二者表达了相同的函数集。
于是，人们发现了三种形式化计算模型：λ-演算、递归函数、图灵机，而这些模型代表了相同的函数集。科学家们称这一函数集是图灵可计算的（Turing Computable）。1936年，邱奇证明基于λ-演算，判定问题是不可解的[1]，几个月后，图灵在邱奇的指导下，证明基于图灵机模型，无法判定机器是否可以最终得到预期的结果，这同样意味着判定问题是不可解的[2]。基于图灵可计算函数集，判定问题不可解，这是1936年人们得到的结论。
那么，是否任何有效可计算的（Effectively Calculable）函数都是图灵可计算的（Turing Computable）呢？或者说，是否有比图灵机更强大的计算模型，在这一模型下可解决判定问题呢？因为有效可计算性没有精确定义，这个问题并不好回答。于是，克莱尼将这一问题总结为一个“论题”，或叫“假说”，称为邱奇-图灵论题，表述如下：“自然数上的有效可计算（Effectively Calculable）的函数都是图灵可计算的（Turing Comptuable）”，或者说，不存在比图灵机更加强大的计算模型。
当然，作为一个假说，邱奇-图灵论题是没有证明的。然而，随着时间的推移，人们越来越相信这一论题是正确的。事实上，从图灵开始，人们就在探索比图灵机更强的计算模型，这些模型称为超图灵机（Super Turing Machine）。然而直到今天，超图灵机的存在还没有切实的证据[3]。
邱奇-图灵论题及相应的判定定理是可计算性理论的基础，同时也为人工智能提供了理论保障。例如，神经网络先驱McCulloch 和 Pitts就认为他们的神经网络模型符合邱奇-图灵论题，当配合无限长纸带后将等价于图灵机[4]。受此启发，人们提出物理上邱奇-图灵论题，即如果一个物理过程是可计算的，则由这一计算过程得到的函数是图灵可计算函数，可以用图灵机来实现。如果这一论题成立，当我们假设人类的思维过程是一个计算过程的话，那么当前的计算机架构将有能力对这一过程进行模拟。当然，人类的思维过程是否可以简单地视为一个计算过程，目前还没有定论。
参考文献：
[1]Church, Alonzo (June 1936b). "A Note on the Entscheidungsproblem". Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326.
[2]Turing, A. M. (1937) [Delivered to the Society November 1936], "On Computable Numbers, with an Application to the Entscheidungsproblem"
[3]Davis, Martin (2006). "Why there is no such discipline as hypercomputation". Applied Mathematics and Computation. 178 (1): 4–7Journal of Symbolic Logic. 2 (4): 153–163
[4]Piccinini G. Computationalism, the Church–Turing thesis, and the Church–Turing fallacy[J]. Synthese, 2007, 154(1): 97-120.
By：清华大学 王东