软硬件融合技术内幕 基础篇 (2) —— 罪恶政权迫害世界和平功臣致死的故事

在上期，我们提出了一个命题：

小霸王学习机能够作为服务器使用吗？

实际上，决定这个问题的核心问题是：图灵完备。

先说结论：小霸王学习机的处理器 理光6502，是图灵完备的，因此理论上小霸王学习机可以作为服务器。

图灵完备这个术语是著名的计算机科学家艾伦·图灵提出的。

20世纪30年代，纳粹德国开始设计建造新一代战列舰，并以历史上的“铁血宰相”俾斯麦的名字予以冠名。1940年，俾斯麦号正式服役。

俾斯麦号排水量达5万吨，拥有160000马力的动力功率，航速30节，主炮口径380mm，可发射重800千克的被帽穿甲弹和高爆弹，并装备了当时先进的368MHz米波雷达和光学测距仪。

1941年5月，在纳粹德军发起的“莱茵演习”作战行动中，盟军海军与俾斯麦号遭遇，以胡德号战列巡洋舰被击沉为代价，击伤了俾斯麦号。三天后，由于德军的加密电文被监听后破译，盟军集中了42艘战舰，包括2艘航空母舰、3艘战列巡洋舰和5艘战列舰，以鱼雷轰炸机为先导，齐力同心，让满载纳粹野心的“俾斯麦号”成为了沉没海底的残骸。

在破译纳粹德国的密电中，大科学家艾伦·图灵居功甚伟。然而，这位为打败法西斯实现世界和平作出卓著贡献的功臣，在美国工作生活期间，却因为个人的隐私，受到残酷的精神和肉体方面的迫害，最终，他在1954年6月7日，吃了一口被氰化钠浸泡过的苹果，以结束自己41年的生命的方式，逃离了这个反人类专制政权的魔掌，同时，也对这个罪恶的政权，发出了足以铭刻在人类历史上的控诉的最强音。

图灵的发明是一台自动化密码破解机，也就是现代电子计算机的雏形。基于密码破解机，图灵破译了纳粹德国几乎所有的密电通信。

密码破解机的内核是所谓的“图灵机”。图灵机（Turing Machine）是图灵在1936年发表的 《On Computable Numbers, with an Application to the Entscheidungsproblem》（《论可计算数及其在判定性问题上的应用》）中提出的数学模型。图灵在论文中证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。

图灵机的结构包括以下几个部分：

1. 一条足够长的纸带（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个字符（symbol）；
2. 一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符。
3. 一个读写头（head），可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容，此外也可以每次向左/右移动一个格子。
4. 一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。
5. 一个有限的指令集（instructions table），它记录着读写头在特定情况下应该执行的行为。

如下图所示：

我们可以想象，读写头连接了一本操作步骤手册，里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时，擦除，改写为1，并向右移一格。此外，令下一状态为运行。”这样的命令。

在计算开始前，纸带可以是完全空白，也可以在某些格子里预先就有写上部分字符作为输入。运算开始时，读写头从某一位置开始，严格按照当前格子内容和指令要求进行操作，直到状态变为停止，运算结束。而后，纸带上留下的信息，即字符的序列（比如类似“...011001...”）便作为图灵机的输出。

为了方便大家的理解，让我们再翻出一样童年的记忆：

算盘实际上就是一种图灵机。

算盘的每一串算珠是图灵机纸带上的一格，一串算珠上展示的数字便记录着当前格中的字符。人类的手即是读写头，可以更改每串算珠的状态，执行的指令是：

一上一

二上二

三下五去二

四去六进一

五上五

六上一去五进一。。。

当算法结束，算盘停机。

根据前文的理论，算盘作为图灵机的一种，可以计算出任何可计算的问题，包括原子弹和氢弹的数学模型：

这里所说的可计算问题，涉及到计算理论（Computation Theory）的概念。

计算问题泛指一切与计算相关的问题，如

“给定一个正整数 n，判断它是否是质数”，

或

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

(leetcode第887题)

与此对立的是非计算问题：

晚上吃什么？

你在鹅民公社拿Q米换的衣服怎么这么破？

为什么小美的男朋友带她去三亚玩，你却只舍得带我去逛海雅城？

为什么你微信里面和那个绿茶婊的聊天记录是空白的？

你们男人能不能少说几句瞎话？

你还有多少事情瞒着我？

我和你妈同时掉水里你先救谁？

显然，这些非计算问题超出了正常的范畴，不是方老师这样高尚的人，纯粹的人，有道德的人，脱离了低级趣味的人和有益于人民的人能够搞定的，建议去豆瓣网问。

计算问题有的可以解决，有的不可解决。可以解决的计算问题，就是所谓的可计算问题。它可以被理解为“是否存在一个算法，能解决在任何输入下的此计算问题”。如上面的问题 1，我们当然可以找到一个算法来解决判断任意正整数 n 是否为质数的问题（比如从2遍历到 n-1，看 n 是否可以整除它）。所以，问题 1 就是可计算的。

图灵指出，对于一个问题，对于任意输入，只要人类可以保证算出结果（不管花多少时间），那么图灵机就可以保证算出结果（不管花多少时间）。

图灵完备性（Turing Completeness）则是针对一套数据操作规则而言的概念。

数据操作规则可以是一门编程语言，也可以是计算机里具体实现了的指令集。当这套规则可以实现图灵机模型里的全部功能时，就称它具有图灵完备性。直白一点说，图灵完备性就是包括足够的内存、if/else 控制流、while 循环……在内的一系列的工具。

基本上，目前常见的CPU都是图灵完备的。工程师们的努力，都是在设法为计算机提供更大的存储能力和更强的计算能力……

这些话题，容下期详细描述。

请思考：

方老师以前写的文章 《插播：一道有趣的程序题 (上)》里面，提到的机器人是不是图灵完备的？