图片来源于网络
慕名而来找他刮脸的人，可谓是络绎不绝。
可是有一天，理发师早上起来照镜子，发现自己的胡子长了，便顺手拿起剃刀。
就在剃刀抵住胡须的那一刻，理发师在头顶缓缓打出一个问号：我到底能不能给自己刮脸呢？
如果我不给自己刮脸，那我自然就属于“不给自己刮脸的人”，也就可以给自己刮脸；但如果我给自己刮脸，那我就不属于“不给自己刮脸的人”，也就不能给自己刮脸。
能刮还是不能刮，这是个问题。
这个故事叫理发师悖论，而停机问题，就是计算机届的“理发师悖论”。
早些年，各位在使用电脑的时候，想必都在屏幕上见过一个小沙漏，它的出现，预示着你的电脑卡住了。
这里就有个问题：仅靠一个小沙漏，你根本无法判断电脑是彻底死机需要重启，还是电脑正在进行巨量运算，稍后就能恢复。
等还是不等，这是个问题。
此时，如果有一段程序，它可以检测全天下任何一个软件的运行情况，然后告诉你软件究竟是遇到了鬼打墙，陷入死循环需要重启，还是仅仅在正常计算，稍后就能恢复，那该有多好。
这便是停机问题：是否存在一个程序，它可以判断任意一个程序，究竟会在有限时间内结束，还是陷入死循环无法自行终止。
答案是，这样的软件不存在。
在自我判断过程中，软件需要调用自己，就像上面故事中的理发师一样，这种高阶逻辑不自洽的情况，自然不可能实现。
由上可知，抛开计算时长不谈，只要是可计算问题，图灵机就一定能够给出答案。
知道了什么是单带图灵机、可计算性理论后，我们回到今天的重点，来看看到底什么是图灵完备。
3、图灵完备性重温一下概念：在可计算性理论中，如果一系列操作数据的规则，可以用来模拟单带图灵机，那么它就是图灵完备的。
有了基础知识打底，这就好理解了：如果一套操作规则，它可以解决图灵机能够解决的所有问题，就可以说它具备了图灵完备。
打个比方，假设图灵机是一把万能钥匙，它可以打开全天下的锁。有一天，张三、李四、王五、赵六分别造出了一把钥匙，尽管形状各不相同，有 U 型、L 型等，但只要它们也能打开全天下的锁，就说它们具备了图灵完备。
至于为什么图灵完备指的是操作规则，而不是图灵机本身，其实很简单：假设你面前有一台图灵机，但我告诉你，纸带的格子中不能有除 0 以外的任何字符，这样的图灵机便丧失了计算的意义，何谈图灵完备。
此处提一句，还有一个概念叫做「图灵等价」，它与可计算性理论相关，也非常好理解：你面前有一台计算机，如果它可以模拟图灵机，就可以说，它等同于图灵机。
更进一步说就是，通用图灵机可以用来模拟任何一台图灵机，进而模拟任何一台真实世界中计算机的计算能力。
「图灵等价」这个概念，看似简单枯燥，其实背后有很多值得推敲的东西，在现有计算机中，图灵完备的系统都是图灵等价的，很大程度上两者可以等同理解。有朋友对此感兴趣的话，可以延伸了解一下相关知识，比如 1935 年著名的丘奇定理：算法可计算函数都是递归函数。这里暂不展开讲解了。
如今，绝大多数编程语言都具备图灵完备，比如 C 、Java、Python。现在，Excel 也成功加入了这一行列，支持自定义函数，能够解决更多计算问题。
不过你可能想不到，除了编程语言，游戏其实也可以具备图灵完备。
不知各位有没有玩过一款游戏：《我的世界》。从理论上来说，这款游戏算得上是图灵完备。
图片来源于网络
《我的世界》是一款沙盒游戏，自由度极高。千万别小看这浓浓的像素风，在这个世界里，你可以通过放飞创造力，感受到科技的巨大能量。
前提是，你得有两把刷子。
在游戏中，普通玩家只能停留在采矿、建屋、互殴、溜宠等层面，高端玩家则不同。
图片来源于网络
游戏中有一个超级厉害的系统，叫做红石科技。它能实现模拟电路，带领玩家离开原始社会，进入半自动、乃至全自动化的工业时代。
玩家用铁锹挖出埋在地下的红石块，直接铺地上就是红石线，用熔炉烧制就变成石头，再通过一系列合成操作，就可以获得红石火把、红石信号、红石中继器 (延长红石信号)等。
红石就是能量源，你也可以把它理解成电路，电力的意义不用我多说，想想电力革命就知道。
我们来看看大佬们是如何用红石创造奇迹的。
来自复旦大学的季文瀚，用一年的时间，在《我的世界》中，建造了一个计算机雏形，命名为 Alpha21016。
图片来源于网络
Alpha21016 是个超大规模的集成电路，存储器堆叠起来，就有八层之多。它可以进行各种函数运算，比如加减乘除、三角函数，以及矩阵运算。
另一位大佬 Xcom6000，和其他十几位同伴一起，在《我的世界》中，建造了一个超光速运行的交通系统：可控珍珠炮。
