圖靈完備性

(重定向自图灵完全

可计算性理论里,如果一系列操作数据的规则(如指令集编程语言细胞自动机)可以用来模拟任何图灵机,那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集,图灵完备性被用作表达这种数据处理规则集的一种属性。如今,几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。

还有一个相关概念是图灵等价 – 如果P可以模拟Q并且Q可以模拟P,则两台计算机P和Q称为等效计算机。 邱奇-图灵论题认为任可以通过算法计算其值的函数都可以由图灵机计算,因此,如果任何真实世界的计算机都可以模拟图灵机,则其对图灵机是图灵等价的。 通用图灵机可用于模拟任何图灵机,且可以扩展现实世界计算机的计算方面。[NB 1]

如果某物是图灵完备的,则它可以用于模拟某些图灵完备的系统。例如,一个指令式编程具有条件表达式(例如,“ if”和“ goto”语句,或者“branch if zero”的指令;请参见单一指令计算机)并且具有更改任意指令的能力,则他为图灵完备的。当然,任何物理系统都不可能拥有无限的内存。但如果忽略了有限内存的限制,则大多数编程语言都将是图灵完备的。

非数学应用编辑

在口语用法中,术语“图灵完备性”或“图灵等价”用于表示任何现实世界通用计算机或计算机语言都可以近似模拟任何其他现实世界通用计算机的计算方面、用途的计算机或计算机语言。

到目前为止构建的现实计算机可以在功能上进行分析,就像单带图灵机(对应于它们的内存的“带”)一样; 因此,相关的数学问题可以通过足够抽象的运算来应用。但是,现实计算机的物理资源有限,因此它们仅是线性有界自动机。与之对应的,通用计算机被定义为具有图灵完备的指令集,无限内存和无限可用时间的设备。

参见编辑

笔记编辑

  1. ^ A UTM cannot simulate non-computational aspects such as I/O.

参考文献编辑

参考阅读编辑

外部链接编辑