可计算函数与丘奇-图灵论题

可计算函数是指可以通过机械过程评估的函数，而丘奇-图灵论题则将这一非形式化概念与几个精确的数学模型联系起来，这些模型都定义了相同的函数类别。

Definition

如果某个图灵机（或等价地，某个部分递归定义）能在其定义域内的每个输入上产生输出，则该函数是可计算的；丘奇-图灵论题断言，这个数学上精确的类别与直观上有效可计算函数的类别是一致的。

Scope

本主题涵盖图灵机、通过复合、原始递归和最小化从基本函数构建的部分递归函数、λ演算和寄存器机、这些模型等价性的证明、通用机以及丘奇-图灵论题，该论题认为这些模型捕捉了所有有效的计算。

Core questions

• 什么是图灵机，它如何定义计算？
• 部分递归函数是如何从基本操作生成的？
• 为什么所有合理的计算模型都定义了相同的函数？
• 丘奇-图灵论题的地位和意义是什么？

Key theories

图灵机模型

图灵机是一种在无限磁带上操作的有限状态设备，它计算的函数以基本符号操作的形式形式化了算法的概念。

模型等价性

图灵机、部分递归函数、λ演算和寄存器机都计算完全相同的函数类别，这表明了可计算性概念的稳健性。

通用机与枚举

存在一台通用图灵机，它可以模拟任何给定其代码的机器，因此可计算函数可以被有效地枚举并作为数据处理，这是自指结果的基础。

Clinical relevance

可计算函数的概念是理论计算机科学的基础：通用机预示了存储程序计算机的出现，模型的等价性证明了算法单一而稳健的定义是合理的，并且该框架为研究不可判定性和复杂性提供了精确的背景。

History

1936年，丘奇通过λ演算定义了有效可计算性，图灵通过他的机器定义了有效可计算性，这两种概念很快被证明与克莱尼的递归函数等价。由此产生的丘奇-图灵论题成为公认的算法定义，而图灵的通用机则成为通用计算机的概念先驱。

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

有些函数是不可计算的吗？

是的。由于程序可以被枚举而函数不能，一个计数论证表明大多数函数是不可计算的，并且像停机函数这样的特定例子被证明是不可计算的。可计算性是对算法可以评估哪些函数的真正限制。

丘奇-图灵论题是否限制了计算机能做什么？

它表明，没有任何有效的计算模型能将可计算函数的类别扩展到图灵机之外。更快的硬件或不同的架构改变的是效率，而不是原则上可计算的边界，因此该论题为算法可解性设定了绝对限制。