你 16 歲時夢想做什麼？我想開車環遊世界。但美國數學家雷·索洛莫諾夫在那個年紀有更遠大的目標。他想找到一種方法來解決所有可以想見的科學問題。
這不僅僅是異想天開，這位少年有一個開創性的想法，將建立一個全新的研究領域。在接下來的幾年裡，索洛莫諾夫提出了一個概念，該概念使系統地搜尋資料中的模式成為可能，從而揭示我們世界背後的隱藏過程。
今天，這可能讓人想起人工智慧的工作方式。但是索洛莫諾夫在 1942 年就提出了他的第一個想法——遠在人工智慧演算法出現之前。索洛莫諾夫的方法基於奧卡姆剃刀原理，根據該原理，對現象最簡單的解釋通常是正確的。（物理學家也採用同樣的邏輯；他們尋求最簡單的公式來儘可能多地描述物理過程。）
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保有關當今塑造我們世界的發現和想法的影響深遠的故事的未來。
索洛莫諾夫正在尋找一套規則或演算法，以揭示資料中的隱藏關係。他希望，透過這種方式，世界上的一切都可以得到簡單的解釋。例如，如果您記錄丟擲的棒球的軌跡，您可以找到任意數量的數學公式（有些非常複雜）來再現軌跡的路線。要從所有這些可能性中推匯出正確的規律，您應該尋找最簡單的描述。答案很可能對應於牛頓運動定律，該定律描述了兩種力的相互作用：人拋球的力和將球拉到地面的重力。
索洛莫諾夫正在尋找一個規則，該規則將選擇所有可能描述中最簡單的描述。這樣的規則可以轉化為計算機程式。任何資料都可以傳遞給這個程式，經過一定的時間後，就可以獲得對這些值起源的最簡單的解釋。這將是一臺名副其實的奇蹟機器。
如何定義“簡單”
首先：索洛莫諾夫的最簡單描述查詢器不存在——而且永遠不會存在。然而，憑藉他的想法，當時 16 歲的他站在了一個全新研究領域的前沿，該領域涉及機會和複雜性的真正本質。正如自然科學中經常發生的那樣，另外兩個人在大約同一時間產生了非常相似的想法。
這些人之一是蘇聯數學家安德烈·柯爾莫哥洛夫，他主要關注機率和隨機數。特別是，他對如何判斷現象的描述是簡單還是複雜感興趣。
假設我向您展示數字 25,041,903。乍一看，它似乎很隨機。有多種方法可以解釋我是如何獲得這個值的。例如，我可能使用了隨機數生成器，並按順序獲得了數字 2、5、0、4、1、9、0 和 3。這似乎不是很令人滿意——它背後沒有任何有助於您記住該值的推理。但我也可以說這個數字等於三個素數 3 x 61 x 136,841 的乘積。或者我可以告訴您，數字序列從 pi 的第 40,122,575 位小數位開始，或者我選擇這個數字是因為柯爾莫哥洛夫出生於 1903 年 4 月 25 日。這些解釋中哪一個聽起來最簡單？不同的人可能會有不同的回答。
柯爾莫哥洛夫成功開發了一種客觀方法來確定物體的複雜性。數字的柯爾莫哥洛夫複雜性對應於計算該數字的最短計算機程式的長度。程式越短，數字越簡單。
因此，柯爾莫哥洛夫複雜性取決於所使用的程式語言。某個程式在 Python 中可能比在 C++ 中更短，反之亦然。每個計算機程式都可以用機器程式碼表示，機器程式碼又由 0 和 1 的序列組成。計算機計算所需結果的最短 0 和 1 序列的長度對應於柯爾莫哥洛夫複雜性。
因此，如果您想確定 25,041,903 的柯爾莫哥洛夫複雜性，您可以將各種解釋（它是數字列舉或素數分解的結果、pi 中的位置或柯爾莫哥洛夫生日的日期）轉換為計算機程式，並計算相應機器程式碼中所需的字元。
而我之前的例子可能排除了 25,041,903 的更簡單的解釋。柯爾莫哥洛夫開發了一種系統的方法來識別最短的程式。為此，您給計算機一個數字，例如 25,041,903。然後，計算機逐個執行所有可能的演算法——從最小的開始，用 0 或 1 編碼。計算機這樣做，直到制定的程式產生所需的結果。例如，第一個返回 25,041,903 值的程式是最短的。它的字元長度對應於 25,041,903 的柯爾莫哥洛夫複雜性。
一個討厭的悖論摧毀了夢想
乍一看，索洛莫諾夫的夢想現在似乎已經實現了。藉助柯爾莫哥洛夫複雜性，似乎可以揭示任何資料中的任何模式。
但是一個悖論給工作帶來了麻煩。哲學家伯特蘭·羅素在 1908 年將相關問題歸因於圖書管理員 G. G. 貝里——遠在索洛莫諾夫和柯爾莫哥洛夫發表他們的想法之前。貝里思想實驗的一個例子如下：假設你有一本只有 20 個單詞的字典，你嘗試使用這些單詞來描述不同的數字——非常類似於柯爾莫哥洛夫在計算機程式中的想法。您可以開始使用這 20 個單詞逐步定義數字。組合這 20 個單詞的方式只有有限種，因此您只能描述有限數量的數字。然而，由於數字是無限的，其中一些數字將無法進行這樣的定義；您最終會得到一個無法用 20 個或更少的單詞描述的數字。但是，如果您使用這 20 個單詞中的一些來制定描述“無法用 20 個或更少的單詞描述的最小數字”呢？
這個定義僅包含 12 個單詞，從而產生了矛盾。哪裡出錯了？事實證明，您無法計算定義一個數字需要多少個單詞。乍一看，這似乎是一個廉價的藉口，但事實上，貝里悖論和柯爾莫哥洛夫複雜性與數學最違反直覺的特徵之一有關：有些真理無法證明。或者換句話說：數學是不完備的。
假設真的有一個計算機程式 K 可以計算與每個輸入相關的柯爾莫哥洛夫複雜性。這個程式由一百萬個字元組成。它不必快速或高效；它只需要工作。
現在測試該程式，併為其提供所有可能的輸入，直到您最終找到一個複雜度為 200 萬的大數 x。然後以類似於貝里悖論的方式進行。您編寫一個新的計算機程式 P，該程式執行以下任務：它系統地遍歷所有字串，並使用程式 K 計算字串的柯爾莫哥洛夫複雜性，直到找到一個複雜度為 200 萬的字串。
新程式 P 直接依賴於 K，因此不會包含比 K 多太多的字元。（在任何情況下，它都由少於 200 萬個字元組成。）但這意味著已經找到一個字元少於 200 萬的計算機程式，該程式計算出的數字的複雜性為 200 萬——這是一個矛盾。
如果一個邏輯論證產生矛盾，則至少有一個假設必須是錯誤的。在這種情況下，我們假設存在一個程式 K，該程式計算每個輸入的柯爾莫哥洛夫複雜性。因此，只有一個可能的結論：這樣的 K 不可能存在。不可能找到對於每個可以想象的輸入都生成此輸入的最短程式。
儘管如此，一個圓滿的結局是可能的
因此，16 歲的索洛莫諾夫的夢想沒有實現。但是，即使柯爾莫哥洛夫複雜性無法針對每個輸入進行計算，這個想法在許多應用中仍然證明是有用的。大多數特殊情況不需要精確的柯爾莫哥洛夫複雜性——近似值就足夠了。專家通常使用壓縮程式來實現這一點。在需要柯爾莫哥洛夫複雜性的情況下，“您可以將資料輸入到壓縮程式中，例如使用 gzip 或將影像另存為 .gif 檔案，並將其用作粗略的近似值”，德克薩斯大學奧斯汀分校的計算機科學家斯科特·阿倫森告訴Plus。
例如，如果您想找出兩個數字序列 x 和 y（例如，它們可以對應於測量資料）是否相關，您可以首先分別壓縮 x 和 y，然後將兩個序列附加在一起並壓縮 xy。如果 xy 的壓縮率僅略高於 x 或 y 的單獨壓縮率，那麼數字序列之間一定存在相關性——並且您獲得了隱藏模式的線索。
柯爾莫哥洛夫複雜性也可用於確定特定數字序列的隨機性。例如，三個八位數字 25,041,903、47,395,929 和 10,101,010 可能是由隨機數生成器生成的——即使它們並非都顯得同樣隨機。透過偶然性生成這三個數字中每一個數字的機率是相同的：在 00000000 到 99,999,999 的數字範圍內，您遇到其中一個值的機率為 1/108。但 10,101,010 有明顯的模式，25,041,903 也是如此，它對應於出生日期。透過計算數字的柯爾莫哥洛夫複雜性，可以評估它們是否遵循某種模式——以及隨機數生成器是否可靠地工作。
不幸的是，柯爾莫哥洛夫複雜性沒有回答“生命、宇宙和萬物”的問題。如果我們相信科幻小說作家道格拉斯·亞當斯，那麼這個問題的答案是 42。但奇怪的是，數字 42 並不是特別複雜——可以使用柯爾莫哥洛夫複雜性來計算它。
本文最初發表於《明鏡線上》雜誌，經許可轉載。