“Church–Turing 论题把图灵机视为有效计算的标准形式化之一。通用图灵机进一步说明，机器描述本身可以编码成输入，由另一台机器解释执行；程序与数据之间因此没有不可跨越的形式边界。”
形式陈述
Church–Turing 论题主张：任何可由有限、机械、有效步骤执行的计算过程，都能由图灵机计算。等价模型包括
直觉
图灵机用极简的符号操作模型刻画“机械可计算”。纸笔式计算、递归函数、λ 演算和寄存器机等模型独立提出后，却给出同一类可计算函数；这种一致性支持了有效过程可以由图灵机表达的主张。
两类陈述的地位有所不同：精确定义的计算模型之间等价，可以用数学证明；“所有有效过程”中的有效性原本是非形式概念，将它与图灵可计算联系起来是论题本身。
例子与边界
原论题讨论有效计算过程的范围。物理 Church–Turing 论题进一步讨论物理系统可实现的计算，扩展论题则加入高效模拟要求，例如只允许多项式开销；它们各自引入了额外主张。
加法、Euclid 算法和有限字符串搜索都能编成 图灵机，也能写成 λ 项或递归方程；模型之间的模拟说明它们在可计算性上没有差别。反过来，停机不可判定性说明停机集合的特征函数不存在图灵机实现，因此论题把它判为不存在任何普适机械算法，而不只是“当前还没找到程序”。
模型间能模拟彼此，并不意味着模拟开销小。一种模型上简短的计算，在另一种模型上可能耗费很多步骤；可计算性只要求模拟最终给出相同结果，效率则要另算时间、空间和其他资源。
推论与应用
精确模型之间的模拟定理保证 可计算函数 的类在这些模型中一致，因此可以选用最方便的已证等价模型。Church–Turing 论题进一步把这类形式结论联系到非形式的有效算法，使不可判定性成为对普适机械过程的限制，由此奠定可计算性理论的模型稳健性。复杂度理论在其上加入资源界，研究模型之间模拟所需的时间和空间开销，并区分 时间复杂度 与空间复杂度；超计算模型和预言机则常被用来探测论题边界，而不是作为普通算法实现。
参考资料
- Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§3.3。
- John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chapter 8。