江湖上，有种说法流传已久：Excel 除了不能生孩子，其他都会。

抖音博主教你用 Excel 浪漫表白，函数一出手，既能彰显自己的内在，又能充值女票的少女心，一举两得。

图片来源于网络

82 岁的日本老人 Tatsuo Horiuchi，用 Excel 制作出一幅幅栩栩如生的画作，从整体到细节，不惧挑剔，作品被多个美术馆争相收藏。

图片来源于网络

同样是 Excel，别人能撩妹、能作画，而你除了查找、求和，啥也不会，是不是突然有种想要卸载的冲动？

壮士，手下留步。

前不久，微软宣布 Excel 经过进化，已经具备了图灵完备，成为全球第一大编程语言 (虽然才刚完成进化，奈何群众基础广泛，直接成为第一)。

从这个角度看，所有使用 Excel 的人，四舍五入就是程序猿/媛了。从此以后，简历上继「参与过上千亿项目」(双十一) 后，你还可以大方的写上：会编程。

俗话说，吃水不忘挖井人，那么问题来了：这个暗搓搓给你简历增光添彩的图灵完备，到底是个啥？

1、站在计算极限上的图灵机

关于图灵完备，百度百科上是这样解释的：在可计算性理论中，如果一系列操作数据的规则，可以用来模拟单带图灵机，那么它就是图灵完备的。

讲真，这种弯弯绕的概念解释，就像在通往知识的大门上挂了把锁，似对圈外来访者叫嚣：学术重地，闲人回避。

但是，如果你熟悉图灵机，这把锁便会不攻自破。

可能和很多人想的不同，图灵机并不是指某一台实体机器，而是一种想法，是图灵在 1936 年进行的一场思想实验：通过模拟人用纸笔进行数**算的过程，探索计算的极限。

假设从天而降一道数学题：13 × 21，回忆一下，你的数学老师是如何教你列竖式求解的？个位数相乘，对位相加，就能得出结果。

图片来源于网络

如果你留心就会发现，整个计算过程，虽然被分成了很多步，但不管相乘还是相加，每一步你要关注的，都只是当前位置上的数字，以及运算规则。

换句话说，求解的过程，就是笔尖不断的读写和**，直到运算结束，得出答案。

由此，图灵开始想象，假设有一条无限长的纸带，上面被分成了一个一个的小格子，每个格子最多只能出现一个字符。

这时，如果有一个读写头，不仅能读取当前格子的内容，还能遵循某种操作规则，通过在纸带上的位置**，对格子内容进行修改，那么，等到运行结束，就能输出结果。

图片来源于网络

这就是图灵机的原理，也是计算机的核心理论。

如果各位觉得文字不过瘾，可以了解一个叫做 Brain** 的编程语言，它能帮你更加直观地理解图灵机。

在很多人眼里，Brain** 是一款传奇的计算机编程语言，当然不是指名字。

Brain** 创建于 1993 年，最大的特点是极简，只包含八个字符：所有的操作，都是由这八种字符组合完成。

图片来源于网络

如果你在 brain** 中输入下面这段代码，猜猜会出现什么？

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

答案是：Hello World! (别眨眼，注意看动图最后一行)

图片来源于网络

这张动图，可以直观看到图灵机的运行原理，当然，牢记这 8 个字符，你也可以完成各种计算。

十分钟学会一门编程语言，你骄傲了吗？可以骄傲，但没必要。

Brain** 传奇的地方在于：它什么都能干，但干什么都不方便。如果你想深入感知图灵机，愿意上手试试自然是极好的，但如果想用它干别的，劝你放弃。

别看现在的计算机很强大，能孕育出各种人工智能，貌似无所不能，事实上，如今所有的计算机都是图灵机，包括量子计算机。在过去的数十年里，计算机的每一次进化，都是硬件和算法上的升级，核心始终未曾变化：图灵机就是计算的边界。

只包含一条纸带的图灵机，叫做单带图灵机，即使对它升级，安装更多的纸带和对应的读写头，**更多符号，把它改装成多带图灵机，大幅提升它的计算能力，却依旧改变不了事实：多带图灵机只是算的快些罢了，本质没有变化。

记住：图灵机做不了的事情，今天的计算机再强大，还是做不了。

2、可计算问题

图灵机有了，但它能解决哪些问题呢？

图灵给出的答案是：如果图灵机能被做成物理实体，它就能解决任意可计算问题。

可计算问题，是用数学的视角看世界，指通过某种算法，比如数手指、加减乘除、开立方根等，能够得出确切结果的问题。要知道，很多问题，虽然有答案，却是不可能找到算法来解答的。

来个无奖问答：以下六个选项中，哪些是可计算问题？

1、123456 × 654321 等于多少？

2、太阳为什么东升西落？

3、给定一个正整数，判断它是否为质数？

4、媳妇和妈掉水里，你先救谁？

5、给定一个字符串，判断某个字符是否存在？

6、美术馆着火，保画还是保猫？

很明显，答案是：1、3、5。

毕竟，像 6 这种保画还是保猫的问题，在奇葩说中都不一定辨的清楚，对计算机来讲，更是无法找到某种解法来得出答案。

图片来源于网络

但是，凡事都有例外，比如在可计算问题中，就存在一个不可计算问题：停机问题。

在解释什么是停机问题之前，我给各位先来点前菜，开开胃。

在某个城市中，有一位理发师，此人很有意思，他在宣传海报上写了这样一段话：“本人技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸，我对各位表示热诚欢迎。”

图片来源于网络

慕名而来找他刮脸的人，可谓是络绎不绝。

可是有一天，理发师早上起来照镜子，发现自己的胡子长了，便顺手拿起剃刀。

就在剃刀抵住胡须的那一刻，理发师在头顶缓缓打出一个问号：我到底能不能给自己刮脸呢？

如果我不给自己刮脸，那我自然就属于“不给自己刮脸的人”，也就可以给自己刮脸；但如果我给自己刮脸，那我就不属于“不给自己刮脸的人”，也就不能给自己刮脸。

能刮还是不能刮，这是个问题。

这个故事叫理发师悖论，而停机问题，就是计算机届的“理发师悖论”。

早些年，各位在使用电脑的时候，想必都在屏幕上见过一个小沙漏，它的出现，预示着你的电脑卡住了。

这里就有个问题：仅靠一个小沙漏，你根本无法判断电脑是彻底死机需要重启，还是电脑正在进行巨量运算，稍后就能恢复。

等还是不等，这是个问题。

此时，如果有一段程序，它可以检测全天下任何一个软件的运行情况，然后告诉你软件究竟是遇到了鬼打墙，陷入死循环需要重启，还是仅仅在正常计算，稍后就能恢复，那该有多好。

这便是停机问题：是否存在一个程序，它可以判断任意一个程序，究竟会在有限时间内结束，还是陷入死循环无法自行终止。

答案是，这样的软件不存在。

在自我判断过程中，软件需要调用自己，就像上面故事中的理发师一样，这种高阶逻辑不自洽的情况，自然不可能实现。

由上可知，抛开计算时长不谈，只要是可计算问题，图灵机就一定能够给出答案。

知道了什么是单带图灵机、可计算性理论后，我们回到今天的重点，来看看到底什么是图灵完备。

3、图灵完备性

重温一下概念：在可计算性理论中，如果一系列操作数据的规则，可以用来模拟单带图灵机，那么它就是图灵完备的。

有了基础知识打底，这就好理解了：如果一套操作规则，它可以解决图灵机能够解决的所有问题，就可以说它具备了图灵完备。

打个比方，假设图灵机是一把万能钥匙，它可以打开全天下的锁。有一天，张三、李四、王五、赵六分别造出了一把钥匙，尽管形状各不相同，有 U 型、L 型等，但只要它们也能打开全天下的锁，就说它们具备了图灵完备。

至于为什么图灵完备指的是操作规则，而不是图灵机本身，其实很简单：假设你面前有一台图灵机，但我告诉你，纸带的格子中不能有除 0 以外的任何字符，这样的图灵机便丧失了计算的意义，何谈图灵完备。

此处提一句，还有一个概念叫做「图灵等价」，它与可计算性理论相关，也非常好理解：你面前有一台计算机，如果它可以模拟图灵机，就可以说，它等同于图灵机。

更进一步说就是，通用图灵机可以用来模拟任何一台图灵机，进而模拟任何一台真实世界中计算机的计算能力。

「图灵等价」这个概念，看似简单枯燥，其实背后有很多值得推敲的东西，在现有计算机中，图灵完备的系统都是图灵等价的，很大程度上两者可以等同理解。有朋友对此感兴趣的话，可以延伸了解一下相关知识，比如 1935 年著名的丘奇定理：算法可计算函数都是递归函数。这里暂不展开讲解了。

如今，绝大多数编程语言都具备图灵完备，比如 C++、Java、Python。现在，Excel 也成功加入了这一行列，支持自定义函数，能够解决更多计算问题。

不过你可能想不到，除了编程语言，游戏其实也可以具备图灵完备。

不知各位有没有玩过一款游戏：《我的世界》。从理论上来说，这款游戏算得上是图灵完备。

图片来源于网络

《我的世界》是一款沙盒游戏，自由度极高。千万别小看这浓浓的像素风，在这个世界里，你可以通过放飞创造力，感受到科技的巨大能量。

前提是，你得有两把刷子。

在游戏中，普通玩家只能停留在采矿、建屋、互殴、溜宠等层面，高端玩家则不同。

图片来源于网络

游戏中有一个超级厉害的系统，叫做红石科技。它能实现模拟电路，带领玩家离开原始社会，进入半自动、乃至全自动化的工业时代。

玩家用铁锹挖出埋在地下的红石块，直接铺地上就是红石线，用熔炉烧制就变成石头，再通过一系列合成操作，就可以**红石火把、红石**、红石中继器 (延长红石**)等。

红石就是能量源，你也可以把它理解成电路，电力的意义不用我多说，想想电力**就知道。

我们来看看大佬们是如何用红石创造奇迹的。

来自复旦大学的季文瀚，用一年的时间，在《我的世界》中，建造了一个计算机雏形，命名为 Alpha21016。

图片来源于网络

Alpha21016 是个超大规模的集成电路，存储器堆叠起来，就有八层之多。它可以进行各种函数运算，比如加减乘除、三角函数，以及矩阵运算。

另一位大佬 Xcom6000，和其他十几位同伴一起，在《我的世界》中，建造了一个超光速运行的交通系统：可控珍珠炮。

图片来源于网络

Xcom6000 做了一个测试：朝珍珠炮中扔一颗珍珠，1040 颗早已就绪的 TNT，立刻开始超远距离**。28 秒后，珍珠落地，玩家被传送的距离长达 88065.38。

还有一位印度小哥，他在游戏中搭建了一个具有图像识别功能的神经网络：在游戏中的窗**写字，游戏中的计算机就能识别文字内容。

图片来源于网络

在红石系统中，红石电路搭配触发器等原件，就能实现图灵机的纸带功能；通过控制电路，就能进行读写，实现了图灵机中的读写头功能；再加上一系列自研的指令集和控制规则，从理论上来看，确实实现了图灵机。

在现实中，恐怕不会有人说：等着看吧，我要造出一种非图灵完备的语言。因为这句话听起来就很不高级。

但有一说一，图灵完备真的那么好吗？

在前面的故事中，我们已经知道，由于可计算问题中存在不可计算的特例，所以图灵机存在陷入死循环而导致程序崩溃的可能。一般来说，图灵完备与非图灵完备，二者最常见的一个区别就是：程序是否会出现无限死循环。

也就是说：在图灵不完备的情况下，每段程序都可以运行完，不会陷入死循环，而图灵完备则有可能陷入死循环。

正因如此，常混币圈的盆友们才总会听到这样一句话：比特币是非图灵完备，更安全；以太坊是图灵完备，更智能。

所以说，二者没有高下之分，放对了位置，各个都是人才。

参考资料：

1、http://fatiherikli.git**.io/brain**-visualizer/

文 | 木子Yanni

嗨，这里是浅黑科技，在未来面前，我们都是孩子。

想看更多科技故事，欢迎戳→：浅黑科技。