一、从PHP与Python的语言比较去了解什么是图灵完备

从非常严格的理论角度来说，答案是：没有。因为PHP和Python都是图灵完备(Turing complete)的语言，所以理论上你找不到一个Python能做到而PHP做不到的事情。

可图灵指在可计算性理论中，编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之，此系统可与通用图灵机互相模拟。这个词源于引入图灵机概念的数学家艾倫·图灵（Alan Turing）。

虽然图灵机会受到存储能力的物理限制，图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。

简单来说，一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。

图灵等价02Turing equivalence02和图灵完备02Turing completeness

经常在讲编程语言的书或文章里面看到图灵等价（Turing equivalence）和图灵完备(Turing completeness)，但却不知道这两个词的精确含义和区别。尤其是很多书或文章经常对这两个词进行混用，我就很疑惑这两个词是不是就是一个意思。我用Google搜索了一下，很遗憾的是中文结果基本没用，只有一篇百度空间里面转载的一个外国人写的文章，还是全英文的，简单看了下感觉写得不怎么清楚，就查了下英文维基百科。言归正传，下面先看看维基百科的两段话：

In02computability theory, a system of data-manipulation rules(such as an02instruction set, a02programming language, or a02cellular automaton) is said to beTuring complete02or02computationally universal02if and only if02it can be used to simulate any single-taped02Turing machine02and thus in principle anycomputer.

在可计算理论里，一个数据操作规则的系统（比如：指令集、编程语言、细胞自动机）被称作图灵完备或者通用计算的，当且仅当它可以被用来模拟单带图灵机。

In computability theory, there is a closely related concept known as Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine, but the term is most often used to mean Turing equivalent to a Turing machine.02

在可计算理论里，有一个很相关的概念叫图灵等价。当计算机 P和计算机 Q是图灵等价的，当P可以模拟Q而且Q也可以模拟P。因此，一个图灵完备的系统可以模拟图灵机，但是这个术语（即图灵等价）常常被用来指与图灵机等价。

然后我们再来看看在可计算理论中，这两个词的正式定义：

Turing completeness：A computational system that can compute every Turing-computable function02is called Turing complete(or Turing powerful). Alternatively, such a system is one that can simulate a02universal Turing machine.

Turing equivalence：A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do02Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine.(All known Turing-complete systems are Turing equivalent, which adds support to the02Church–Turing thesis.)

图灵等价：一个图灵完备的系统被称为图灵等价的，如果任何它可以计算的函数也是图灵可计算的。也就是它可计算的函数和图灵机可计算的函数是完全相同的。换句话说，就是图灵等价的系统就是能模拟通用图灵机同时也能也被通用图灵机模拟的系统。（所有已知的图灵完备的系统都是图灵等价的，这增加了对丘奇-图灵论题的支持）

通过上面的分析，我们就可以清楚的知道这两个词的意思和关系了。图灵等价有两个意思，一个是指两个计算系统在可计算性上计算能力相同；另一个，也是常用的一个就是指一个系统的计算能力与通用图灵机计算能力相同（在可计算性的意义上）。而图灵完备是指能够模拟通用图灵机的计算系统。而所有已知的图灵完备的系统都是图灵等价的，这也增加了对丘奇-图灵论题的支持。因此，在现有的计算机系统（编程语言、指令集等）上，使用图灵等价和图灵完备是一个意思。

二、sql算是一种语言么 满足图灵完备性么

当然算是语言了,名字都叫结构化查询语言.

我不知道如何证明是不是图灵完备的,有读能写(对应图灵机里面的读写头),有存储系统(对应图灵机里面的纸带),有逻辑判断功能(对映图灵机里面读写头在纸带上的按指令移动功能).

感觉SQL语言把brainfuck语言的指令功能都能实现. brainfuck是图灵完备的,也许可以通过证明SQL语言对于brainfuck语言的等价来证明SQL语言的图灵完备性,或不等价来证明非图灵完备.

就差一个数学大神了

三、如何证明一门编程语言是图灵完备的

一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。一个能计算出每个图灵可计算函数（Turing-computable function）的计算系统被称为图灵完备的。一个语言是图灵完备的，意味着该语言的计算能力与一个通用图灵机（Universal Turing Machine）相当，这也是现代计算机语言所能拥有的最高能力。图灵完备是什么意思呢？在可计算理论中，当一组数据操作的规则（一组指令集，编程语言，或者元胞自动机）满足任意数据按照一定的顺序可以计算出结果，被称为图灵完备（turing complete）。一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的，它（计算机设备）有能力执行条件跳转（“if”和“goto”语句）以及改变内存数据。如果某个东西展现出了图灵完备，它就有能力表现出可以模拟原始计算机，而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的（C++ template就是图灵完备的），都能解决内存有限的问题。图灵完备的机器都被定义有无限内存，但是机器指令集却通常定义为只工作在特定的，有限数量的RAM上。

四、什么是图灵完备语言

如果一个计算机语言具有图灵完备性（Turing Completeness），那么这个语言就是图灵完备语言（Turing-complete language）。

背景

艾伦·图灵

艾伦·麦席森·图灵（Alan Mathison Turing，1912.6.23- 1954.6.7），英国数学家、逻辑学家、密码学家和英国首位计算机科学家，被誉为计算机科学和人工智能之父。

他对计算机科学的发展有着很高的影响力，他用图灵机提供了算法和计算概念的形式化，图灵机可以被视为通用计算机的模型。他的图灵测试对人工智能的发展，作出了重要的、典型的、具挑战性的和持久的贡献。

图灵机

图灵机模型

在 1928年第八届国际数学家大会上，德国数学家希尔伯特（David Hilbert，1862- 1943）提出了关于数学的三个精辟问题：

First, was mathematics complete…（数学是完备的吗？）

Second, was mathematics consistent…（数学是一致的吗？）

And thirdly, was mathematics decidable?（数学是可判定的吗？）

希尔伯特的第三个问题又被称为判定性问题（Entscheidungsproblem）。为了证否这个命题，1936年，图灵发表了一篇论文，题为《论可计算数，及其在判定性问题上的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）。在这篇论文里，图灵提出了一种假设的计算装置，他称之为 A-Machine（Automatic Machine，自动机器），这就是图灵机（Turing Machine）。

可计算函数

艾伦·麦席森·图灵

1938年，在美国普林斯顿大学攻读博士学位的图灵，发表了一篇博士论文，题为《基于序数的逻辑系统》（Systems of Logic based on Ordinals）。在这篇论文里，图灵定义了可计算函数（Computable function）：

A function is effectively calculable if its values can be found by some purely mechanical process.

如果一个函数的值可以通过某种纯机械的过程找到，那么这个函数就可以有效地计算出来。

在作为特定计算模型的图灵机上产生的可计算函数，就被称为图灵可计算函数。

图灵完备性

如果一个计算系统可以计算每一个图灵可计算函数，那么这个系统就是图灵完备的；或者说，这个系统可以模拟通用图灵机。

图灵完备性也可以用来描述计算机语言的计算能力。

定义

图灵完备语言

具有图灵完备性的计算机语言，就被称为图灵完备语言。绝大多数的编程语言，都是图灵完备语言。这包括：

广泛使用的所有通用语言：

过程式语言，如 FORTRAN、Pascal等。

面向对象语言，如 Java、Python等。

多范式语言，如 Ada、C++等。

使用不太常见范式的大多数语言：

函数式语言，如 Haskell、Mercury等。

逻辑式语言，如 Logtalk、Prolog等。

声明式语言，如 SQL、XSLT等。

深奥的语言（Esoteric programming language），一种奇特的数学娱乐形式，程序员用极其困难但数学上图灵等价的语言来实现基本的编程结构。

非图灵完备语言

并非所有的计算机语言都是图灵完备的，例如标记语言，或者更恰当地称为“容器语言”或“数据描述语言”，就不是图灵完备的。

非图灵完备语言（Non-Turing-complete language），包括 HTML、JSON、XML、YAML等。