圖靈完備性 在可计算性理论如果一系列操作数据的规则如指令集编程语言细胞自动机可以用来模拟任何图灵机那么它便符合图灵完备Turingcomplete或computationally universal这意味着这个系统也可以识别其他数据处理规则集图灵完备性被用作表达这种数据处理规则集的一种属性如今几乎所有编程语言都是具有图灵完备性的这个词以引入图灵机概念的数学家艾伦图灵命名 还有一个相关概念是图灵等价  如果P可以模拟Q并且Q可以模拟P则两台计算机P和Q称为等效计算机 邱奇图灵论题认为任何可以通过算法计算其值的函数都可以由图灵机计算因此如果任何真实世界的计算机都可以模拟图灵机则其对图灵机是图灵等价的 通用图灵机可用于模拟任何图灵机且可以扩展现实世界计算机的计算方面 如果某物是图灵完备的则它可以用于模拟某些图灵完备的系统例如一个指令式编程具有条件表达式例如 if和 goto语句或者branch if zero的指令请参见单一指令计算机并且具有更改任意指令的能力那麼它便具備图灵完备性 需要注意的是虽然任何物理系统都不可能进行无限的迭代展开但如果忽略这項限制绝大多数物理系统都符合图灵完备性