理论-丘奇-图灵论题

丘奇-图灵论题（Church-Turing Thesis）是计算理论中的一个核心假设，它由逻辑学家阿隆佐·丘奇（Alonzo Church）和人物-艾伦·图灵独立提出。该论题断言，任何在直观上可被视为“可有效计算”的函数，都可以被图灵机所计算。换言之，它将人类直觉中的“算法”或“机械过程”这一模糊概念，与图灵机这一精确的概念-形式系统等同起来。

论题的核心思想

丘奇-图灵论题并非一个可以被严格证明的数学定理，而是一个基于经验和直觉的论题。它之所以被广泛接受，是因为所有已知的、被认为是“可计算”的计算模型（如λ演算、递归函数等）都被证明与图灵机在计算能力上是等价的。这个论题为探讨概念-智能的本质和人工智能的可能性提供了理论基础。

与本书思想的关联

丘奇-图灵论题是《集异璧》一书的隐含支柱之一。它构成了“机器是否可以思维”这一问题的形式化基础。如果接受该论题，那么任何可以被算法化的思维过程，原则上都可以由一台图灵机（即计算机）来模拟。书中关于概念-智能、心智和意识的许多讨论，都是在这一论题的背景下展开的。

早于卢卡斯1961年论文的一篇出色论文，但从根本上说是反驳前者的。人们可能由此得出结论：要想反驳卢卡斯，你得具有“司马”这一文明悠久的“特殊”姓氏所传下来的“古德”。

Smart J. . C.[司马特]“Gödel’s Theorem, Church’s Theoren, and Mechanism”[哥德尔定理、丘奇定理和机械论]，Synth6se《综合》13(1961)第105页。

对论题的质疑

尽管被广泛接受，丘奇-图灵论题也并非没有受到过质疑。书中提及了匈牙利数学家拉茨洛·卡尔马（Löeszló Kalmár）是该论题的著名不信者之一，他的诘难代表了对“可计算性”边界的持续探索。

一篇由也许是最著名的不信丘奇-图灵论题的人所写的有趣论文。

Kalmár Löeszló[卡尔马·拉茨洛]，“An Argument Against the Plausibility of Church’s Thesis”[对丘奇论题正确性的诘难], A. Heyting[海廷]编：Constructivity in Mathematics: Proceedings of the Colloquium held at Amsterdam，1957《数学中的建设性：1957年阿姆斯特丹年会文集》，North-Holland，1959年。