未名残章/Samlye~3

From Project Archive by Lakejason0

计算科学·深度档案馆[edit | edit source]

你是否很享受 SCP 收容系列和 Backrooms 系列这样的都市怪谈?计算科学·深度档案馆就是一个类似的机构,我们也会保管一些听上去奇奇怪怪的东西,不过都与计算科学相关。如果感觉我们的归档摘要晦涩难懂,也是很正常的事情。

对了。我们的档案不是怪谈

Oracle[edit | edit source]

Oracle 的外表像一个木头手提箱,表面看起来像是喷过漆,但是目前没有发现方法对 Oracle 产生任何划痕。Oracle 的把手变成了一个可以塞入纸条的缝。在这个「把手」缝的相对面,有一个更长的缝,称为「箱底」缝。

Oracle 的侧表面刻有使用说明。若需使用 Oracle,用户需要在「把手」塞入 9.28cm 宽的纸带,纸带上只能以涂黑或不涂黑的方法,按 9.28cm 每格的方式填涂,它们分别表示 0 和 1。同时,「箱底」缝接受 13cm 宽的纸带,纸带上按 1.86cm 每格的大小,按使用说明中的编码来描述状态转移方式。两处缝所接受的纸带长度不限,曾有测试项目将 3000m 长的纸带输入 Oracle,并未发生因塞满而导致无法继续塞入的情况。

Oracle 会将两张纸带视为图灵机模型,其中「把手」纸带是图灵机模型中的正常纸带,以塞入端为 0 号。「箱底」纸带是图灵机的机器描述。磁头最初会置于 0 号。尽管纸带输入是有端点的(即从纸带格子从 0 号开始增加,没有负数号码),但是 Oracle 内部会按双端无穷长纸带进行处理。

当两处都塞入纸带,Oracle 会在「把手」纸带格数乘以 35 纳秒的时间之后,从「把手」缝吐出边长为 5.337cm 的正方形纸片。纸片若涂黑代表图灵机停机,若未涂黑代表图灵机不停机。

计算科学深度档案馆曾委托美国计算机学会成立专门委员会对 Oracle 进行讨论。由于无法了解 Oracle 如何解决了停机问题,委员会最后决定将 Oracle 的存在定为绝密级。

为了掩盖 Oracle 存在的事实,委员会另外设计了一个「Oracle」:这个虚构的 Oracle 能在多项式时间内判定 NP 问题,并以这个 Oracle 作为计算理论学科的习题。因此,任何试图在网络上搜索 Oracle 的人最后都会搜索到这个虚构的 Oracle,没有人会了解到真实 Oracle 的情况。