七月的 Use Your Head is Permitted 谜题非常有意思。谜题是设计一个只有五个状态（外加一个终止状态）的字符集大小为二且停机的五状态图灵机（状态转移后必须左右移动），另外要求所经过的状态转移次数，也就是步数尽可能大。在月末的时候，会公布所有提交答案选手的排名。

如果你对这个问题非常感兴趣，并想自己尝试解决这个问题的话，请先暂时跳过下面的文字。

在开始讲述这个故事之前，需要感谢同在新加坡的 P&P 将这个问题转述给我。

由于图灵机限制了状态的个数之后，总的个数就是有限的，于是停机的图灵机也只有有限个，所以必定有一个最大步数。于是我们纷纷开始对这个最大步数进行猜测，P&P 觉得这个数应该在一千以内，为区分，我认为范围是一千〇一至一万之间。

吃晚饭的时候，P&P 想出了一个能执行十步的图灵机，他妄想通过手工构造的方式得到最优解在我看来简直就是以卵击石也。

吃完晚饭，我提出通过遗传算法寻找最优解。在证明一些关于最优解的性质之后，我便开始实施自己的遗传算法计划。虽然本科数学建模课也学过遗传算法的理论，本科某个项目的时候也用到遗传算法，但实践还真是第一次。

第一步，随机生成一万个合法解，并计算每个图灵机的步数。基于当时的认识，我将时间复杂度超过一千的或者空间复杂度超过两百的图灵机都视为不会停机。

第二步，反复执行优选与繁殖的操作。每次选取最优的五千个最为上一代，随机选取两个杂交，生成五千个新的第二代，替换掉原来较差的五千个。杂交的方式是将两个图灵机的转移函数混合。

由于多年不碰 C 语言，写高效的链表结构排序压力很大，写错的概率几乎为一。于是乖乖投奔 Ruby 这种非常适合懒人的。不一会，遗传算法就写好了。

很快就出了一些结果，例如144步，195步，295步，364步。

但过了很久，都没有出更大的解。于是我断定，我的解应该挺大的了。结果 P&P 放弃手工构造之后，也写了一个遗传算法，得到了一个六百多步的解。他的算法与我不同之处在于，他在每次优选的时候，将两千个物种中的最优的五百个保留，另外随机生成五百个作为外来物种，进行杂交。

于是，我把自己的遗传算法也设计成了带有外来物种，但无奈，跑了两个多小时只得到了568步的结果。这个568步的图灵机，初始状态为 1，终止状态为 ，字符  作为空字符。

1021R 1101R 2031L 2141R 3040L 3130L 4051R 4121R 5010R 5121L

感觉是比不过了，还是洗洗睡吧。

第二天早晨，P&P 来敲门，让我猜他酝酿出了多大的结果。我说一千多吧。

他说，四万多步。

当时我就震惊了。

他将这个图灵机取名为 “Never” End Machine 。

其实在第一天有个小插曲。在我发布 Awesome Turing Machine 的第二天，有个叫 johnsonye 的用户写了一个名为 busy beaver 的图灵机，描述如下：

Just 5 states, but it’s so busy that you need to take a long.. long.. really long time to see it stop. （只有五个状态，但它实在太忙以至于你需要经过很长很长很长的时间才能看到它停下来。）

在写程序的间隙，我试图在我网站上运行了这个用户写得这个程序。但在中途，我自认为看出了规律，断言这个构造是不会停机了。感兴趣的读者可以去亲自运行一下。

免责声明，一切企图等待其停机，并因此造成不必要的人身伤亡或财产损失，请自行负责。

第二天，我们去询问了新加坡国立大学递归论学家杨越。杨老师说这个问题叫做 Busy Beaver 问题，建议我们去查一查相关资料。

有的热心的读者可能会问，那只要给我足够长时间就一定能枚举出来吧？计划是这样的，给我任意一个图灵机，同时开两台计算机，一台负责去运行这个图灵机，看看它能不能停机；同时，另外一台电脑去搜索一个数学证明，证明这个图灵机是不能停机。迟早其中有一台电脑会给我一个结果。

但实际上，这个梦想是无法实现的。最简单的反驳方式是：停机问题是不可计算的。当然在回答这个问题之前，需要对什么是一个数学证明进行定义，例如靠塔罗牌占卜一个图灵机是否停机不算是数学证明。

更热心点的读者可能要质问，停机问题不可计算说的是对于所有的图灵机，不存在一个普适的程序，判定任意给定的图灵机是否停机。但是说不定对于状态数为五的图灵机，就存在这样的程序去判定他们每一个是否停机。最有力的证据是，我们能通过之前提到的“开两台计算机”的方法去判定状态数为一的图灵机。

实际上，以上的对话发生在我和 P&P 之间，但这个可能扯开去有点远了，我打算放在另外的一篇日志里展开，如果要写的话，标题就定为《一个有限主义者与一个柏拉图主义者的对话》。当然，我也可能过了一阵忘了这个事情，也说不定。

说回正题，我们马上回去就维基百科了 Busy Beaver ，说来惭愧，当初我自己写日志时用 Busy Beaver 为名写了一个左右不断循环的图灵机，殊不知这背后大有文章。

如果你真心想自己尝试这个问题的话，强烈建议你忽略下面的文字。

这个问题叫做 Busy Beaver 5 问题，对应的最大步数的函数记为$S(5)$，对于较小的$S$函数值已经确定，但$S(5)$尚未确定，只知道以下不等式：

也就是说，存在一个字符集大小为二的五状态图灵机，经过 47,176,870 之后再停机。

当时，我又震惊了。

我默默将 johnsonye 于4月13日在我网站上构造的 busy beaver 放到我的 Ruby 程序中运行，47,176,870 步停机。

数学已经不止一次挑战着我们的想象力。