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