資料壓縮問題最簡單的形式可能與數字及其符號有關。 數字可以用數字(“十一” 對於數字 11),數學表達式 (“二十分之一” 1048576),字串表達式(“五個九” 99999),專有名詞(《野獸之數》 對於 666 來說, “圖靈去世的那一年” 1954),或其任意組合。 任何指定都是合適的,對話者可以透過它清楚地確定我們正在談論的數字。 顯然,告訴你的對話者 “八的階乘” 比等效符號更有效 “四萬三百二十”。 這裡出現了一個邏輯問題:給定數字的最短表示法是什麼?
哲學家伯特蘭·羅素於 1908 年發表
這樣的數字一定存在:從 3480 個俄語字母和空格中只能組成 3480 個名稱,這意味著使用 3480 個字母最多可以指定 XNUMX 個數字。 這意味著不可能以這種方式指定不超過XNUMX的某個數字。
這意味著該數字將對應於指定 “八十個字母不夠的最小數字”,只有 78 封信! 一方面,這個數字必須存在;另一方面,這個數字必須存在。 另一方面,如果這個數字存在,那麼它的名稱與之不對應。 悖論!
消除這個悖論的最簡單方法是參考口頭符號的非正式性。 就像,如果符號中只允許一組專門定義的表達式,那麼 “八十個字母不夠的最小數字” 不會是一個有效的符號,而實際上有用的符號,例如 “八的階乘” 仍然可以接受。
是否有正式的方法來描述數字操作的順序(演算法)? 有很多,它們被稱為程式語言。 我們將使用顯示所需數字的程式(例如,Python)來取代口頭符號。 例如,對於五個 XNUMX,該程式適合 print("9"*5)
。 我們將繼續對給定數量的最短程序感興趣。 這樣一個程式的長度稱為
我們現在可以考慮一個類似的悖論,而不是貝裡悖論: 千字節程式不夠輸出的最小數是多少?
我們將按照與之前相同的方式進行推理:有 2561024 KB 文本,這意味著 KB 程式最多只能輸出 2561024 個數字。 這意味著不能透過這種方式導出不大於2561024的某個數字。
但是,讓我們用 Python 編寫一個程序,生成所有可能的千字節文本,運行它們以執行,如果它們輸出一個數字,則將該數字添加到可到達文本的字典中。 檢查完所有 2561024 種可能性後,無論需要多長時間,程式都會尋找字典中缺少的最小數字並列印該數字。 顯然,這樣的程式將適合 XNUMX KB 的程式碼 - 並且將輸出 XNUMX KB 程式無法輸出的數字!
現在有什麼問題嗎? 它不能再歸因於符號的非正式性!
如果您對我們的程式需要大量記憶體才能工作(包含2561024 個元素的字典(或位數組))感到困惑,那麼您可以在沒有它的情況下執行相同的操作:依次針對2561024 個數字中的每個數字,遍歷所有2561024個可能的方案,直到沒有合適的方案。 這樣的搜尋將持續很長時間並不重要:在從號碼和程式中檢查少於(2561024)2對後,它將結束並找到那個非常珍惜的號碼。
還是不會完成? 事實上,在所有將要嘗試的計劃中,將會有 while True: pass
(及其功能類似物) - 事情不會比測試這樣的程序更進一步!
與貝裡悖論不同,貝裡悖論的問題在於符號的非正式性,在第二種情況下,我們有一個精心偽裝的重新表述
來源: www.habr.com