第169章 幽灵机器的终焉（1 / 2）
九月十二日，正式开课后的第一个下午。
六点零七分。
项目组会议室的大屏幕上，孤零零地掛著一句写於1990年的判断。
【人们永远无法证明：Σ=4098，s=47176870。】
艾伦布雷迪（allenbrady）。
对於繁忙海狸（bybeaver）问题的人来说，这都是一个绕不开的名字。
1983年，他完成了四状態繁忙海狸的证明。
而五状態繁忙海狸那台著名冠军机，由马克森（arxen）和邦特罗克（buntrock）在1989年找到。
那是一台宛如奇蹟般的机器，它会在全白纸带上运行整整四千七百一十六万八千八百七十步，然后在停机的那一瞬间，留下四千零九十八个“1”。
冠军早已找到，甚至被人们瞻仰了三十多年。
但问题在於，谁也无法在数学和逻辑上给出一个坚不可摧的证明：在这个庞大的搜索空间里，在等价约化前超过十六万亿张转移表、经过树形规范化后仍需处理上亿台代表机器的搜索空间里，谁也无法排除另一台藏得更深、跑得更久的机器。
五个状態。
两个符號。
一张只有十个转移位置的表格。
这就是五状態图灵机的全部构成。
它的规则是如此简单。
任何人，只要花上几分钟，都能把它的规则抄在一张便签纸上。
然而，正是这近乎原初的简单，孕育出了连现代超级计算机都无法穷尽的复杂性。
几代最顶尖的研究者前赴后继，先后尝试循环判定、符號压缩、闭合纸带语言、有限自动机约简和形式化验证，却始终无法给这两个数字盖上最后一枚印章。
32年前，布雷迪在耗尽了无数心血后，乾脆把它写进了自己的预测清单。
永远无法证明！
乔闻鐸今天又把这句话放了出来。
这位在形式化验证领域摸爬滚打了半辈子的老教授，此刻双手撑在会议桌的边缘，静静地注视著大屏幕。
他之所以放出这句话，是因为大屏幕右侧，还掛著项目组全库復验后的最后一行状態提示。
【unresolved_aches：1】
九月十日，当大一新生江临刚刚完成军训物资清退，还在操场上听著院系入学教育的喧闹时，两支被严格物理隔离的实现组，已经悄然完成了共享可信核的独立盲测。
记住我们101看书网
那是一场不见硝烟的惨烈战爭。
中间出现过一次足以让整个团队惊出冷汗的分歧。
当时，ocal实现组在处理一段裁剪纸带两端空白格的逻辑时，由於一个极其隱蔽的思维盲区，將底层容器的起始下標误当成了逻辑坐標，直接吞掉了一段本该保留的平移量。
第三方测试组毫不留情地抽取了最小復现件。
江临被紧急召回，他没有看两边的代码，而是直接依据冻结在保险柜里的规范文档，给出精確的解释。
两支团队被迫推翻之前的进度，重新编译可执行文件，从第一个隱藏样例开始，全量重跑了所有的测试用例。
那是令人窒息的几个小时。
最终的结果传回时，所有人都屏住了呼吸。
rt通过。
ocal通过。
两份裁决摘要的哈希值在校验器中逐位比对，绿色的atch亮起，宣告一致。
九月十一日，安全教育与学籍补项按校歷有条不紊地推进。
与此同时，全库復验也在同一天轰然启动。
八千八百六十六万四千零六十四台种子库机器，连同项目组这几个月来日夜不休生成的非停机见证，被像倾倒进巨型熔炉的矿石一样，分批送进两套互不通信的核验器中。
精確循环机制启动。
平移循环机制启动。
反向不可达判定树展开。
成百万、上千万台机器在经过严苛的审查后，从待判队列里消失，化为资料库中一行行確定的绿色记录。
旧证书里的格式错误、机器哈希错配、甚至是多年前留下的坐標约定污染，被核验器无情地逐一退回，强制重新生成。
每一台被標记为非停机的机器，都必须给出一份无可辩驳的证据。
一条能够从机器底层语义层面重新走通的证明路径，绝不允许任何概率性猜测。
到九月十二日下午，现有证书全部復验完成。
八千八百多万台机器构成的浩瀚星海中，只剩下最后一台。
最后一台的状態栏里没有reject，只有unknown。
项目组至今拿不出任何可核验见证。
乔闻鐸关掉布雷迪那句沉重的预测，拿起遥控笔，將最后一台机器的转移表放大，直到它占据了整个屏幕的中心。
【skelet#17】
只有五行，两列。
十个转移位置。
表格小得一张便签纸就能抄下。
“这台机器来自格奥尔基skelet格奥尔基耶夫在2003年公布的四十三台holdouts，因此被称为skelet#17。”
乔闻鐸站在屏幕左侧，声音在空旷的会议室里显得格外低沉。
“我们尝试了所有常规武器，精確循环无效，平移循环无效，反向不可达集合我们强行展开到了第九层，但状態数量在那之后开始呈现出恐怖的指数级膨胀，內存直接溢出。”
乔闻鐸的语气中透出深深的疲惫。
“现有最长轨跡，已经超过了两百亿步。仍然没有停机。更可怕的是，它也没有进入任何能被现有规则捕捉的重复结构。”
周述在一旁接手操作。
他深吸了一口气，將一张庞大的空间—时间图调了出来。
黑白相间的纸带轨跡瞬间占满了整面墙的屏幕，仿佛某种远古生物的复杂基因图谱，又像是高空俯瞰下的异星城市遗蹟。
“这就是它两百亿步的生命歷程。”周述指著屏幕上那些密密麻麻的纹理说，“读写头在越来越宽的区间里来回扫动，像一个不知疲倦的织布工。它写入，擦除，再折返。图像的外沿在不断扩张，纸带越来越长。”
周述说著，放大了其中一个区域。
“但是內部却找不到两个完全相同的截面，继续模擬下去没有任何意义。”
周述转头看向眾人，语气篤定。
“两百亿步和两千亿步，甚至两万亿步，在这里没有本质区別。只要它还能在边界上生成新的纸带结构，只要它的行为没有展现出闭合的周期性，我们就永远等不到循环。”
会议桌的另一端，叶寧揉了揉布满红血丝的眼睛，调出项目组连日来熬夜赶出的三份厚厚的分析报告。
“项目组先后尝试过三条分析路线。有人把它看成一种广义的二进位计数器，试图用进位法则去框定它；也有人怀疑它在模擬某种类似於考拉兹猜想的动態叠代，所谓的3n+1变体。”
叶寧继续翻页。
“我们尝试了三套最先进的压缩模型去解释它的轨跡。在局部，这些模型確实能完美契合。但只要推到边界归併的极端情况，只要读写头触碰到那个特定的0与1的交界，模型就会瞬间断裂，所有的预测都会失效。”
她把最后一份报告翻到末页，展示给所有人。
【结论：现有抽象不足以排除未来停机。】
屏幕右上角，那个数字仍然是1。
就像悬在整个团队头顶的达摩克利斯之剑。
只要这个1还在那里，布雷迪的预言就依然生效。
四千零九十八就只能被称为下界，四千七百一十六万八千八百七十也仅仅只是一个候选值。
整个五状態繁忙海狸问题四十年的歷史，几代人的心血，此刻全都被死死压在这张只有十个格子的微小转移表上。
乔闻鐸转过头，將目光投向了坐在会议桌最末端的江临。
这个名义上的大一新生，穿著一件普通的纯色t恤，面容平静得像是一汪没有波澜的湖水。
但就是他在过去的几天里，一次又一次地展现出了远超常人的敏锐与决断。
“共享可信核已经圆满完成了它的任务。”乔闻鐸对江临说，语气中不无期待与託付，“现在，我们缺的是一份能被它检查、能经受住数学界审视的见证。”
江临的视线从那张转移表上扫过，在脑海中快速重构著这十个转移规则背后的代数结构。
十几秒后，他抬头说道：“把单步动画关掉。”
周述愣了一下，隨即敲下空格键，按下了暂停。
屏幕上那片令人眼晕的黑白轨跡，呈现出庞大到令人绝望的纸带状態。
“只保留读写头每次回到最左侧分隔符的配置。”江临站起身，走向前方的白板，“中间那些繁杂的来回扫动，全部隱藏，状態属性也要保留下来。”
叶寧心领神会，立刻拖出系统里的轨跡筛选器，双手在键盘上飞快敲击，重新设定採样条件。
密集的运行记录迅速收缩，最后，屏幕上只剩一列时间间隔越来越长的纸带快照。
第一张快照。
第二张快照。
第三张快照。
当过滤完成时，眾人的目光都被吸引了过去。
每一次快照里，纸带上都不再是杂乱无章的黑白像素，而是呈现出诡异的规律性。
长短不一的连续1的区块，中间被单个的0精確隔开。
隨著机器模擬轮次的不断运行，有些连续的1段在增长，有些在缩短，还有一些被无情地向右侧推开。
“单看这些长度，依然是杂乱的数值。”江临走到白板前，拿起一支黑色的白板笔，“但如果你们仔细看变化发生的位置，就会发现它隱藏著清楚的顺序。”
说著，他提笔在白板上写下一段最基础的纸带符號表示。
【01??01?101?20……1??0】
“它没有在纸带上製造隨机图案。”
江临转身在每一段连续1的上方標出一个整数。
“这些连续段是一张用一进位写出来的整数表。读写头每完成一次长程的往返扫描，看起来修改了成千上万个格子，但在宏观层面，它仅仅只修改了其中一项的数据。下一次完整的扫描，它会去修改相邻的另一项。当某一端发生进位时，它的修改方向就会发生反转。”
周述猛地站直了身体，他瞪大眼睛，目光在那列被筛选出的整数快照上快速移动，大脑在飞速运转。
十几秒钟后，他像触电一般衝到了大屏幕旁，用手指著连续八张快照的变化位置，声音因为激动而微微发颤：“零，一，零，二，零，一，零，三。”
会议桌边，刚才还在敲击键盘的几个研究员，手部的动作瞬间停滯了悬在半空。
“格雷码（grayde）。”周述脱口而出，转头看向江临。
“对。”江临点了点头。
在计算机科学中，格雷码是一种特殊的二进位编码方式。
它最显著的特徵是，相邻两个数之间，永远只有一个二进位位发生改变。这种特性常用於硬体设计中以消除毛刺。
而这台只有五个状態、简陋到极点的图灵机，竟然用它那左右往返、看似愚笨的读写头，以及纸带上一串串长短不一的1，在两百亿步的狂飆突进中，硬生生地把一整套格雷码的更新次序，天衣无缝地藏进了纸带的结构演化里！
过去十几年里，所有研究者的分析都深陷在泥潭中，因为他们都在试图追踪每一格纸带在每一纳秒里究竟发生了什么。
那是一个细节爆炸的微观地狱。
而江临，直接把观察的尺度抬高了整整一个维度。
“一轮长程扫描结束后，具体在这个区间里写过多少个1，已经不再重要了。”
江临的语速不快，但每一个字都像钉子一样敲进眾人的脑海里。
“我们要剥离无关变量。需要保留的只有三类信息：作为符號参数存在的活动段索引iii，当前扫描阶段，以及边界標记的奇偶类。八个宏状態只描述控制阶段、扫描方向与奇偶类的组合，活动段索引和各段长度仍作为证书中的符號参数存在。”
叶寧作为形式化验证的老手，此时已经完全明白过来他到底想做什么。
“但是这个列表的长度是会无限增长的啊！”叶寧指著屏幕边缘，眼中闪烁著兴奋的光芒，“如果只记录活动段的位置和奇偶性，能覆盖未来所有新生成的连续段吗”
“能。”江临毫不犹豫地回答，“因为每个新段的產生，都必然通过同一个固定的进位模板。”
说完，他在白板的右侧，刷刷刷地写出了三类局部重写规则的大纲。
1、普通翻转。
2、向右进位。
3、抵达边界后的反向扫描。
“列表可以向右无限延伸，宇宙毁灭它也不会停。但生成这无尽列表的规则，只有这三种。”
江临转过身，直视著所有人。
“所以，我们的非停机见证不需要装下整张纸带的快照，那是內存装不下的。我们只需要在数学上证明：所有合法的列表状態，在经过一次这样的宏转换之后，仍然属於我们定义的同一个集合。只要这个集合是闭合的，机器就永远逃不出去。”
“那停机条件呢”乔闻鐸从桌边霍然站起，快步走到屏幕前。
长年做学问的稳重此刻也被打破了。
江临走过去，手指直接点在转移表最后那个显眼的未定义入口上。
“这台机器要撞进停机状態，条件极为苛刻。它必须同时满足三个前提：第一，它必须在回收阶段抵达当前编码区的右端分隔符；第二，以指定状態读取空白符；第三，让边界標记落在偶类。”
“只有这三个条件同时成立，那个未定义转移才会被触发。”
江临转身，沿著刚才写出的宏转换逻辑，一层层向下推导。
笔在白板上划出一道道严密的逻辑链条。
“根据刚刚拆出的三类宏转换，活动段每向右推进一次，边界奇偶位都会隨对应的进位模板翻转。这个结论来自机器自身的局部重写关係，而非格雷码的一般性质。”
“因此，我们可以得出结论：当机器抵达当前编码区的右端分隔符形成宏状態时，它的奇偶標记永远落在奇类，也就是非停机类。而如果奇偶標记碰巧符合了停机要求的偶类时，对不起，此时活动段与边界之间，至少还隔著一个不可逾越的分隔符，它根本触碰不到边界。”
“那个未定义的停机入口確实就在那里，敞开著大门。”
江临看著眾人，语气平静得让人不由得冒起鸡皮疙瘩。
“却不属於任何一个从初始配置可达的宏状態。”
乔闻鐸稍一思索，拿起桌上的另一支红色白板笔，走到江临身边。
在江临列出的宏状態旁，画了一个圈，加上了一个退化情况。
他敏锐地察觉到了这个宏大架构中的一个风险点。
“你的理论很精妙。但如果中间这一段连续的1缩减到零呢两个0分隔符直接合併，活动位置会发生跳跃，直接跨过一层，方向標记也会在跨层合併的同时发生翻转。”
江临微微一笑，仿佛早就预料到了这个问题。
他接过红笔，在归併规则的下方补上了一行严密的代数推导。
“跨层发生以后，虽然发生了一次额外的翻转，但由於位置的跳跃补偿了相位的损失，新的边界奇偶类经过计算，仍然与停机类保持相反。它依然落入我们的不变量集合中。”
周述紧接著举起手，指出了系统实现层面的第二个问题。
“逻辑上成立了，但是核验器怎么识別如果两个分隔符合併成连续的00，读写头停在其中任意一格时，左右两种编码都可能成立。核验器在匹配规则时会產生歧义，怎么避免把两个不同的宏状態识別成同一个”
“很简单。把读写头停留在分隔符上的朝向，强制写进状態定义里。”江临在白板上画了一个带有箭头的方块，“我们不做对称归併，破除歧义。”
原本白板上的六个宏状態，因为这一调整变成了八个。
叶寧没有废话，直接从伺服器里调出了之前运行的最长轨跡，从中抽取出所有发生过边界归併的极端样本。
她把这些数据打包，逐条投入到江临刚刚定义的新的宏状態逻辑中进行跑批测试。
三十七次严重的边界归併。
全部安全著陆，无一遗漏地落在江临刚写出的那两条边界路径里。
当然那，这三十七条轨跡能证明新抽象与已知数据一致，还是无法替代对全部符號参数的闭包证明。
会议室里原本同时打开的几个键盘，打字声逐渐停了下来。
所有人都停下了手头的工作，目瞪口呆地看著白板上的推导。
乔闻鐸重新看向白板。
“歷史样本过了，现在，怎么把无限个参数情形交给核验器”
他此时问出的第三个问题，已经不再是怀疑这个不变量是否成立，而是已经直接跨越到了工程实施的层面。
江临在八类宏控制状態的外围，画了一个大大的方框，將其整体圈住。
“在系统中，单独建立第四类非停机见证类型——宏状態不变量见证。”
“底层的公共可信核呢”第三方负责人立刻追问，因为这关係到整个验证架构的公信力。
“公共核保持冻结，绝对不能修改。”
江临说完在方框外写下三条冷硬的检查条件。
【条件一：验证初始配置是否安全进入宏状態集合。】
【条件二：穷举所有的局部重写规则，验证其是否能保持集合闭合。】
【条件三：验证宏状態集合是否与停机入口彻底互斥。】
“具体的工程方案是这样的：新的见证文件只负责提交宏状態的定义、符號块的划分以及局部重写的模板。公共核继续负责验证图灵机的一步转移语义和有限基例；新的宏状態核验器负责检查参数化重写模板的归纳条件、集合闭包与停机排除。两层之间只通过冻结后的机器语义接口连接。”
江临看著周述和第三方负责人，侃侃而谈。
“rt组和ocal组，分別独立实现针对这八类宏控制状態的核验器扩展模块。第三方，你们的责任是，想尽一切办法生成能击穿这八个状態边界的变异样例。”
“两组开发人员能看到你的白板推导吗”乔闻鐸问。
“只给抽象的规范文档和序列化后的证书格式。隔离必须彻底。”江临平静地说。
乔闻鐸抬起腕錶看了一眼时间。
晚上七点二十六分。
从江临下令关掉单步动画，到他在白板上徒手写出完整的足以镇压skelet#17的核验边界，用了一个小时十九分钟。
乔闻鐸转过身，目光如炬，扫过周述和第三方负责人。
“都听清楚了开启新的规则编號，两套实现团队继续保持绝对隔离，切断一切私下通讯。今晚九点前封存规范文档，明天一早，开始盲测。”
周述深吸了一口气，合上桌面那叠曾经耗费了他们无数心血，此时已经失效的分析报告。
他转过头，又看了一眼大屏幕右上角那个红色的数字1。
“这一次总该轮到它归零了吧。”周述喃喃自语，手心全是汗。