“Church–Turing 论题把图灵机视为有效计算的标准形式化之一。通用图灵机进一步说明，机器描述本身可以编码成输入，由另一台机器解释执行；程序与数据之间因此没有不可跨越的形式边界。”
形式陈述
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。