邱奇－图灵论题

假说前提

已知的三种计算过程（递归，λ演算和图灵机）都是等价的--这三种方法定义了同一类函数。这导致数学家和计算机科学家相信可计算性的概念可由上述三种等价的计算过程描述。简单来讲，邱奇-图灵论题认为如果某种方法（算法）可进行运算，那么该运算也可被图灵机执行（也可被递归定义的函数或λ函数执行）。
邱奇-图灵论题是对计算特性进行描述的一种陈述，故而不能被严格证明。虽然上面提到的三种计算过程可被证明为等价的，但是邱奇-图灵论题最根本的前提--声称一个函数是“可有效计算的”究竟意味着什么--在某种意义上是不甚明确的直觉结果。所以，该论题依然是一个假想。
尽管邱奇-图灵论题不能被证明，到目前为止它仍然受到近乎全面的接受。

起源

在他1936年的论文“论可计算数字，及其在判定性问题（德语：Entscheidungsproblem）中的应用”中，阿兰·图灵试图通过引入图灵机来形式地展示这一想法。在此篇论文中，他证明了“判定性问题”是无法解决的。几个月之前，阿隆佐·邱奇在“关于判定性问题的解释”（A Note on the Entscheidungsproblem）一文中证明出了一个相似的论题，但是他采用递归函数和Lambda可定义函数来形式地描述有效可计算性。Lambda可定义函数由阿隆佐·邱奇和斯蒂芬·克莱尼（Church 1932, 1936a, 1941, Kleene 1935）提出，而递归函数由库尔特·哥德尔（Kurt Gödel）和雅克·埃尔布朗（Jacques Herbrand，Gödel 1934, Herbrand 1932）提出。这两个机制描述的是同一集合的函数，正如邱奇和克林（Church 1936a, Kleene 1936）所展示的正整数函数那样。在听说了邱奇的建议后，图灵很快就证明了他的图灵机实际上描述的是同一集合的函数（Turing 1936, 263ff）.y

影响

之后用于描述有效计算的许多其他机制也被提了出来，比如寄存器机、埃米尔·波斯特（Emill Post）的波斯特系统，组合子逻辑以及马尔可夫算法（Markov 1960）等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能力；类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果，所以现在普遍认为邱奇－图灵论题是正确的。但是，该论题不具有数学定理一般的地位，也无法被证明；说是定理不如说是个将可计算性等同于图灵机的提议。如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许，则该论题也是可以被驳斥的。
在20世纪初期，数学家们经常使用一种非正式的说法即可有效计算，所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用图灵可计算（或简写为可计算）这一定义良好的概念。由于这个没有定义的用语在使用中已经淡去，所以如何定义它的问题已经不是那么重要了。

不可计算函数

我们可以正式定义不可计算的函数。一个有名的例子是海狸很忙函数。该函数接受输入n，返回具有n个状态的图灵机在停机之前所能打印的最大符号数量。找到海狸很忙函数的上限等于解决停机问题，该问题已被确定不能使用图灵机解决。由于海狸很忙函数不能被图灵机计算， 邱奇-图灵论题断言该函数不能使用任何方法进行有效计算。
有一些模型可用于计算（邱奇-图灵）不可计算函数：即所谓的超计算机。Mark Burgin认为类似归纳性图灵机的超递归算法（super-recursive algorithms）可用于反证邱奇-图灵论题。他的论述依赖于对算法更广泛的定义， 这种定义上的扩展使得一些归纳性图灵机包含的不可计算函数变得可计算。这种对邱奇-图灵论题的解读与计算机科学的常规解读不同，把超递归算法归于邱奇-图灵意义上的算法的这种看法并未受到相关领域的广泛接受。