阿隆佐·丘奇(1903年6月14日—1995年8月11日)是美国数学家、逻辑学家,他的工作为计算的数学基础作出了奠基性贡献。他创立了λ演算,证明了一阶逻辑的一般判定问题不可判定,并提出将有效可计算性等同于一个有精确定义的数学函数类。这一主张成为丘奇—图灵论题的一种表述。他的研究、教学与编辑工作也对20世纪的逻辑学和计算机科学产生了深远影响。
生平与学术生涯
丘奇出生于华盛顿哥伦比亚特区。他就读于普林斯顿大学,1924年取得本科学位,1927年在奥斯瓦尔德·维布伦指导下取得数学博士学位。完成博士后研究后,他于1929年加入普林斯顿大学任教,直至1967年。随后,他转赴加利福尼亚大学洛杉矶分校,任教至1990年。
在普林斯顿大学期间,丘奇培养了多位后来成为逻辑学与理论计算机科学核心人物的研究者。他的博士生包括艾伦·图灵、斯蒂芬·科尔·克莱尼、莱昂·亨金、迈克尔·拉宾、达纳·斯科特和雷蒙德·斯穆里安。图灵在提出自己的计算模型后,于1938年在丘奇指导下完成了普林斯顿大学的博士学业。
丘奇还自《符号逻辑杂志》1936年创刊起便与该刊保持着密切联系。他在该刊评论栏目上投入了大量工作,帮助梳理和传播这一迅速发展领域中的研究成果。
λ演算
20世纪30年代初,丘奇在尝试为逻辑学和数学建立基础的过程中提出了λ演算。其核心思想是将函数、函数的应用以及通过抽象定义函数的方式,作为形式语言的基本对象。
例如,表达式
表示恒等函数。将其应用于表达式 ,得到
这一变换是β归约的一个实例:用实参替换函数体中的约束变量,同时采取适当措施,避免意外的变量捕获。
尽管λ演算的语法规则很少,它仍能表示算术、数据结构和一般计算。在无类型λ演算中,函数既可以应用于其他函数,也可以应用于自身。这种灵活性使系统具有强大的计算能力,但也允许出现求值永不终止的表达式。
从逻辑基础到计算理论
丘奇最初提出的基础体系,不仅包含如今称为λ演算的计算机制。1935年,克莱尼与J.巴克利·罗瑟证明,丘奇早期提出的逻辑基础体系是不相容的。但这一结果并未证明,作为项与转换规则系统的纯λ演算是不相容的。
这一区别十分重要:一个未能成功的基础方案,却包含了经久不衰的计算形式体系。此后,λ演算成为程序设计语言理论的核心研究对象,并成为函数式编程的理论基础。
丘奇—罗瑟定理
丘奇与罗瑟于1936年证明了丘奇—罗瑟定理。按照一种标准表述,如果一个λ项沿两条不同的有限路径归约,那么得到的两个项都能进一步归约为同一个项。
这一性质称为合流性。它意味着,如果一个项有正规形,即无法再进行β归约的表达式,那么在不计约束变量重命名差异的意义下,这个正规形是唯一的。这并不意味着每个项都有正规形,也不意味着只要正规形存在,每一种求值策略都能找到它。该定理将计算结果的一致性与计算是否终止的问题区分开来。
有效可计算性与判定问题
20世纪30年代,逻辑学家试图精确定义“通过机械过程进行计算”的含义。直观上,算法被理解为一套有限的步骤说明,执行时不需要创造性的思考,但这种理解尚未确定一个得到普遍认可的数学类。
丘奇提出,自然数上的有效可计算函数应当等同于λ可定义函数,也等价于可计算性理论所研究的一般递归函数。在1936年的论文《初等数论中的一个不可解问题》中,他运用这一框架证明,某些数学问题不存在有效解法。
一阶逻辑的不可判定性
Entscheidungsproblem,即判定问题,尤其与大卫·希尔伯特和威廉·阿克曼的工作相关。它要求找到一种通用的机械过程,以判断任意一阶逻辑公式是否具有逻辑有效性。
1936年,丘奇利用自己对有效可计算性的形式化刻画,证明不存在这样的通用有效过程。图灵则通过如今称为图灵机的机器模型,独立得出了这一否定结果。
这一结果针对的是一种必须对每个输入公式都能给出正确的是非答案并终止的算法。它并不意味着任何个别的有效性问题都无法解决,也不意味着每一种受限的逻辑语言都是不可判定的;例如,命题逻辑就存在判定过程。
不过,一阶逻辑的有效公式仍然是可有效枚举的。通过系统地搜索证明,最终可以找到任何有效公式的证明;但当输入公式无效时,这一过程可能永不终止。识别与判定之间的这一区别,是可计算性理论的基本内容。
丘奇—图灵论题
研究表明,图灵基于机器的分析与丘奇基于函数的方法,刻画了相同的计算能力。这两种方法殊途同归,再加上以递归函数给出的等价表述,为丘奇—图灵论题提供了有力支持:
每个有效可计算函数都能由图灵机计算。
这一论题将“有效计算”这一非形式化概念与一个形式化的数学定义联系起来。它不是像两个形式计算模型的等价性那样得到证明的定理。
这一论题讨论的是原则上能够计算什么,而不是计算效率有多高。时间、存储空间与实际可行性等问题需要进一步分析。关于高效模拟或物理过程计算极限的更强主张,与原始论题有所不同。
类型论与逻辑学
丘奇也对类型论作出了奠基性贡献。他在1940年的论文《简单类型论的一种形式化》中,提出了一个以λ记法为核心、影响深远的带类型逻辑系统。
类型限制了哪些表达式可以有意义地组合。在简单类型体系中,函数具有指定的输入类型和输出类型;函数应用必须遵守这些类型规定。这样的限制排除了不受约束的自应用,并有助于防止那些导致某些逻辑悖论的构造。
丘奇的简单类型论支持高阶推理,包括对谓词和函数进行量化。它成为后来高阶逻辑与自动证明系统研究的重要参照。
带类型λ演算后来也成为柯里—霍华德对应的核心内容;这一对应将命题与类型、证明与项联系起来。它是多位研究者共同发展起来的,应当与丘奇本人提出的具体形式体系加以区分。
著作与影响
丘奇的主要著作包括《初等数论中的一个不可解问题》(1936年)、《关于判定问题的一则注记》(1936年)、《简单类型论的一种形式化》(1940年)、《λ转换演算》(1941年)以及《数理逻辑导论》第一卷(1956年)。
他的不可判定性结果与哥德尔不完备定理,同属20世纪逻辑学确立的重大局限性结果,但它们回答的是不同的问题。不完备性涉及适当形式理论内部可证明性的局限;丘奇关于判定问题的结果,则涉及判定逻辑有效性的通用算法不可能存在。
丘奇的影响也延续于具体的技术构造之中。丘奇编码用函数来表示自然数、布尔值和有序对等对象。例如,丘奇数通过重复应用函数来表示自然数:
这里, 表示对 恰好应用 共 次。这些编码展示了一个仅由抽象与应用构成的形式体系,如何表达结构化数据与算术。