1 历史背景
1.1 希尔伯特的可判定性问题
20世纪初，德国数学家大卫·希尔伯特在1928年国际数学家大会上提出了“可判定性问题”（Entscheidungsproblem）：是否存在一种通用的机械步骤，能够判定任意一个给定的数学命题（在一阶谓词逻辑范围内）是否可证？希尔伯特相信这样的算法是存在的，这一信念被称为“希尔伯特纲领”的一部分——试图为所有数学建立一套完备且一致的公理化系统。
1.2 哥德尔不完备定理的启发
1931年，库尔特·哥德尔发表了他的不完备定理，指出任何包含算术的相容形式系统都无法证明其自身的相容性，并且存在不可判定的命题。哥德尔的工作动摇了希尔伯特纲领的根基，但并未直接否定可判定性问题的存在——因为不可判定命题的存在并不自动意味着“判定过程”的不存在。不过哥德尔在研究中引入了“递归函数”的概念，为形式化“有效计算”提供了初步工具。
1.3 丘奇的λ演算与递归函数
1936年，阿隆佐·丘奇提出了一种基于函数抽象和应用的符号演算系统——λ演算（lambda calculus），并定义了一类“可定义函数”。同年，他与斯蒂芬·克莱尼合作，系统化了哥德尔-赫布兰德意义上的递归函数，证明了λ可定义函数与一般递归函数等价。丘奇由此首次提出：任何直觉上“可有效计算”的函数正是这些递归函数（或λ可定义函数）。这一断言后来被称为“丘奇论题”。
1.4 图灵的自动机模型
1.4.1 图灵机（Turing machine）
几乎与丘奇同时，阿兰·图灵在1936年的论文《论可计算数及其在判定问题上的应用》中提出了另一种计算模型——图灵机。图灵机由一条无限长的纸带、一个读写头以及一组有限的状态组成，能够执行最简单的读写和状态转移操作。图灵论证了这种机器能够模拟任何人类数学家（在有限时间内）能执行的计算过程，并且提出“可计算数”的概念——即那些可以由图灵机在有限步后输出的实数。
1.4.2 停机问题与不可判定性
在图灵的同一篇论文中，他证明了著名的“停机问题”：不存在一个通用的算法，能够判断任意一个图灵机在给定输入上是否会最终停机。这个结果等价于希尔伯特判定性问题的否定答案。图灵利用对角化方法构造了一个自相矛盾的机器，揭示了算法能力的内在边界。停机问题成为第一个被严格证明的不可判定问题，也为丘奇-图灵论题提供了强力佐证：如果某种更强大的计算模型存在，它必须能解决图灵机无法解决的问题，但至今未发现这样的“物理合理”模型。
2 核心内容
2.1 直观的“有效计算”概念
“有效计算”（effective calculability）指的是：一个函数可以通过一系列离散、确定、有限的机械步骤（算法）求出结果，每一步都明确可行，且算法最终会终止并输出答案。这一概念依赖于直觉——类似于一个训练有素的数学家，仅凭纸笔，严格遵循指令而不需要任何创造性洞察，就能在有限时间内完成计算。
2.2 论题的形式化表述
丘奇-图灵论题可以表述为：
一个函数是“可有效计算的”当且仅当它可用图灵机（或任何等价的通用计算模型）计算。
该论题没有声称图灵机是唯一可能的计算模型，而是断言所有合理的计算模型精确刻画了同一个计算能力边界。所有等价模型——包括λ演算、递归函数、波斯特系统、寄存器机等——都被证明相互等价，进一步支持了这一论题。
2.3 与数学定理的区别（论题 vs. 定理）
丘奇-图灵论题不是数学定理，因为它涉及“有效计算”这一未严格定义的直觉概念，无法在形式系统内被证明。一个定理需要从公理出发经形式推导得出，而这里的“有效计算”本身没有公理定义。因此，论题是一条“命题”或“原理”，其可信性依赖于经验事实：所有已知的、物理上可实现的计算过程都未超越图灵机的计算能力，且所有被提出的替代模型都被证明等价。
3 等价的计算模型
3.1 λ演算（lambda calculus）
λ演算由丘奇提出，是一种基于函数定义和函数应用的符号系统。它包含三种基本操作：变量、抽象（λx.M）和应用（M N）。通过β归约等规则，λ演算可以模拟任何图灵机可计算函数。反之亦然，图灵机也可以模拟λ演算的归约过程。因此，λ演算与图灵机在计算能力上等价。
3.2 递归函数（recursive functions）
哥德尔、赫布兰德、克莱尼等人发展了一般递归函数理论，将可计算函数定义为那些从初始函数（零函数、后继函数、投影函数）出发，经过复合、原始递归和极小化操作有限次得到的函数。丘奇和克莱尼证明了这类函数恰好等于λ可定义函数，也等于图灵可计算函数。
3.3 图灵机
3.3.1 确定性图灵机
确定性图灵机（DTM）在每个状态下根据当前符号只有一个确定的下一步动作（写入、移动、状态转换）。尽管其结构简单，却足以计算所有可计算函数。
3.3.2 非确定性图灵机
非确定性图灵机（NTM）允许在每个状态下有多种可能的动作。尽管其定义更“强大”（允许选择路径），但可以证明NTM的计算能力并不超过DTM——任何NTM都能被一个DTM模拟，只是模拟可能花费指数级时间。这一等价性也说明非确定性并未突破可计算性边界。
3.4 其他等价模型
3.4.1 寄存器机（register machine）
寄存器机是一种抽象计算机，拥有有限个整数寄存器，每条指令可以增加、减少寄存器值或进行条件跳转。虽然资源有限，但寄存器机可以模拟图灵机，故二者等价。
3.4.2 马尔可夫算法
马尔可夫算法由苏联数学家安德烈·马尔可夫提出，是一种基于字符串替换的规范系统。给定一组按优先顺序排列的替换规则，算法反复应用最左侧可匹配的规则直到无法继续。马尔可夫算法也被证明等价于图灵机。
3.4.3 波斯特系统
埃米尔·波斯特在20世纪20年代提出了一种基于产生式规则的符号操作形式系统。其后在1936年独立提出“波斯特机器”，类似于图灵机但使用双端队列。这些系统同样与图灵机等价。
4 哲学与数学意义
4.1 可计算性与算法本质
丘奇-图灵论题第一次给出了“算法”的精确数学定义：算法就是可以被图灵机执行的过程。这意味着算法的本质是离散的、一步步的、确定的符号操作。这为计算机科学提供了理论基石，使得人们能够严格讨论哪些问题是“可解的”，哪些是“不可解的”。
4.2 心智、意识与计算主义
4.2.1 强人工智能的可能性
如果心智过程本质上是一种计算，那么根据丘奇-图灵论题，任何智能行为都可以被图灵机（即数字计算机）实现。这就是“强人工智能”的立场：正确的程序加上合适的硬件就能产生真正的意识。计算机的终极能力并不受限于图灵机本身——只要大脑的计算能力不超越图灵机，则人工智能理论上是可行的。
4.2.2 塞尔的“中文屋”质疑
约翰·塞尔提出“中文屋”思想实验来反驳强人工智能：一个人关在屋子里按照规则手册操作中文符号，完全不懂中文含义，却能让外界以为他懂中文。塞尔认为这证明了语法操作（计算）不能产生语义理解。然而，计算主义者回应说，整个系统（人+规则手册+房间）才是理解的主体，而非房间内的人。中文屋争论至今未达成共识，但它凸显了丘奇-图灵论题在意识哲学中引发的核心张力。
4.3 论题在数学基础中的地位
丘奇-图灵论题并非一般数学定理，但在数学基础中扮演“定义性原理”的角色——它划定了形式系统可证明性的边界。哥德尔不完备定理表明任何足够强的系统都存在真而不证的命题；丘奇-图灵论题则进一步说明，不存在通用算法可以判定所有数学命题的真假，这为数学的不可穷尽性提供了计算视角的解释。许多数学家接受论题作为合理的公理，用来判定某些问题是否“不可计算”。
5 争议与拓展
5.1 超计算（hypercomputation）
5.1.1 神谕机（oracle machine）
图灵自己在1939年的论文中引入了“神谕机”的概念：一台图灵机加上一个外部“神谕”，能够瞬间回答某个特定问题（如停机问题）。神谕机可以计算图灵机不可计算的函数，但神谕本身是否“物理可实现”并不在图灵考虑之内。超计算领域试图探索利用物理过程（如实数的连续运算、时间旅行、无限并行）来超越图灵可计算性。
5.1.2 现实主义与物理可实现性
大多数物理学家和计算机科学家认为，基于已知物理定律（如量子力学中的有限能量、有限信息传输速度等），任何现实的物理系统都不能实现真正的超计算。因此，丘奇-图灵论题被广泛接受为“物理的”或“经验性的”原理，而非纯粹的数学约定。
5.2 量子计算与丘奇-图灵论题
5.2.1 量子图灵机
量子图灵机由大卫·多伊奇在1985年提出，是图灵机在量子力学框架下的推广。它利用量子叠加和纠缠进行并行计算。然而量子图灵机在可计算性层面（即哪些函数可计算）并未超越经典图灵机——任何量子可计算函数也都是经典可计算的，只是速度可能更快。
5.2.2 丘奇-图灵-多伊奇原理
多伊奇提出强化的丘奇-图灵原理：任何有限物理系统都可以被一台通用计算机（量子计算机）以有限步模拟。这一原理将论题从经典计算推广到所有物理过程。虽然量子计算机可能在复杂性上超越经典计算机，但可计算性边界仍未动摇。
5.3 随机性对论题的影响
如果允许真正的随机性（如抛硬币），图灵机可以扩展为“概率图灵机”。概率图灵机可以解决某些经典图灵机在确定性意义下无法高效解决的问题（例如素性检验在确定性多项式时间内的算法较晚才被找到），但就“可计算”而言，概率不会使不可判定问题变为可判定——如果一个问题对确定性图灵机不可判定，那么随机性也无法保证在有限步内以概率1得到正确答案（因为随机性只能降低错误概率，不能消除无限循环的可能性）。
6 应用与影响
6.1 编程语言与可计算性
几乎所有主流编程语言（C、Java、Python、Lisp等）都是图灵完备的——它们可以模拟任意图灵机，因而能够实现任何可计算函数。编程语言的“图灵完备性”通常意味着该语言可以书写任何算法，只要内存不限。但实际编程中，由于有限资源的限制，可计算性理论更多用于理解问题能否被“原则上”解决，而不是描述实际运行。
6.2 复杂性理论的基础
丘奇-图灵论题为复杂性理论提供了底层模型：所有多项式时间可解的问题（P类）、非确定性多项式时间可解的问题（NP类）等等，都是在图灵机模型上定义的。如果没有公认的计算模型，复杂性类别将失去统一基准。论题保证了不同计算模型（例如寄存器机、随机存取机）之间的多项式时间模拟不会改变问题的所属复杂性类（多项式等价性）。
6.3 密码学与不可解问题
密码学利用计算难解性（即某些问题虽然可计算，但需要天文数字的时间）来确保安全性。然而，丘奇-图灵论题也提示了存在根本不可解的问题。例如，密码学中判断一个程序是否会在给定输入下输出特定结果，这类问题往往可归约为停机问题的变形，从而被证明不可判定。这提醒密码分析师：某些安全性的“绝对保证”在理论上是不可能的。
7 参考文献
（此部分通常列出参考书目和论文，作为百科词条示例，此处省略具体文献条目，仅说明格式要求。）