当前位置:91小说网>都市小说>这个学霸疑似巨额知识来源不明> 第165章 让世界排队(6/10)
阅读设置(推荐配合 快捷键[F11] 进入全屏沉浸式阅读)

设置X

第165章 让世界排队(6/10)

请确认退回、补充材料或进入本人固定处理窗口。】

江临先建立归档目录。

【2022_09_External_problems】

随后逐项。

第一项,busy beaver 5。

在计算机科学的版图里,busy beaver 5是一个诞生于上世纪六十年代的古老谜题。

它的前世,源于数学家们一个纯粹的疑问。

如果只允许一段程序拥有极少的内部状态,它在进入停机状态以前,究竟能表现出多么复杂的行为?

为了寻找答案,他们把目光投向了现代计算机的理论始祖——图灵机。

试图在不同状态数量的限制下,寻找那些运行步数最多最忙碌的冠军机器。

寻找一到四状态冠军的任务,已经在过去几十年间先后被确定并完成验证。

然而,当状态数来到五,机器数量急剧膨胀;更困难的是,一台机器运行再久,也不能自动证明它永远不会停。

这就是它的今生:bb(5)已经不再是一道纸笔算术题,而演变成了一场需要依靠全球算力协作、启发式算法与形式化验证工具共同推进的大型工程。

它的底层规则,其实异常简洁。

五状态,二符号,空白纸带。

如果把那些抽象定义全部拿掉,它很像一场专门为机械打工人设计的极限比赛。

参赛者是一只脑容量很小的机器人。

它面前铺着一条向左右无限延伸的方格纸带,每个格子里只能是0或者1。

机器人每走一步,都要低头看一眼当前格子,再按照预先写好的《工作守则》完成三件事。

把脚下的数字改成0或1。

向左或者向右移动一格。

把自己切换到下一种工作状态。

五状态,意味着它工作时只有A、b、c、d、E五种内部状态。

守则还允许它在某些情况下进入一个额外的停止状态。

一旦进入,整台机器便彻底停下。

故事里讨论的是繁忙海狸的步数版本。

比赛目标很简单:在所有最终能够停下的五状态机器人里,找出工作步数最多的那一只。

提前停下,成绩不够高。

永远不停,也没有成绩。

真正麻烦的是,人们经常无法分清某台机器究竟属于哪一种。

如果它运行一百步后停下,只需把这一百步完整重放一遍,结果便能得到验证。

可如果它已经运行一万亿步,仍在纸带上来回移动,人们只能确认它前一万亿步没有停。

它可能会在下一步进入停止状态,也可能早已掉进一个极其隐蔽的循环,将同一套工作永远重复下去。

继续等待解决不了这个问题。

纸带没有尽头,时间也没有预设上限。

对任意程序,都不存在一种万能工具,可以提前判断它最终会不会停止。

这就是停机问题划出的边界。

五状态机器的种类毕竟有限,人们仍然可以换一条更艰难的路:针对不同机器的行为特征,分别寻找能够证明它永不停机的证据,再把这些机器一批批排除。

清华计算机系发来的三类decider,承担的正是这种工作。

第一种,cycler。

它寻找的是原地打转的机器。
本章未完,请翻下一页继续阅读.........