图灵与可计算性理论
1936年图灵提出图灵机模型与停机问题不可判定，奠定计算机科学理论基础。
背景
为回答”可计算性”的精确含义，并解决希尔伯特提出的”判定问题（Entscheidungsproblem）“——即是否存在一种机械步骤能判定任意数学命题是否可证——需要先严格界定什么叫”算法”或”机械可计算”。
详细描述
1936年，英国数学家阿兰·图灵（Alan Turing）发表论文《论可计算数及其在判定问题上的应用》，提出图灵机模型：一条无限长的纸带、一个读写头，以及一组有限的状态转移规则。图灵机精确刻画了”机械可计算”这一概念。
关键结果包括：
- 通用图灵机：存在一台机器可以模拟任意其他图灵机，这是现代”存储程序计算机”的概念原型。
- 停机问题不可判定：不存在一个算法，能判定任意给定的图灵机在给定输入下是否会最终停机。图灵由此证明判定问题无解。
同期，阿隆佐·丘奇（Alonzo Church）独立提出λ演算并得出相同结论，二者被归纳为丘奇–图灵论题：所有”直观可计算”的函数都恰好是图灵机可计算的函数。
求解过程 / 影响（含最新进展若相关）
图灵机成为现代计算机科学的理论模型，可计算性理论由此诞生。停机问题的不可判定性揭示了计算的内在边界，与哥德尔不完备定理相互呼应、彼此印证。这一理论框架至今仍是算法设计、计算复杂性（如P对NP问题）与人工智能的哲学基础。