一種討論「邏輯簡單」的框架

02-19

題圖：Edge InPrivate 瀏覽 Wikipedia 英文的 Kolmogorov complexity 詞條的截圖，截圖時已經啟動放大鏡並使用反色效果。

本文重新整理後已發表在我的個人博客上。

本文旨在表達作者認為一種可以用來定義「邏輯簡單」的方法。

任何上過小學數學的人都應該見過「找規律填數」這類問題。一方面，通常人確實會認為數列「1、2、3、？、5、6」中空缺項（問號）應該是 4；另一方面，任何知道 Lagrange 插值多項式的人都知道這個問號處填任何數都是可以被解釋的；甚至，就我個人來說，我更喜歡用分段函數解釋。

此外，近來我在瀏覽知乎的時候有看到大家探討「是漢語的動詞變化邏輯簡單還是英語動詞變化邏輯簡單」這類問題。譬如「V 過」「V 了」「V 過了」與 V-ed/to have V-ed 等的對應。有人認為漢語的動詞變化比較簡單（語氣、語態、時、體等體現在外部且規律性很強），對應地，英語的動詞形態變化比較複雜（過去式、過去分詞）。

之前在考慮如何好地定義找規律填數類問題答案的時候有過本文將要介紹的思路，現在把它整理下來。

閱讀以下內容需要有基本的計算理論知識，至少知道什麼是語言、什麼是圖靈機。不熟悉該概念的讀者可以簡單地把語言和包含一些字元串的集合等同起來，把圖靈機和圖靈完全語言的程序等同起來，這種對應關係下文章的解讀將會標註在括弧裡面。

計算理論里的經典考慮——字元串的 Kolmogorov 複雜度

選定一個 Turing 可計算的 Turing 機編碼（也就是，把程序和源代碼對應起來） $r:mathrm{TM} oSigma^ast$ ，這就是說，存在著圖靈機 $U$ ，當輸入像 $r(M)$ 時， $U$ 可以模擬 $M$ （ $U$ 可以理解為語言的解釋器）。

考慮串 $s$ ，如果圖靈機 $M$ 在輸入 $t$ 時停機並輸出 $s$ ，我們說 $s$ 可以被 $({M,t})$ 表示（或後者是前者的一個表示），稱 $|r(M)|+|t|$ 為這個表示的長度。對於一個串 $s$ ，它的所有表示中長度最小者叫做它的最小表示，最小表示的長度叫做它的 Kolmogorov 複雜度，定義 Kolmogorov 複雜度除以長度為壓縮率。

兩個簡單的例子：

一個壓縮率很低的串：（連續 $n$ 個 $1$ 的串的壓縮率是 $mathcal{O}left(frac{log n}{n} ight)$ ）

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

一個 Kolmogorov 複雜度很高的串：

bJc.5Ha~@mtynS7(tTB5#_7!6;m<4ut~QsQT;XE6guA/P+dNc(5H256%F4?w&yS[{FB$9jg3:Y;)24^8]GBf]E&7qXu93x5Mr43+

熟知幾個結論：

串的 Kolmogorov 複雜度不超過它的長度加上一個常數（該常數和選定的 $r$ 有關係）；
對於每個長度的串，存在著壓縮率不小於 $1$ 的串；
大多數串的壓縮率都很大（接近 $1$ ，很難壓縮）；
判斷輸入串的壓縮率是否不小於 $1$ ，是 Turing 不可計算的。

找規律填數

下面我給出一種令我信服的、找規律填數類問題答案的定義。希望也能讓你信服。

在考題之前，我們要先規定 $r$ （規定一種程序語言），設有一個給定 $a_1,dots,a_{n-1},a_{n+1},dots,a_m$ 填 $a_n$ 的題目 $P$ 。考慮圖靈機 $M$ ，使得 $M(k)=a_kquad({k=1,dots,n-1,n+1,dots,m})$ 成立，且 $M(n)$ 停機，則說 $M$ 是 $P$ 的一個解， $|r(M)|$ 叫做這個解的邏輯複雜度。

考慮 $P$ 的邏輯複雜度最低的解 $M^star$ （如果同樣長度的有多個，可以用 $r(M)$ 的字典序決定誰更優先），則應該認為這裡規律就是指 $M^star$ ，以 $a_n=M^star(n)$ 作為標準答案。

一句話解釋：選定一個固定的程序設計語言；兩段代碼相比，更短的更優先，同樣長的代碼字典序更小的更優先；給定數列的某些項和一些待填寫的下標，如果某個程序在這些下標都能運行完畢，並且運行結果和已經給出的項是一致的，則認為是解；最優先的解代表了「規律」，因此最優先的解在待填寫下標上的輸出就是應該填寫的答案。

例子：考慮「1、2、3、？、5、6」，使用的語言約定是 JavaScript ES5 的表達式，該表達式必須是一個方法表達式，且返回的方法就作為程序使用，長度相同時，Unicode 字典序更小者認為更優先。那麼該問題的一個解可以是：

function (n) { if (n != 4) return n; return 16384;}

該問題的最優解是：

function($){return $}

因此此題標準答案是 4。

類似地，可以定義需要填多項的題目如何定義標準答案。

關於這個定義的幾個結論是：

對於所有給出有限項，要填有限個缺失項的題目，在該定義下都有解；
如果給定無限項，要填一個缺失項，則該定義不一定有解，考慮任意一個不可計算數列，抽去一項，那麼這樣的題目是不存在解的；
該定義下的最優解是 Turing 不可計算的（可以用 Kolmogorov 複雜度來歸約）；
考慮找規律（不填數）問題，這個問題裡面只要尋找最小機器 $M$ 符合給定的數列規律，設有一個（無窮長的）可計算數列 $a_1,dots,a_n,dots$ 的最優解是 $M$ ，則存在 $N$ ，使得對任意 $m>N$ ，問題 $a_1,dots,a_m$ 的最優解是 $M$ 。

其中第一條和第三條告訴我們了該定義的辨證矛盾（pia 飛）：該定義對於實際問題是良好的，但是是不可計算的。這正好說明了能夠解決複雜的找規律問題的人具有超乎尋常的計算能力。注意：對於任意一個具體的（有限大小的）找規律問題，它的解都是可計算的，但是不存在計算任意規模問題的演算法，因此也不要因為自己的找規律問題做得很好而沾沾自喜。

第四條是後來加上的，它的含義是：對於一個可計算數列，存在一個項數的界，使得給出該界以內的所有項，就不存在比能夠完整生成該可計算數列的最小機器在邏輯上更簡單（更小）的機器了。

譬如評論中提問 2、3、5、7、？、13、17、19 的問題，如果考慮上述模型，或許寫一個分段函數（分 8 段）比寫一個求第 $n$ 個質數的程序短，從而該問題答案不一定是 11；但是，如果題目堅持這個數列的規律是「第 $n$ 個質數」，那麼可以通過給出更多的項，例如給出 2、3、5、7、？、13、17、19、23、……、某個超級大的質數，這樣就可以鎖定答案必須是 11。

此外，在剛剛的「1、2、3、？、5、6」裡面，如果我們把問題改成「1、？」，那麼最優解將變成：（被填寫的數將不是 2 而是 1）

function(){return 1}

這裡這個 $N$ （給出至少多少項可以鎖定最簡單的邏輯到那個可計算數列，也就是例子中「某個超級大的質數」是第幾個質數）可以非常非常大，存在性的證明是平凡的：考慮比 $M$ 小（優先）的所有機器，它們都不是該可計算數列的解，因此它們計算的數列某一項和該數列不同（要麼這一項上它不停機，要麼它算出的結果不同），設這些機器第一次和該數列不同的諸個下標的最大值是 $N$ ，則這個 $N$ 恰好就是可以選擇的最小的 $N$ 。細心的讀者一定已經發現，該 $N$ 一定是 Turing 不可計算的。

可以證明，在上述模型（JavaScript ES5）下，對於可計算數列 $a_n=n$ ，只要給出前兩項即可「鎖定」它的邏輯。

語言的邏輯性

讀者已經可以仿照上述過程比較兩個語言的邏輯性。

給出一個 sketch：首先假定語義可以被（用 Turing 可計算的映射）編碼，然後選定一個 $r$ ，定義圖靈機 $M$ 是自然語言 $L$ 的機器，當且僅當 $M$ 輸入任意語義的編碼的時候，都停機，且輸出一句語法正確、語義同輸入的被編碼語義、用法符合母語使用者用法的句子。定義一個自然語言的邏輯複雜度為它的所有機器中 $|r(M)|$ 最小者的 $|r(M)|$ 。

對於兩個自然語言，邏輯複雜度較小者，邏輯更簡單，更「符合邏輯」。

轉載

在未經書面授權的情況下，您不可以用除了複製本文章地址的方法轉載該文章。注意：您不能複製本文章的內容，也不能複製部分內容作為摘要，您只能通過 URL 鏈接到該文章。您可以複製文章的內容供個人觀看，但將其貼在公眾可瀏覽位置並不算是個人觀看，即使該位置只有您自己觀看。當轉載到的位置上的軟體提供 URL 預覽功能的時候，您應該嘗試關閉該功能。