形式陈述

Church–Turing 论题主张：任何可由有限、机械、有效步骤执行的计算过程，都能由图灵机计算。等价模型包括 $\lambda$$\lambda$ 演算、一般递归函数、寄存器机和现代通用程序语言；这里的“等价”指它们计算相同的部分函数类。

直觉

图灵机不是声称真实计算机长得像纸带，而是提出一个极简模型来捕捉“算法可执行性”的共同核心。许多独立提出的计算模型最终得到相同可计算函数类，是论题的主要证据。

例子与边界

该论题不是普通数学定理，因为“有效过程”在论题提出前是非形式概念，不能在同一形式体系内直接证明与图灵可计算等价。它也不等同于“图灵机能高效模拟一切计算”，更不等同于物理 Church–Turing 论题或扩展 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。