2.1 计算模型与丘奇-图灵论题

文档摘要

2.1 计算模型与丘奇-图灵论题 2.1 计算模型与丘奇-图灵论题在可计算性理论的宏阔画卷中，计算模型犹如一幅精密的蓝图，勾勒出人类心智所能触及的算法疆域。第二章伊始，我们已从宏观视角审视了可计算性的本质：它并非抽象的哲学遐想，而是根植于形式化系统的严密框架。本节将深入剖析计算模型的核心，尤以图灵机为基石，辐射至等价模型的家族，并直面丘奇-图灵论题的哲学光芒。这不仅仅是技术层面的铺陈，更是连接“可计算”与“不可计算”鸿沟的桥梁——它为后续探讨停机问题、递归枚举集等微观难题奠定基调。试问：何为“计算”？在1936年那个动荡年代，阿兰·图灵与阿尔诺·丘奇的洞见，是否已预言了今日量子比特与神经网络的边界？