关于图形完备性的理解。
转载：2019/10/13 什么是图灵完备？ - 知乎
https://www.zhihu.com/question/20115374 1/5
这是一篇旨在帮助理解图灵机及相关概念是什么，而非证明其正确性的回答，它包含以下内容：
- 什么是图灵机
- 图灵机可以解决什么问题
- 什么是图灵完备
- 直观理解图灵完备——Brainfuck语言
1. 什么是图灵机
图灵机（Turing Machine）是图灵在1936年发表的 “On Computable Numbers, with an
Application to the Entscheidungsproblem”（《论可计算数及其在判定性问题上的应用》）中提出的
数学模型。既然是数学模型，它就并非一个实体概念，而是架空的一个想法。在文章中图灵描述了它是
什么，并且证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。
图灵机的结构包括以下几个部分：
一条无限长的纸带（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个
字符（symbol）。
一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空
白字符（blank），意思是此格子没有任何字符。
一个读写头（head），可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容，此
外也可以每次向左/右移动一个格子。
一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终
止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。如果你了解有限状态机，它
便对应着有限状态机里的状态。
一个有限的指令集（instructions table），它记录着读写头在特定情况下应该执行的行为。可以想象读
写头随身有一本操作指南，里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时，擦
除，改写为1，并向右移一格。此外，令下一状态为运行。”这样的命令。其实某种意义上，这个指令
集就对应着程序员所写下的程序了。
图灵机结构
在计算开始前，纸带可以是完全空白，也可以在某些格子里预先就有写上部分字符作为输入。运算开始
时，读写头从某一位置开始，严格按照此刻的配置（configuration），即：
当前所处位置
当前格子内容
来一步步的对照着指令集去进行操作，直到状态变为停止，运算结束。而后纸带上留下的信息，即字符
的序列（比如类似“…011001…”）便作为输出，由人来解码为自然语言。
要重申一下，以上只是图灵机模型的内容，而非具体的实现。所谓的纸带和读写头都只是图灵提出的抽
象概念。为便于理解打一个比方。算盘虽然不是图灵机（因为它没有无限长的纸带，即无限的存储空
间），但它的行为与图灵机一致。每一串算珠都是纸带上的一格，一串算珠上展示的数字便记录着当前
格中的字符（可以是空白，可以是 12345 ）。人类的手即是读写头，可以更改每串算珠的状态。算盘
的运行遵循人脑中的算法，当算法结束，算盘停机。
2. 图灵机可以解决什么问题
在文章中，图灵所做的事是证明了，假设上述模型里所说的功能都能被以某种形式物理实现，那么任意
可计算问题都可以被解决。这里所说的可计算问题，涉及到计算理论（Computation Theory）的概
念。这个领域的概念很繁杂，先简单梳理一下。
在计算机领域，或者说自动机领域，我们研究的一切问题都是计算问题（Computational
Problem）。它泛指一切与计算相关的问题。
A computational problem is a mathematical object representing a collection of questions that computers might be able to solve.
计算问题的一些举例：
- 给定一个正整数 n，判断它是否是质数
- 给定一个 01 序列，把它们按位取反
- 给定一个字符串，判断某个字符是否存在，及查找存在位置
- 给定一个逻辑蕴含的命题，求它的逆否命题
非计算问题的例子：
- 今晚吃什么
- 为什么太阳从东边升起
计算问题有的可以解决，有的不可解决。这就引出了计算问题的可计算性（Computability）。它可以
被理解为“是否存在一个算法，能解决在任何输入下的此计算问题”。如上面的问题 1，我们当然可以
找到一个算法来解决判断任意正整数 n 是否为质数的问题（比如从2遍历到 n-1，看 n 是否可以整除
它）。所以，问题 1 就是可计算的。
也有一些不可计算的计算问题，比如著名的停机问题（Halting Problem）。它的表述是这样的：给定
一段程序的描述和该程序的一个有效输入，运行此程序，那么程序最终是会终止，还是会死循环下去？
Halting Problem: given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.
这个问题很绕人，有点像那个著名的理发师悖论，但它确实是一个计算问题。更具体的，它是一个不可
判定问题（Undecidable Problem）。即不存在一个通用算法，可以在任意输入下解决此问题。图灵在
文章里很优雅的用反证法推翻了假设“假设有这么一个算法可以解决任何停机问题”，从而证明了这样
的算法并不存在。具体证明过程网上的资料非常丰富，我就不再花篇幅了。
回到这一节的主题。简而言之，对于一个问题，对于任意输入，只要人类可以保证算出结果（不管花多
少时间），那么图灵机就可以保证算出结果（不管花多少时间）。
3. 什么是图灵完备
图灵完备性（Turing Completeness）是针对一套数据操作规则而言的概念。数据操作规则可以是一门
编程语言，也可以是计算机里具体实现了的指令集。当这套规则可以实现图灵机模型里的全部功能时，
就称它具有图灵完备性。直白一点说，图灵完备性就是我给你一工具箱的东西，包括无限内存、if/else
控制流、while 循环……那么你现在图灵完备了吗？
概念本身倒是非常直观，但整件事似乎还是让人云里雾里。我曾经一直不懂的就是为什么图灵给出的那
个命题是正确的。换句话说，凭什么有了纸带以及其他的那一套东西，就可以自信解决任意可计算问题
呢？尽管我不能通读他的那篇论文里的证明，但是通过一门叫做 Brainfuck 的编程语言，还是可以获得
一些直觉。
4. 直观理解图灵完备——Brainfuck 语言
如今主流的编程语言（C++，Java，Python，以及等等等等）都是图灵完备的语言。关于语言优劣之
争也只是在其封装、优化等方面，以及因为这些区别而产生的“不同语言适用于不同情况”的争执。如
果我们回到最底层，就会发现它们可以实现的功能其实完全一样，并且本质上就是一个图灵机。
在1993年，Urban Müller 发明了 Brainfuck 语言。这门语言可以说是编程语言界的 helloworld 了
——它一共只含有 8 个有效字符，每个有效字符就是一条指令。语言虽然极致轻量，它却是一门图灵完
备的编程语言。如果能理解它的工作原理，那么对于理解图灵机是有很大帮助的。
Brainfuck is fully Turing-complete.
先贴上一段 BF 的代码，体验一下它的画风：
1 | +++++ +++++ initialize counter (cell #0) to 10 |
这个程序编译运行后，控制台打印 “Hello World!”。
BF 的工作机制与图灵机高度一致。首先它存储数据的方式是一个不限长的一维整数数组，里面的数值
全部初始化为 0。此外，有一数据指针，每一时刻都指向数组的某一任意元素。指针可以向左/右移动，
也可以读取/修改当前值。
语言里的 8 个有效字符分别是：
1 | > |
程序跳转回与之对应的 [ 处
有了这些工具，我们可以很快做出一个计算乘法的程序。因为 ASCII 表中 ‘A’ 对应的值为 65，可以使
用 5 * 13 算出 65 并输出得到字符 ‘A’。
1 | +++++ |
把指针初始处的格子命名为 cell 0，cell 0 右边的那个格子命名为 cell 1。那么第一句将其递增 5 次变
为 5。然后，循环执行“右移指针，递增 13 次， 左移指针，递减 1 次”。当 cell 0 的值最终被递减为
0 的时候，循环结束。此时 cell 1 的值执行了 5 次“递增 13 次”的操作，即 65。指针右移至 cell 1，
输出此格子，则在终端会看到 ‘A’。