AI Prehistory | Two Legends Who Made Encoding Possible · Part I · GödelAI 前傳｜讓編碼變成可能的兩位傳奇人物 · 上篇 · 哥德爾
“3 > 2 = 2,250; 2 < 3 = 3,240”: Without Ideas This Strange, Today’s AI Would Be Hard to Imagine「3 > 2 = 2,250；2 < 3 = 3,240」：沒有這些讀起來瘋狂的東西，就幾乎沒有今天的 AI
3 > 2 is a statement in arithmetic. The same statement can be written in a different form—as an integer, say 2,250.
3 > 2，在算術裏是一條陳述句。這條陳述句，也可以換種方法，寫成一個整數，例如 2,250。
Preface — Programs can read programs; machines can simulate machines. Today’s AI systems likewise run as programs, while language must first become tokens and vectors before a model can process it. Beneath all of this lies an idea that once looked absurd: encoding.
Preface — 程式可以讀程式、機器可以模擬機器；今日 AI 系統同樣要由程式運行，語言進入模型前，更要先變成 token 與向量。地基都藏在這個看似荒謬的編碼裏。
Reverse the two sides and 2 < 3 becomes another statement, which the same method writes as 3,240. Neither 2,250 nor 3,240 is the result of a calculation. They are codes. Factor the two integers and the original statements—3 > 2 and 2 < 3—can be recovered.
A digital photograph is made of pixels; a sound recording is digitised through successive samples. Such conversions are now easy enough to grasp. What Gödel encoded in 1931 was more abstract: what a mathematical statement says on the page, and which rules a mathematical derivation follows. Symbols, formulae, and even entire proofs could all be encoded as integers.
The crucial move was not merely turning abstractions into numbers. Once statements and rules could be encoded as integers, mathematics could turn back and operate on them.
At twenty-five, Kurt Gödel was not devising a convenient file format. He was redrawing the boundary of what a number could represent. A number need not stand only for three apples, twenty metres, or the answer to a calculation. It could preserve the complete structure of a formula—even an entire chain of reasoning.
01How can “three is greater than two” fit inside 2,250?
Begin with a deliberately simplified example. Suppose we assign a number to each symbol:
3 → 1, > → 2, 2 → 3, < → 4, 5 → 5, + → 6, = → 7, 8 → 8
Then 3 > 2 can first be written as 1, 2, 3. But these are still three separate numbers. Gödel needed every string of symbols to correspond to one unique integer—from which the original string could be recovered in full.
Prime numbers provide exactly such a method. They preserve the order of the symbols without scrambling it during factorisation. Take 2, 3, 5, 7 … in sequence, and place each symbol code in an exponent:
2¹ × 3² × 5³ = 2,250
In this simplified example, 2,250 represents 3 > 2. Factor 2,250 into primes and the exponents return 1, 2, 3; consult the codebook and the statement reappears.
把兩邊掉轉，2 < 3 是另一條陳述句；用同一種方法，可以寫成 3,240。2,250 和 3,240 都不是兩條陳述句的計算結果，而是它們的編碼。把這兩個數字拆解，便能分別還原成 3 > 2 和 2 < 3。
一張數碼相片由像素組成，或一段聲音透過連續取樣換成數碼記錄；這種數字轉換，今天已經不難理解。哥德爾在 1931 年處理的對象卻更抽象：他用數字編碼的，是一條數學陳述寫了甚麼，以及一段數學推導根據哪些規則進行。符號、公式，以至整段證明，都可以編碼成整數。
關鍵不只是把抽象概念變成數字。當陳述與規則能以巧妙的方法編碼成整數，它們也就成為數學可以反過來處理的對象。
25 歲的庫爾特・哥德爾（Kurt Gödel）做的不是設計一種方便存檔的格式，而是重新劃定「數字可以代表甚麼」：數字不再只表示三隻蘋果、二十米距離或一道算式的答案，也可以代表一條公式的完整結構，甚至一整個推理過程。
01一句「三大於二」，怎樣裝進 2,250？
先用一個極度簡化的例子。假設我們替每個符號分配一個編號：
3 → 1，> → 2，2 → 3，< → 4，5 → 5，+ → 6，= → 7，8 → 8
那麼，3 > 2 可以先寫成 1, 2, 3。不過這仍然是三個分開的數字。哥德爾需要的，是讓每一串符號都對應一個獨一無二的整數，而且可以由那個整數完整還原原句。
質數剛好提供了一種方法，可以完整保留符號的順序，不會在拆解時打亂。我們依次取 2、3、5、7⋯⋯，再把符號編號放進指數：
2¹ × 3² × 5³ = 2,250
在這個簡化例子裏，2,250 代表的就是 3 > 2。把 2,250 分解成質因數，指數會重新給出 1, 2, 3；再對照符號表，便能還原出原句。
Actual Gödel numbering is far more complete. It must handle variables, brackets, symbols meaning “for all” or “there exists” (quantifiers), sequences of formulae, and entire proofs. The resulting integers also become absurdly large.
Their size does not matter. Gödel’s task was not to sit down and calculate every encoded result. What mattered was proving that the scheme could do three things.
01 · UNIQUENo collisionsDifferent symbol sequences never receive the same number. Even with the same symbols, a change of order changes the code.
02 · REVERSIBLEReversiblePrime factorisation recovers every original symbol and its position.
03 · MECHANICALMechanicalEncoding and decoding follow fixed steps. No interpretation of the sentence is required.
Why does the encoding still work with a different codebook?
A formula has no single, preordained Gödel number. You may code 3 as 1 or as 7. The integer will change, but the encoding remains valid so long as the mapping is explicit, unique, and mechanically reversible.
The interactive tool above lets you switch codebooks. 3 > 2 will no longer become 2,250, yet the new integer still decodes precisely. What matters is the structure of the encoding, not any particular number.
02When mathematical statements become mathematical objects
A formula is, at one level, simply an ordered string of symbols, and can therefore be encoded as an integer. A proof is an ordered sequence of formulae, so it can be encoded as another integer in turn.
真正的 Gödel numbering 比這個例子完整得多，要處理變數、括號、代表「所有」或「存在」的符號（量詞）、公式之間的序列，甚至一整份證明。編碼所得出的數字也會大得荒謬。
但數字有多大並不重要，反正哥德爾的工作不是坐下來把每個編碼結果都計算出來；他需要證明的是，這種編碼可以做到三件事。
01 · UNIQUE不會撞碼不同符號序列不會得到同一個數字。即使符號一樣，順序一改，編碼亦會改變。
02 · REVERSIBLE可以還原數字經過質因數分解，可以找回原來內容的所有符號，以及它們各自的位置。
03 · MECHANICAL毋須釋義編碼與解碼都有固定步驟，毋須先解釋句子的意思，也能依照步驟完成。
為甚麼換一套符號編號，編碼仍然有效？
一條公式沒有唯一、天定的 Gödel number。你可以把 3 編成 1，也可以編成 7；所得的整數會不同，但只要對應關係清楚、獨一，而且可以按照固定步驟還原，編碼便同樣有效。
上面的互動器可以切換符號表。你會看見 3 > 2 不再編碼成 2,250，但仍然可以由新的整數準確還原。重要的是編碼結構，不是某一個特定號碼。
02當數學語句也成為數學對象
一條公式其實不過是一串有序符號，所以可以編碼成一個整數。證明則是一串有序公式，所以也可以編碼成另一個整數。
With these successive layers of encoding, questions about mathematical formulae and proofs can be reframed as relationships among integers:
| Formula(n) | Does the integer n decode to a well-formed formula? |
| Step(a,b) | Does the move from the formula represented by a to the formula represented by b follow a valid rule of inference? |
| Proof(p,s) | Does the symbol sequence represented by p form a valid proof of proposition s? |
This does not mean that mathematics simply replaces language, still less that a machine suddenly understands what a sentence means. Encoding mathematical language makes a proof checker possible: a program that reads the integers representing formulae or proofs, then applies fixed rules to check their form and every step of the derivation.
Without such an encoding, one confronts line after line of symbols on paper. For a mechanical procedure to verify a proof, its formulae, inferential steps, and rules must first become input that the procedure can read and inspect one item at a time.
The checker no longer works only on marks written on paper; it operates on integers representing those long strings of symbols. Once syntax has been “arithmetised”, statements and proofs themselves become objects that mathematics can study.
Can a mathematical statement refer to itself through encoding?
Begin with a direct example:
有了這一層層的編碼，原本關於數學公式與數學證明的問題，也能換個角度，簡化成處理整數之間的關係：
| Formula(n) | 數字 n 解碼後，是不是一條格式合法的公式？ |
| Step(a,b) | 由 a 所代表的公式推演到 b 所代表的公式，是否符合其中一條合法的推理規則？ |
| Proof(p,s) | 數字 p 所代表的整段符號序列，是否構成命題 s 的合法證明？ |
這不代表數學直接取代了語言，更不代表機器忽然理解了句子的意思。把數學語言編碼後，真正變得可能的，是建立一個檢查證明的程式，也就是 proof checker：它可以讀取代表公式或證明的整數編碼，再按照固定規則檢查公式的格式，以及每一步推導是否合法。
沒有這種編碼以前，我們只能直接面對紙上一行又一行的符號。若要讓另一套機械程序驗證一項證明，第一步便是把公式、推導步驟和規則，轉換成程序可以讀取及逐項檢查的輸入。
關鍵在於，這個 checker 不再只是直接處理紙上的符號，而是處理代表那一大串符號的整數。語法被「算術化」（arithmetisation）之後，陳述句和證明本身，也成為數學可以研究的對象。
數學陳述可以透過編碼指向自己嗎？
先看一個最直接的例子：
Natural language can use “this sentence” to point directly to itself, and readers barely hesitate. Formal mathematics cannot simply write “this statement” and assume that the system knows which one is meant. The object must be specified mathematically and exactly.
Gödel numbering first assigns integers to the symbols, formulae, and mathematical statements in a formal system. One can then construct a statement about “the mathematical statement with code n”, and substitute that very statement’s own code for n. The method by which a statement ultimately points to its own encoding is called diagonalisation.
Encoding alone is not yet self-reference, but it opens the door. Before encoding, “a mathematical statement” and “an integer” belong to different levels. With encoding, a statement can point indirectly, through integers, to other statements—and even to itself. We will stop at the threshold here, and enter the magic of self-reference together in the later article on Gödel, Escher, Bach.
Gödel made it possible for mathematics to operate not only on quantities, but on descriptions of mathematics itself. The next step shifts the question from “How can a statement be encoded?” to “How can an executable procedure be described exactly?”Part II: how Turing turned machine instructions into input, opening a path towards the universal machine, programming, and AI.
Part II: Turing and the machine that could read instructions →
Sources and further reading
- Stanford Encyclopedia of Philosophy, “Gödel Numbering”.
- Kurt Gödel, On Undecidable Propositions of Formal Mathematical Systems, notes from the 1934 Princeton lectures.
- Image: Young Kurt Gödel. Licensing and provenance appear on the file page.
自然語言可以用「這句話」直接指向自己，我們讀起來也不覺得困難。形式數學卻不能只寫「這條陳述」，然後假定系統知道所指的是哪一條；這個對象必須由數學精確指定。
Gödel numbering 先替形式系統內的符號、公式和數學陳述編配整數。接着，可以構造一條談論「編碼為 n 的數學陳述」的陳述，再把這條陳述自己的編碼代入 n 的位置。這套讓陳述最終指向自身編碼的方法，稱為「對角化」。
編碼本身還不是自我指涉，但通往魔法的大門已經打開了。未經編碼時，「一條數學陳述」和「一個整數」分屬兩個層次；有了編碼，數學陳述便有可能透過整數間接指向其他陳述，甚至指向自己。今次只停在這道門前；自我指涉的魔法，留待之後的 GEB 文章再和大家一起走進去。
哥德爾讓數學不只處理數量，也能處理對數學本身的描述。下一步，問題由「如何編碼一條陳述」推進成「如何準確描述一套可以執行的程序」。下篇：圖靈如何把機器指令變成輸入，並由此打開通用機器、程式與 AI 的道路。
資料與延伸閱讀
- Stanford Encyclopedia of Philosophy, 〈Gödel Numbering〉。
- Kurt Gödel, 〈On Undecidable Propositions of Formal Mathematical Systems〉，1934 年 Princeton lectures 筆記。
- 圖片：Young Kurt Gödel。授權及來源資料見檔案頁。
Enjoyed this?喜歡這篇？
Get new writing from the lab in your inbox, plus the occasional invite to a class. Free and paid tiers — read at your own depth.訂閱以收到實驗室的新文章，以及不時的課堂邀請。設有免費與付費方案——依你想要的深度閱讀。
Subscribe — free & paid訂閱——免費與付費