经常在讲编程语言的书或文章里面看到图灵等价（Turing equivalence）和图灵完备(Turing completeness)，但却不知道这两个词的精确含义和区别。本文简单记录下图灵完备。
一、图灵完备的编程语言是什么意思呢？先来看一个示例：
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
有点懵圈的感觉，这段代码是一门叫做 BrainFuck 的语言的语法。
输出结果也是计算机世界各种语言的第一个权威示例： Hello World!
二、Brainfuck是一种极小化的计算机语言，它是由Urban Müller在1993年创建的。由于fuck在英语中是脏话，这种语言有时被称为brainf*ck或brainf**k，甚至被简称为BF。
这门语言简单到只有8种指令构成(字符标识)：
what。还是翻译成c来看看：(假设ptr是char*类型):
三、上面说了这么多BrainFuck，跟图灵完备有毛关系啊。其实BrainFuck的设计者只是为了
建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。
也就是说，别看它长这个样，它可是非常有代表性的、图灵完备的指令式编程语言（它有别于声明式编程语言和函数式编程语言）
图灵完备的语言，根据wiki权威的解释：在可计算理论里，一个数据操作规则的系统（比如：指令集、编程语言、细胞自动机）被称作图灵完备或者通用计算的，当且仅当它可以被用来模拟单带图灵机。
换言之：“可以用来模拟图灵机的语言可以被称作是图灵完备的语言”。这里又有了另一个概念“模拟图灵机”。
模拟图灵机，根据权威的解释：“它可以计算一切可以用一个算法计算的问题”。 这解释也是没谁了，讲了跟没讲一样。下面第四点直接上干货了。
四、对于指令式编程语言来说，图灵完备有两个要求：
- 有循环或递归(能够写不终止的程序,如 while(true){}; )
- 具有读写一定数量的数据的功能。简单来说就是要有数组的概念。
五、所以，如果一门语言支持 if、while、goto 和 array 的概念，基本上就可以被称为图灵完备的语言了。
但是，具备这几个概念只是一门语言图灵完备的充分不必要条件。换句话说，即使不具备以上概念，一门语言依然可以使图灵完备的。
感觉以上对于我们实际编程而言并没有什么卵用，全当科普吧。
参考：
https://en.wikipedia.org/wiki/Brainfuck
https://en.wikipedia.org/wiki/Universal_Turing_machine
可以