資料壓縮問題最簡單的形式可能與數字及其符號有關。 數字可以用數字（“十一” 對於數字 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