丘奇-图灵论题：计算的本质与边界

丘奇-图灵论题：计算的本质与边界

引用

科学网

1.

https://blog.sciencenet.cn/blog-107667-1427697.html

丘奇-图灵论题（The Church-Turing thesis）是计算机科学和数学领域的一个重要概念，由美国数学家阿隆佐·丘奇（Alonzo Church）和艾伦·图灵（Alan Turing）提出。该论题指出，一个问题有算法可解，当且仅当该问题可用处处停机的图灵机来计算。这里的"处处停机"是指在所有输入上都在有限步之内停机，而图灵机计算一个问题是指在所有输入上都给出正确答案。

图1：左图：阿隆佐·丘奇。右图：艾伦·图灵（照片：普林斯顿大学）

为了更好地理解丘奇-图灵论题，我们可以探讨以下几个问题：

1. "根号2"（实数）是一种合理的存在吗？"根号2"能被图灵机正确处理吗？
2. "几何曲线"（实数的幂集）是一种合理的存在吗？"几何曲线"能被图灵机正确处理吗？
3. 人类"手舞足蹈"（几何曲线的幂集）是一种合理的存在吗？"手舞足蹈"能被图灵机正确处理吗？

这里所说的"合理的存在"，是指满足下列之一或更多条件：

• 合乎逻辑的
• 具有某种数学上的合理性
• 是现实世界中"客观"存在

图2：舞蹈里的重复练习，做起来很苦，坚持下来很酷

值得注意的是，虽然丘奇-图灵论题在计算机科学和数学领域具有重要地位，但其本身并不能被严格证明。这是因为论题的表述涉及"直观意义上的算法"这一不精确的概念。尽管有人试图反驳这一论题，但都没有成功。

此外，丘奇-图灵论题还与量子计算等领域密切相关。例如，玻色采样模型作为一个可物理实现的专用量子计算模型，有望检验扩展的丘奇-图灵论题，在量子计算和计算复杂性理论方面都有重要意义。

总之，丘奇-图灵论题不仅是计算机科学和数学领域的基础理论，也为我们理解计算的本质提供了重要视角。