未名殘章/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 的情況。