图灵完备性

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

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

如果某物是图灵完备的，则它可以用于模拟某些图灵完备的系统。例如，一个指令式编程具有条件表达式（例如，“ if”和“ goto”语句，或者“branch if zero”的指令；请参见单一指令计算机）并且具有更改任意指令的能力，那么它便具备图灵完备性。

需要注意的是，虽然任何物理系统都不可能进行无限的迭代展开，但如果忽略这项限制，绝大多数物理系统都符合图灵完备性。

非数学应用

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

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

正式定义

在计算理论中，有几个密切相关的术语用于描述系统的计算能力。（比如抽象机器或者程序语言。）

图灵完全一个计算系统可以计算任何图灵-可计算函数，被称作图灵完全（或者图灵完备）。或者任何可以模拟通用图灵机的系统。图灵等价如果一个计算系统可以计算的所有函数都是图灵可计算的，则称他为图灵等价系统。这个系统可以计算的函数和通用图灵机可以计算的是同一类，或者这个系统可以模拟通用图灵机并被模拟。（所有已知的图灵完备系统都是图灵等价的，这为邱奇-图灵论题提供了支持。）（计算）通用性如果一个系统可以计算一个类别的其他系统可以计算的每个函数（或可以模拟这个类别的每个系统），则该系统相对于这类系统称为通用系统。 通常，通用性这一术语是针对图灵完备类的系统默认使用的。 术语“弱通用性”有时用于区分仅通过修改图灵机的标准定义才能实现其通用性的系统（例如细胞自动机）。

非图灵完备语言

存在很多并不图灵完备的语言，比如由正则表达式表示的正则语言，通过有限状态机进行识别。下推自动机和上下文无关文法更强大，但仍不是图灵完备的，他们一般用于在程序编译的初期阶段生成分析树。其他示例包括嵌入在Direct3D和OpenGL扩展名中的像素着色器语言的某些早期版本。([来源请求])

在如Charity和Epigram之类的总函数式编程语言中，所有功能都是总的，必须终止。 Charity使用类型系统和基于范畴论的控制流程，而Epigram使用依赖类型。 LOOP语言的设计使其仅计算原始递归函数。 所有这些都计算总可计算函数的正确子集，因为总的总可计算函数集不可计算。 同样，由于这些语言的所有功能都是合计的，因此与图灵机相比，用于递归可枚举集合的算法无法用这些语言编写。

尽管无类型λ演算是图灵完备的，但简单类型λ演算不是。

数据语言

XML，HTML，JSON，和YAML不符合图灵完备性，因为他们通常用来表示结构化数据而不描述计算。这些语言有时被称为标记语言，或更恰当地称为“容器语言”或“数据描述语言”。