图灵完整性
在计算理论中，据说数据操作规则的系统（例如计算模型，计算机的指令集，编程语言或蜂窝自动机）被认为是完整的，如果可以使用它来模拟，则可以使用它。任何图灵机（由英国数学家和计算机科学家艾伦·图灵（Alan Turing ）设计）。这意味着该系统能够识别或决定其他数据操作规则集。图灵完整性被用作表达此类数据操作规则集的力量的一种方式。如今，几乎所有编程语言都是图灵完整的。
一个相关的概念是图灵等效性- 如果P可以模拟Q和Q可以模拟P。教会论文的猜想，即可以通过算法计算的任何函数可以通过A计算，则称为P和Q。 Turing Machine，因此，如果任何实际计算机都能模拟Turing机器，则其与图灵机相等。通用图灵机可用于模拟任何图灵机，并通过扩展任何现实世界计算机的计算方面。
为了表明某些东西是图灵完整的，足以证明它可以用于模拟某些图灵完整系统。没有物理系统可以具有无限的内存，但是如果忽略了有限内存的限制，则大多数编程语言否则是Turing-Complete。
非数学用法
在通话用法中，使用“图灵完全”和“图灵等效”一词来表示任何现实世界中的通用计算机或计算机语言都可以大致模拟任何其他现实世界通用计算机或计算机语言。在现实生活中，这导致了计算虚拟化和仿真的实用概念。
到目前为止，构建的真实计算机可以像单磁带图灵机（与其内存相对应的“磁带”）进行功能分析；因此，相关的数学可以通过将其操作提取足够远，可以应用。但是，真实的计算机的物理资源有限，因此它们仅是线性界限自动机。相比之下，通用计算机被定义为具有图灵完整指令集，无限内存和无限可用时间的设备。
正式定义
在计算理论中，使用几个密切相关的术语来描述计算系统的计算能力（例如抽像机器或编程语言）：
- 图灵完整性
- 可以计算每个可计算函数的计算系统称为图灵完整（或图灵 - 功率）。另外，这样的系统是可以模拟通用图灵机的系统。
- 图灵对等
- 图灵完整系统称为图灵等效，如果它可以计算的每个函数也是图灵竞争的；即，它与图灵机完全计算出相同类别的功能。另外，图灵等效系统是可以通过通用图灵机进行模拟和模拟的系统。 （所有已知的物理可测量的Turing-Complete系统都是图灵等效的，这增加了教会 - 文化论文的支持。）
- （计算）普遍性
- 如果系统可以计算该类中的系统可计算的每个函数，则称为通用系统（或可以模拟每个系统）。通常，“普遍性”一词被默示地用于图灵完整的系统类别。术语“弱通用”有时用于区分系统（例如蜂窝自动机），该系统仅通过修改图灵机的标准定义来实现通用性，以包括无限多个1s的输入流。
历史
图灵完整性很重要，因为可以通过通用图灵机对计算设备的每个现实世界设计进行模拟。教会论文指出，这是数学定律 - 通用图灵机器原则上可以执行任何其他任何可编程计算机都可以进行的计算。这没有说明编写程序所需的努力，或者机器执行计算所需的时间，或者机器可能拥有的任何能力与计算无关。
如果查尔斯·巴巴奇（Charles Babbage）的分析引擎（1830年代），如果它在设计时是建造的，那将是第一台图灵完整的机器。 Babbage感谢该机器能够进行重大计算的壮举，包括原始的逻辑推理，但他不欣赏没有其他机器能做得更好。从1830年代到1940年代，建造和改进了机械计算机，例如加法器和乘法器，但它们无法执行条件分支，因此无法完成。
在19世纪后期，利奥波德·克罗内克（Leopold Kronecker）提出了可计算性的概念，定义了原始递归函数。这些功能可以通过死记硬背计算，但是它们不足以制造通用计算机，因为计算它们的指令不允许无限循环。在20世纪初期，戴维·希尔伯特（David Hilbert）领导了一项计划，以精确的公理和精确的逻辑扣除规则可以由机器执行。很快，很明显，一系列的推论规则足以产生任何公理的后果。库尔特·戈德尔（KurtGödel）在1930年证明了这些规则足以生产每个定理。
从Gödel的不完整定理开始，不久之后就孤立了计算的实际概念。该定理表明，当推理推理其定理的计算时，公理系统受到限制。教会和图灵独立地表明，希尔伯特的ientscheidungsproblem （决策问题）是无法解决的，因此确定了不完整定理的计算核心。这项工作以及哥德尔在一般递归功能方面的工作确定，有一组简单的说明，当将它们放在一起时，可以产生任何计算。戈德尔的工作表明，计算的概念本质上是独一无二的。
1941年， Konrad Zuse完成了Z3计算机。 Zuse当时不熟悉图灵（Turing）在可计算性方面的工作。特别是，Z3缺乏有条件跳跃的专用设施，因此排除了图灵的完成。然而，在1998年，罗哈斯（Rojas）表明Z3能够模拟条件跳跃，因此理论上完整了图灵。为此，其磁带程序必须足够长的时间才能通过每个分支的两侧执行所有可能的路径。
1946年的ENIAC是第一台能够实践中有条件分支的计算机，因此在实践中完成了Turing。
计算理论
计算性理论使用计算模型来分析问题并确定它们是否可以计算以及在什么情况下。可计算理论的第一个结果是，存在问题，无法预测（图灵完整）系统在任意长时间内会做什么。
经典的示例是停止问题：创建一种算法，该算法以某些图灵完整语言的输入为输入程序，并将某些数据馈送到该程序，并确定该程序在输入上运行，最终将停止还是将继续永远。创建可以为某些输入来做到这一点的算法是微不足道的，但总体上不可能做到这一点。对于该程序最终输出的任何特征，就无法确定此特征是否会保持。
在分析现实世界计算机程序时，这种不可能会带来问题。例如，一个人无法编写完全保护程序员免于编写无限循环或保护用户提供导致无限循环的输入的工具。
相反，可以将程序限制为仅在固定的时间段内执行（超时）或限制流量控制指令的功率（例如，仅提供在现有数组的项目上迭代的循环）。但是，另一个定理表明，通过图灵完整的语言可以解决一些问题，而这些语言无法通过任何具有有限循环能力的语言来解决的（即，保证每个程序最终都会停止的任何语言）。因此，任何这样的语言都不是整理完整的。例如，保证程序可以完成并停止程序的语言无法计算Cantor的对角线论证在该语言中所有可计算函数上产生的可计算函数。
图灵的甲骨文
具有无限数据胶带的计算机可能比图灵机更强大：例如，该磁带可能包含停止问题或其他图灵无法确定的问题的解决方案。这样的无限数据胶带称为图灵甲骨文。即使是带有随机数据的Turing Oracle也无法计算（概率1 ），因为只有很多计算，但无数的计算。因此，带有Turing Oracle随机的计算机可以计算图灵机无法的东西。
数字物理
所有已知的物理定律都有可通过数字计算机上的一系列近似值来计算的后果。一个称为数字物理学的假设指出，这不是偶然的，因为宇宙本身可以在通用图灵机上计算。这意味着没有比通用图灵机更强大的计算机可以在物理上构建。
例子
被讨论为图灵完整系统的计算系统（代数，微积分）是用于研究理论计算机科学的系统。它们旨在尽可能简单，因此更容易理解计算的限制。这里有几个：
大多数编程语言（它们的抽像模型，也许具有某些假定有限记忆的特定构造），传统和非常规的内容是图灵完整的。这包括：
- 所有通用语言都广泛使用。
- 大多数语言都使用较少常见的范式：
一些重写系统正在图灵完成。
图灵完整性是一种抽象的能力陈述，而不是用于实现该能力的特定语言特征的处方。用于实现图灵完整性的功能可能会大不相同。 FORTRAN系统将使用循环构造，甚至可能使用循环陈述来重复； Haskell和Prolog几乎完全缺乏循环，将使用递归。大多数编程语言都在描述具有内存（RAM和寄存器）和控制单元的von Neumann架构上的计算。这两个元素使这个体系结构完整。即使是纯粹的功能语言也是图灵完整的。
声明性SQL中的图丁完整性是通过递归的共同表格表达式实现的。毫不奇怪，SQL（ PLSQL等）的程序扩展也是Turing-Complete。这说明了为什么相对强大的非整洁的语言很少见：语言最初的功能越强大，越复杂的是它所应用的任务，而其缺乏完整性的越早就被视为一种缺点，鼓励了它的任务扩展直到整形为止。
未型的lambda演算是图灵完整的，但是包括系统F在内的许多打字lambda calculi却没有。打字系统的价值基于它们代表最典型的计算机程序的能力，同时检测更多错误。
规则110和Conway的生活游戏，即蜂窝自动机，都完整。
无意的文化完整性
某些游戏和其他软件是偶然的，即不是通过设计。
软体:
游戏：
社交媒体：
计算语言：
生物学：
- 化学反应网络和基于酶的DNA计算机已被证明是图灵等效的
非曲调完整语言
存在许多不完整的计算语言。一个这样的例子是一组普通语言，这些语言由正则表达式生成，并由有限的自动机识别。有限自动机的功能更强大但仍然不包含完整的扩展，是倒数式自动机和无上下文语法的类别，这些语法通常用于在程序编译的初始阶段生成分析树。进一步的示例包括嵌入Direct3D和OpenGL扩展中的像素着色器语言的一些早期版本。
在诸如慈善机构和题词之类的总功能编程语言中，所有功能都是总的，必须终止。慈善机构使用基于类别理论的类型系统和控制构建体，而Epigram则使用依赖类型。循环语言的设计使其仅计算原始递归的函数。所有这些计算总计可计算函数的适当子集，因为整个可计算函数的完整集都无法计算。同样，由于这些语言中的所有功能都是总的，因此与图灵机相比，不能以这些语言编写递归枚举集的算法。
虽然（Untyped） lambda conculus是Turing-Complete，但简单地打字的Lambda演算不是。