图灵机作为衡量计算能力的统一标准

图灵机是一种极度简化的抽象机器——一条可无限延伸、分成单元格的磁带，一个能在磁带上读写符号并左右移动的读写头，以及一套由”当前状态+当前格子内容”决定”下一步写什么、移动方向、切换到哪个状态”的规则表。它看起来简陋到不像是在”计算”什么，却足以模拟递增、加法这类运算，并被证明能表达任何算法能描述的过程。图灵机能计算的函数称为”图灵可计算的”，这个概念之所以重要，是因为它把”一个函数是否可计算”这个抽象问题，转化成了”能否为它设计出一台图灵机”这个具体到可以验证的问题。发散：图灵机的价值不在于它是一种实用的计算工具（没人会真的用它编程），而在于它提供了一把统一的尺子——只要证明某个计算系统的能力等价于图灵机，就能确信它已经具备了”通用计算”所能达到的全部能力，不多也不少，这也是为什么图灵机至今仍是理论计算机科学里衡量一切计算模型能力上限的参照系。