把機器編碼成字串（encoding of machines as strings）

編譯器讀取一個程式，但對編譯器而言，那個程式只是一個文字檔，一串字元。原始碼就是資料。同樣的把戲是整個可計算性理論安靜的根基：任何你在意的物件——一張圖、一個文法、一個數字，甚至另一台機器——都能被寫成某字母表上的有限字串，好讓機器把它當輸入。把機器編碼成字串（encoding of machines as strings），就是這個被寫下來的物件本身是一台圖靈機的那個關鍵特例。

我們用 <M> 表示完整描述機器 M 的字串：列出它的狀態、紙帶字母表、起始與接受狀態，以及轉移函數，全都用某個固定、約定好的格式寫在有限字母表（比如二進位）上。那麼 <M, w> 就是把機器 M 與輸入 w 一起編碼的單一字串。確切格式不重要，重要的只是：編碼是有限的、任何良好形成的機器都有一個編碼，而且這份描述能被機械地剖析回來。依慣例我們也規定：任何不是有效編碼的字串，就描述某台固定的「什麼都不做」的機器，於是每個字串都是合法輸入。

這個想法很小，卻足以改變世界。因為一台機器能被餵入另一台機器的編碼，機器就能把機器當輸入並執行它，這正是通用圖靈機所做的事，也正是儲存程式電腦的運作方式（程式就是記憶體裡的資料）。它也是自我參照的門戶：一台機器可以被遞上它自己的編碼，這是遞迴定理的種子，也是證明停機問題不可判定的對角線論證的種子。誠實的提醒是：編碼必須「合理」——易於剖析、其大小與物件的自然大小呈多項式相關——否則你可能透過一套刁鑽巧妙的編碼偷渡額外計算，從而扭曲複雜度結果。