专业学习 | 什么是图灵完备

坐公交车时突然想到 Brainfuck 这门语言，然后想到它是图灵完备的^[2]，之前一直靠这个词来装逼，然而细想好像说不清楚什么是图灵完备，于是翻了翻图灵完备的词条^[3]。我们说一门编程语言是图灵完备的，意思是指它具有模拟图灵机的能力。另外还有一个相近的概念叫图灵等价，即如果两台计算机可以互相模拟，那么这两台计算机就是图灵等价的。

那么什么是图灵机呢，如果在现代计算机系统中去理解的话，就是具有循环和判断的能力、并且可以操作内存的系统，以下是维基百科上更为详细一些的解释^[2]：

图灵机从数学上描述了一个在纸带上操作的机器。纸带上有一个个符号，机器可以读写这些符号。图灵机的操作由一个有限指令集集合定义，比如“在状态42，如果当前符号是0，那么就写入1；如果当前符号是1，那么就进入状态17，如果此时看到的符号是0，那么就写入1并且将状态转换成6” 。更精确地说，图灵机由以下部分组成：

1. 一条被分成一个个小格子的纸带，每一个小格子都包含一个有限字符集中的符号，该字符集中还有一个特殊的空白符。这条纸带可以任意向左或者向右延长，在一些理论中，这条纸带只能向右延伸，不管怎么说，纸带总是足够使用
2. 一个位于纸带上方的读写头，它能够读写下方小格子中的符号，每次读写头可以向左或者向右移动一个格子（有的模型中是读写头固定，纸带移动），也可以不动
3. 一个存储图灵机当前状态的状态寄存器，在图灵机运行之前，状态寄存器中是特殊的起始状态
4. 一个有限的指令表，假设当前图灵机的状态是$q_i$，读写头下方的符号是$a_j$，该指令表可以控制图灵机依次执行以下操作：
   1. 写入或者擦除当前的符号(用$a_{j1}$替换$a_j$)
   2. 移动读写头，向左向右或者保持不动
   3. 保持当前状态或者进入下一个状态(从状态$q_i$进入状态$q_{i1}$)

从这个角度去看，图灵完备对于一门编程语言来说并不是特别难以达到的目标。实际上，目前我们能接触到的编程语言中，只有一些DSL是非图灵完备的，如HTML、CSS、SQL等^[4]。在所有的图灵完备语言中，最简单的就是Brainfuck了^[1]，它只有8种运算符，其编译器也只有200多个字节。虽然看起来很Braing Fucking，但是理论上它确实可以完成任何一门编程语言的工作。以下是它的8种操作和对应的C语言：

操作	C语言
>	++ptr;
<	--ptr;
+	++*ptr;
-	--*ptr;
.	putchar(*ptr);
,	*ptr = getchar();
[	while (*ptr) {
]	}

如果用Brainfuck来写”Hello World”的话，代码差不多是下边的样子：

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

图灵机的一个特点是其无法判定停机问题^[5]。停机问题定义很简单，即是否能找到一个程序，它可以判定任意一个程序是否可以在有限时间（步数）内结束运行。停机问题是一种自我指涉问题，类似的还有经典的理发师悖论，“我只给不给我刮胡子的人刮胡子，那么我给不给我自己刮胡子？”。

这个问题的证明也很简单，假设程序P对于任意输入I都可以判定其是否停机，如果停机就输出1，否则输出0，那么现在给出另外一个程序F，它在内部调用了P，并且以自身作为输入，即F(F)，如果F停机，即P(F)输出1，那么F(F)就无限循环；如果F无限循环，即P(F)输出0，那么F就立刻停机。构成了矛盾的状态，因此可以判定程序是否停机的程序P是不存在的。

参考文献

[1]. Wikipedia. Brainfuck[EB/OL]. https://en.wikipedia.org/wiki/Brainfuck. 2019-03-19/2019-03-26

[2]. Wikipedia. Turing machine[EB/OL]. https://en.wikipedia.org/wiki/Turing_machine. 2019-03-05/2019-03-26

[3]. Wikipedia. Turing completeness[EB/OL]. https://en.wikipedia.org/wiki/Turing_completeness. 2019-03-16/2019-03-26

[4]. yannis. Are there mainstream general-purpose non-Turing complete languages available today?[EB/OL]. https://softwareengineering.stackexchange.com/questions/202488/are-there-mainstream-general-purpose-non-turing-complete-languages-available-tod. 2013-06-24/2019-03-26

[5]. Wikipedia. Halting problem[EB/OL]. https://en.wikipedia.org/wiki/Halting_problem. 2019-03-05/2019-03-26