丘奇-图灵论题

丘奇-图灵论题（以前通常简称为丘奇论题）指出，任何现实世界的计算都可以转化为涉及图灵机的等效计算。在丘奇最初的表述（Church 1935, 1936）中，该论题指出，现实世界的计算可以使用λ演算来完成，这等同于使用一般递归函数。

丘奇-图灵论题涵盖了比最初设想的更多种类的计算，例如涉及元胞自动机、组合子、寄存器机和替换系统的计算。它也适用于理论计算机科学中发现的其他类型的计算，例如量子计算和概率计算。

关于丘奇-图灵论题存在相互矛盾的观点。一种观点认为它可以被证明，另一种观点认为它作为计算的定义。从未有过证明，但其有效性的证据来自于这样一个事实：迄今为止发现的每一种现实的计算模型都被证明是等效的。如果存在一种设备可以回答图灵机无法回答的问题，那么它将被称为预言机。

对于不同的任务，一些计算模型在计算时间和内存方面更有效率。例如，据推测，与现代计算机相比，量子计算机可以在较低的时间复杂度下执行许多常见任务，因为对于足够大版本的这些问题，量子计算机解决问题的速度将比普通计算机更快。相比之下，存在一些问题，例如停机问题，普通计算机无法回答，并且根据丘奇-图灵论题，没有其他计算设备可以回答这样的问题。

丘奇-图灵论题已被斯蒂芬·沃尔夫勒姆在他的计算等效原理（Wolfram 2002）中扩展为一个关于自然世界过程的命题，该原理还声称，在系统达到通用性之前，只有少数几个中间计算能力级别，并且大多数自然系统都是通用的。