AI 前傳｜讓編碼變成可能的兩位傳奇人物 · 下篇 · 圖靈

答案不只改變了數學家理解「計算」的方式，也奠定了 programming 的基礎。同一部機器之所以能完成無數不同工作，關鍵正是指令不再焊死在機器裏，而可以被表示、儲存、讀取和執行。

Preface — 上篇由哥德爾開始，看數學陳述與證明如何變成整數。今篇把問題再推前一步：一套程序能否同樣被準確描述，成為機器可以讀取與執行的輸入？這一步，通往通用機器、程式，也通往今日 AI。

03當「描述」開始變成可處理的輸入

哥德爾編碼的是數學符號、公式和證明；程式則是一組可以執行的指令。兩者不是同一回事，但哥德爾展示了一個後來極其重要的可能：只要一套符號與規則能被精確編碼，另一套程序便可以讀取、檢查和處理它們。

如果借用今天的軟件語言，公式和證明可以視為 data；proof checker 才是 program；推理規則是 checker 依循的邏輯；輸出則是「合法／不合法」，以及錯誤出現在哪一步。若另一套程式主動搜尋證明，找到的證明才比較像 output。

可是，proof checker 仍然只會執行事先寫好的規則。由這裏再推前一步，問題變得更加有意思：究竟哪些工作可以拆成一套固定程序，交由人或機器逐步完成？二十世紀三十年代，Herbrand、Gödel、Church、Kleene、Turing 與 Post 從不同方向追問這件事，幾條研究路線亦在短短數年間逐步匯合。

1931Gödel：把語法算術化

哥德爾為符號、公式和證明建立可機械處理的整數編碼，讓數學語言本身成為數學對象。

1934Herbrand → Gödel：從遞歸方程到 general recursive functions

法國邏輯學家 Jacques Herbrand 曾提出一個未刊構想：以一組方程規定函數值之間的關係。Gödel 在 1934 年的 Princeton lectures 中採用並修改這個想法；Church 其後明確把這套 recursiveness 歸功於 Herbrand 與 Gödel。

這條路線嘗試把「依照固定規則反覆計算」寫成可研究的數學定義。不過 Gödel 當時仍不確定，這個定義是否已涵蓋所有直覺上可以機械執行的程序。

1935–36Church、Kleene、Turing、Post：用不同方法，找出程序可以做到甚麼

他們想解決的問題其實很實際：若有人聲稱「這件事可以按照固定步驟完成」，數學能否準確判斷甚麼才算固定步驟，以及這套步驟最終能處理哪些問題？

Church 與 Kleene 選擇在紙上變換公式，以符號代換描述計算（λ-calculus）；Herbrand、Gödel 與 Kleene 則用一組方程，規定一個函數怎樣由較早的結果逐步算出之後的結果（general recursive functions）。Turing 和 Post 走另一條路：想像一名執行者只按有限指令移動、閱讀、寫下或擦除符號。

這些看起來毫不相似的方法，後來被證明具有相同的計算能力：其中一種方法能完成的程序，也能翻譯成其他方法完成。Church 與 Turing 更分別利用自己的定義證明，並不存在一套固定程序，可以判定所有依照固定符號和文法寫成的數學陳述，是否必然成立。

「可計算」從此不再只是一種直覺，而有了清楚的數學範圍。幾種獨立方法都圈出同一個範圍，亦成為 Church–Turing thesis 的主要根據：凡是能夠按照有限、明確步驟完成的計算，都可以由這些模型表達。

1938–39Turing：用 Gödel representations 逐級擴展邏輯系統

圖靈的博士論文研究一個新的問題：能否把一套邏輯逐級擴展，每次加入新的規則或公理，令它證明原來處理不到、關於整數的數學命題？他用一套代表層級先後的數學記號，把這些系統排列起來，稱為 ordinal logics（序數邏輯）。

要讓下一級的公式辨認和處理上一級的公式，公式便要先成為可以輸入數學運算的對象。圖靈因此明確採用 Gödel 的方法：先替每個符號編配整數，再用質數冪把整串符號編成一個 Gödel representation。其他公式於是可以透過這些整數，枚舉、辨認和轉換被編碼的公式。

在這篇論文裏，Gödel 的編碼不再只是相似的思想，而是圖靈用來建構和分析 ordinal logics 的實際工具。

Before the universal machine

04要研究計算的極限，先要說清楚甚麼叫計算

當時數學家正在研究一個具體問題：能否設計一套固定程序，輸入任何一條形式邏輯陳述後，都能判定它是否必然成立？要研究這種程序是否存在，便要先說清楚「固定程序」究竟可以做哪些動作。

「形式邏輯陳述」是甚麼？

它不是一條「語氣很正式」的句子，而是依照指定符號和文法寫成的數學句子。最簡單的推理形式例如：P → Q；現在知道 P 成立；所以可以推出 Q。P 和 Q 實際代表甚麼可以改變，推理結構卻固定不變。

自然語言的「今天很好」可以有很多解讀；形式邏輯則刻意排除這種含糊。每個符號的作用、句子怎樣才算格式正確，以及可以使用哪些推理規則，都預先寫得清清楚楚。當時的問題，是能否有一套通用程序，逐條判斷任何依照這些規格寫成的陳述，是否在所有符合前提的情況下都成立。

圖靈於是想像一名只依既定規則工作的計算員（在當時，computer 也可以指負責計算的人）。他觀察到，計算員每一刻只會查看紙上的一小部分，寫下或擦去符號，把注意位置向左或向右移，並根據眼前符號與當前狀態決定下一步。

圖靈把這些動作抽出來，變成一條分成一格格的紙帶、一個每次只讀寫一格的讀寫頭、有限種內部狀態，以及一張指令表。「內部狀態」可以理解為機器當刻正在做甚麼，例如「向右尋找下一個空格」、「剛讀到 1，下一步寫下 0」或「工作完成，停止」。

原本只靠直覺理解的「機械計算」，至此變成一個可以精確分析的數學模型。這個模型，後來被稱為 Turing machine（圖靈機）。

每一部圖靈機，都由自己的符號、內部狀態與指令表界定。圖靈再把整張指令表寫成一套標準格式，並編成一個「描述數」（description number）。這個數字代表的不是一道計算的答案，而是一部圖靈機會怎樣逐步運作。

指令表一旦可以寫在紙帶上，它便不再只是一張給人閱讀的說明，而可以成為另一部圖靈機的輸入。圖靈於是再問：可否只造一部機器，讓它讀入任何其他圖靈機的描述，然後照着那份指令表模擬對方？答案是可以。這部能夠模擬其他圖靈機的機器，就是 universal machine（通用機器）。

通用機器讀入兩樣東西：要模擬的圖靈機之描述，以及原本要交給那部圖靈機處理的輸入；然後逐步重現它的行為。換句話說，不必為每一項工作重新造一部機器。同一套執行機制，只要讀入不同指令描述，便可以完成不同工作。

Gödel把數學描述編成整數對象：符號、公式、證明
方法：符號編號與質數冪
作用：讓語法成為算術對象

Turing把機器描述編成輸入對象：狀態、符號、指令表
方法：替狀態、符號與動作逐一編碼
作用：讓一部機器模擬其他機器

哥德爾與圖靈帶來的共同突破，可以直接說成一句話：描述不再只寫給人看；經過編碼，它也能成為系統可以處理的對象。哥德爾讓數學處理數學公式與證明的描述；圖靈則讓一部固定的機器讀取另一部機器的描述，並依照那份描述模擬它。

這一步把「執行工作的機制」與「指定要做甚麼的指令」分開。機制不用改變，只要換一份輸入的指令描述，行為便會隨之改變。下面的示範只集中展示這一點。

史實補充：圖靈的 universal machine 是否直接受 Gödel numbering 啟發？

1936 年 Turing 的研究是否和 Gödel 有因果關係，現時無從證實。現有史料顯示，圖靈可能在 universal machine 的核心構思成形後，才仔細讀到哥德爾的論文。因此，較準確的說法不是「圖靈沿用 Gödel numbering，順勢建構出 universal machine」，而是二人從不同問題出發，分別讓描述成為數學或機器可以處理的對象。

到了 1939 年，關係便十分明確：圖靈在博士論文中採用 Gödel representations，把公式編成整數，再由其他公式枚舉、辨認和轉換這些編碼。正文時間線所寫的，正是這段有文獻可證的技術接續。

05兩位傳奇人物，共同改變了甚麼？

哥德爾把數學陳述與證明編成整數，令數學可以檢查數學語言；圖靈把機器規則編成描述數，令一部機器可以讀取並模擬另一部機器。二人共同打開了新的可能：先把符號、結構與規則變成可處理的輸入，令系統有能力處理描述本身。

1. 內容可以被編碼。公式和證明不再只供人閱讀；它們的符號與排列可以完整保存，交由另一套形式程序處理。
2. 規則可以被檢查。Proof checker 毋須理解一句話想表達甚麼，也能逐步核對公式格式與推導是否符合既定規則。
3. 指令可以成為輸入。一部機器的運作規則可以像其他輸入一樣被讀取，讓另一部機器依照描述模擬它。
4. 執行機制可以與任務分開。同一套通用機制讀入不同程式，便能處理不同工作；程式本身也可以由其他程式檢查、轉譯和修改。

From symbols to AI

06AI 先要有程式，才談得上處理語言

現代 AI 不是一團脫離電腦而存在的「智能」。一套完整的 AI 系統包括規定運算方法的程式、訓練後記下模型所學模式的大量數值（參數）、資料與硬件。讓這些部分真正運作的，仍然是程式：訓練程式反覆讀取資料、計算結果並調整參數；推理程式則載入參數，讀取新的輸入，再一步步計算輸出。

這正是圖靈為現代 AI 提供的最基礎設施：指令可以被表示、儲存、載入和執行，同一套通用計算機制才能按照不同程式完成不同工作。走到今天，人寫的程式先由編譯器翻譯成機器可以執行的指令，作業系統負責載入和管理程式，AI 訓練框架再指揮處理器完成大量數學運算。沒有可編程的電腦與這一層層軟件，AI 的訓練與推理根本無從發生。

Foundation A · Program先讓機器能執行 AI訓練與推理都是程式：它們指揮處理器讀取資料、進行大量數學運算、更新或載入模型參數，再產生輸出。

Foundation B · Encoding再讓語言能進入 AI文字必須先轉成 token、token ID 與向量，才會成為模型程式可以接收和運算的輸入。

一段文字，實際怎樣進入語言模型？

文字首先由 tokenizer 切成一小段一小段的 token；每個 token 再換成一個 token ID。模型利用 ID 找出相應的向量，然後交給 Transformer——一種負責計算各個 token 之間關係的模型架構——逐層處理，最後計算下一個 token 最可能是甚麼。

以上使用 OpenAI 的 o200k_base tokenizer 實際計算；同一句文字換用另一套 tokenizer，切法和 ID 都可能不同。圖中的 v₁、v₂、v₃ 只代表三組向量，實際數值由模型決定。

所以，「AI 可以處理語言」其實包含兩次轉折：先有一套可以執行 AI 的程式，再把語言編碼成這套程式可以處理的數值表示。Gödel number 不是今日的 token ID，Turing machine 也不是 Transformer；但三者共享同一項必要前提：符號與規則必須先變成系統能夠辨認和操作的形式，處理才有可能開始。

由數學陳述變成整數、機器指令變成輸入，再到語言變成 token 與向量，編碼方式已經完全不同；那個最初看似荒謬的轉折卻一直沒有消失：描述本身，也可以成為計算的材料。

數學陳述可以寫成整數，機器指令可以成為輸入，語言也可以轉成 token 與向量。由 2,250 開始的怪異轉換，一路走到程式讀程式、機器模擬機器，再走到 AI 程式將文字轉成數字，從數字生成文字。今次先停在這道門前；下一篇，再和大家一起走進自我指涉的魔法大門。

閱讀範圍說明本文提到「AI」時，為了讓敘事集中，主要以大型語言模型（large language models, LLMs）作為現代例子。AI 並不等於 LLM；推薦系統、擴散模型、電腦視覺系統及其他方法同樣屬於 AI。本文追蹤的是一條由「描述變成可處理的輸入」通向語言模型的歷史與技術脈絡，而不是為 AI 的所有分支提供完整概覽。

← 上篇：哥德爾與變成整數的數學

資料與延伸閱讀

1. Stanford Encyclopedia of Philosophy, 〈Gödel Numbering〉。
2. Kurt Gödel, 〈On Undecidable Propositions of Formal Mathematical Systems〉，1934 年 Princeton lectures 筆記。
3. Alonzo Church, 〈An Unsolvable Problem of Elementary Number Theory〉, 1936；S. C. Kleene, 〈λ-Definability and Recursiveness〉, 1936。
4. Emil L. Post, 〈Finite Combinatory Processes—Formulation 1〉, 1936。
5. Alan M. Turing, 〈On Computable Numbers, with an Application to the Entscheidungsproblem〉, 1936–37。
6. Alan M. Turing, 〈Systems of Logic Based on Ordinals〉, 1939。
7. Rico Sennrich, Barry Haddow & Alexandra Birch, 〈Neural Machine Translation of Rare Words with Subword Units〉, 2016；Ashish Vaswani et al., 〈Attention Is All You Need〉, 2017。
8. OpenAI, 〈Counting tokens〉；tiktoken。文中的 o200k_base token 與 ID 由該編碼器實際計算。
9. Stanford Encyclopedia of Philosophy, 〈The Church–Turing Thesis〉。
10. B. Jack Copeland & Zhao Fan, 〈Did Turing Stand on Gödel’s Shoulders?〉, 2022。
11. Thomas Haigh, 〈Actually, Turing Didn’t Invent the Computer〉, 2014；Jürgen Schmidhuber, 〈Turing Oversold〉，作為不同立場的延伸閱讀。
12. 圖片：Young Kurt Gödel；Alan Turing, 1951。兩者的授權及來源資料見各檔案頁。