Reference-Request

圖靈的(還是?)分類推理引擎算法?

  • April 11, 2018

有誰知道圖靈的 Colossus推理引擎使用的算法,高度機密以至於英國人在二戰後將其保密了幾十年?

事實上,它可能仍然是分類的。幾年前,我的一位同事,已故的羅伯特·約翰遜,給我發了一封電子郵件,回應了我關於人類知識無損壓縮 Hutter 獎的聲明。Bob 是設計 Burroughs 零地址架構的人,該架構在銀行業中使用了這麼多年(順便還發明了用於支票的磁性墨水)。他當然有很多他沒有宣傳的背景,包括機密工作。

Computerdom 在推理引擎(做出預測)方面沒有很多藝術。我所知道的最有效的推理引擎是為 Colossus 製作的軟體,這是圖靈在二戰中的密碼破解“電腦”。即使硬體已經解密多年,英國人仍然將該軟體視為機密。據我所知,英國以外沒有人知道該軟體的詳細資訊。我的觀點是,從自然語言中獲得理解是一種相對較小的藝術,主要由密碼分析家實踐。我進一步的觀點是,感興趣的自然語言(無論是英語、漢語、瑪雅語還是……)對一個人(人或程序)如何進行分析和推理具有重大影響。從實踐的角度來看,如果我能用中文完成,至少對我來說,Hutter 挑戰會更容易處理。我的第一個博士生是顧俊,他目前是中國首席資訊科學家。他的論文是關於高效壓縮技術的。如果您願意,您可以與任何您喜歡的人分享這些想法。

Bob Johnson 名譽教授電腦科學大學。猶他州

這並不能回答您的問題,但您可能會在艾倫·圖靈 (Alan Turing) 的兩篇戰時論文中找到線索,這些論文以前是機密的,已於 2015 年解密並發表在英國國家檔案館,現在可在 arXiv 上找到:

Alan M. Turing,“機率在密碼學中的應用”,英國國家檔案館 HW 25/37,1942,arXiv:1505.04714

Alan M. Turing,“重複統計論文”,英國國家檔案館 HW 25/38,1942,arXiv:1505.04715

根據其中列舉的原則,有可能重建圖靈在 Colossus 中實施的算法執行已知能夠執行的壯舉。

我的業餘理解,從我狂熱閱讀的所有內容中滲透出來,是艾倫圖靈獨立發現並將貝氏定理應用於破解 M4 Enigma。貝氏定理可以描述為“推理”。

圖靈沒有直接參與攻擊魚或建造巨像,但他的機率方法被紐曼裡採用。Colossus 是一個機電計數器,但早期的攻擊是手動的。

2007 年,新重建的 Colossus Mk 2 在 Bletchley Park 投入使用時,一條金槍魚在德國傳輸,在英國攔截並被 Colossus 成功解碼。今天已經理解了足夠的程式來實際使用 Colossus 來破譯魚。令人興奮:)

在戰時和直到現在,貝氏在學術界都非常失寵。然而,在西方密碼學界的秘密下,它被熱烈地接受了。

Colossus 的“軟體”是一個外掛板。我覺得有趣的是,可能有一些方法可以插入巨像以做出現在尚未重新發現的推論!想像一下應用貝氏的捷徑可能尚未公開發現,這是令人興奮的。如果是這樣,這些將對貝氏的非常實際的應用產生巨大的影響,貝氏正在隨著自動駕駛汽車和所有其他汽車的普及……

引用自:https://crypto.stackexchange.com/questions/34682