丘奇-图灵论题

丘奇-图灵论题断言，任何有效过程可计算的每个函数都可以由图灵机计算，从而将算法的非正式概念与精确的数学模型等同起来。

Definition

丘奇-图灵论题是指直观上可计算的函数恰好是图灵机可计算的函数，等同于λ演算或一般递归函数可计算的函数；它是一个论题而非定理，因为直观概念没有形式化定义。

Scope

本主题涵盖了该论题的陈述、来自独立提出的模型的趋同证据、关于有效可计算性的原始论题与更强的物理或计算复杂性理论变体之间的区别，以及该论题作为可计算性理论中直觉与形式证明之间桥梁的作用。

Core questions

• 将算法的非正式概念与形式模型等同起来意味着什么？
• 为什么独立模型的趋同被认为是该论题的有力证据？
• 该论题是数学定理、定义还是经验主张？
• 物理和计算复杂性理论版本如何超越原始陈述？

Key theories

计算模型的趋同

图灵机、丘奇的λ演算以及哥德尔和赫布兰德的递归函数被证明定义了完全相同的函数类，这种独立的共识是该论题的主要证据。

作为论题而非定理的地位

由于有效过程的直观概念未被形式化，该主张无法被证明；它被接受为一种基础性等同，使得非正式的算法论证可以替代形式化的图灵机构造。

Clinical relevance

该论题允许日常实践中以高级伪代码而非图灵机来描述算法，因为任何合理的有效过程概念都被假定为图灵等价的；它也构成了关于物理或量子设备是否能计算超出图灵可计算范围的争论的框架。

History

1936年，丘奇提出将有效可计算性与λ可定义性等同起来，图灵独立地提出了他的机器模型，此后图灵、克莱尼等人证明了这些模型与递归函数是等价的。哥德尔最初持怀疑态度，后来认为图灵的分析是决定性的，合并后的主张被称为丘奇-图灵论题。

Debates

物理计算能否超越图灵极限？

原始论题关注有效过程，但更强的物理版本声称，任何物理上可实现的设备都不能计算非图灵可计算函数。超计算的提议和量子力学的含义使得这一扩展主张仍存在争议，尽管经典的论题基本未受挑战。

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

为什么它被称为论题而不是定理？

它将形式模型与有效过程的非正式概念联系起来，而这个非正式概念没有数学定义来证明相关事物。有力的证据是，每一次独立尝试形式化计算都产生了相同的函数类，但这种支持是概念性的而非证明。

量子计算机是否驳斥了丘奇-图灵论题？

不。量子计算机可能更快地解决某些问题，但它们计算的函数类与图灵机完全相同，因此关于什么是可计算的原始论题依然成立。它们更多地与更强的计算复杂性理论版本有关，该版本关注效率而非可计算性。