BlooP、FlooP 與 GlooP

自我覺察與混沌#

BlooP、FlooP、GlooP 是作者為本章發明的三種程式語言。它們的角色是釐清「遞迴」一詞在計算理論中的不同含義——尤其是原始遞迴（primitive recursive）與一般遞迴（general recursive）。這些概念將用來說明 TNT 的自我指涉機制。

在自然數系統中，有秩序的系統一旦複雜到足以鏡像自身，就必然包含某些奇異、混沌的特徵——這是哥德爾定理的核心精神之一。

但混沌之中也有秩序——這是「遞迴函數理論」這門學科的源頭。

可表徵性（Representability）：足夠強大的判準#

「足夠複雜」、「足夠強大」這些詞要如何定義？

在《Contracrostipunctus》中，蟹想用冰箱當「完美唱機」，因為冰箱可放任何唱片在上面——但冰箱根本沒有播放能力。同理，要把烏龜的「我不能在唱機 X 上播放」這招用上，X 必須是真正的唱機。

對形式系統而言：

可表徵所有原始遞迴真理，是「足夠強大」的判準。
一個系統若達到這個門檻，哥德爾的方法就可施加於它，使其不完備；一個系統若未達到這個門檻，它本身就因表達力不足而不完備。
無論如何，哥德爾之斧（Gödel’s Ax，「岩頭斬猴」的後設數學版）都會落下。

BlooP：有界迴圈的語言#

要刻畫「可預期長度的計算」，從以下基本步驟出發：

加法、乘法
比較相等、比較大小

僅這些原始步驟還不夠，必須加上控制結構。BlooP 的關鍵限制是：

BlooP 唯一的控制結構是「有界迴圈（bounded loop）」——可重複執行的指令組，但有預先決定的上限。

上限不一定要在程式中寫定，可由先前計算的結果決定。例如計算 2 的 3^N 次方：

DEFINE PROCEDURE "TWO-TO-THE-THREE-TO-THE" [N]:
BLOCK 0: BEGIN
  CELL(0) ← 1;
  LOOP N TIMES:
  BLOCK 1: BEGIN
    CELL(0) ← 3 × CELL(0);
  BLOCK 1: END;

  CELL(1) ← 1;
  LOOP CELL(0) TIMES:
  BLOCK 2: BEGIN
    CELL(1) ← 2 × CELL(1);
  BLOCK 2: END;

  OUTPUT ← CELL(1);
BLOCK 0: END.

BlooP 的特色#

區塊結構（block structure）：以 BEGIN/END 劃定
IF 分支與 QUIT/ABORT 跳出
自動分塊：已定義的程序可在後續定義中當作原始步驟
測試（test）：輸出為 YES 或 NO 的程序（名稱以 ? 結尾）

BlooP 計算的函數稱為原始遞迴函數；BlooP 測試的性質稱為原始遞迴謂詞。例如「N 是質數嗎？」、「N 是否有 Goldbach 性質」皆是原始遞迴。

並非所有事都是原始遞迴#

利用康托爾（Cantor）的**對角線方法（diagonal method）**可以證明：

B = 所有「無呼叫、單參數、計算函數」的 BlooP 程式（藍程式）
依長度與字典序，每個藍程式有唯一索引號 k：Blueprogram{#k}

定義函數：
  Bluediag[N] = 1 + Blueprogram{#N}[N]

Bluediag[N] 顯然是人類可計算的，但它不在任何藍程式的列表中—— 若它是第 X 個藍程式，則代入 N=X 時自相矛盾（X 等於 X+1）。
結論：存在不能由 BlooP 程式計算的函數。

康托爾的原始對角論證#

康托爾證明實數集無法被自然數列舉：

r(1): .1 4 1 5 9 2 6 5 3 ...
r(2): .3 3 3 3 3 3 3 3 3 ...
r(3): .7 1 8 2 8 1 8 2 8 ...
r(4): .4 1 4 2 1 3 5 6 2 ...
...

取對角數字 1, 3, 8, 2, ...
每個減 1（0 視為 9）：0, 2, 7, 1, ...

得到 d = .0271...，不可能在列表中

兩種「對角證明」的差別在於回頭撤回哪個假設：

康托爾：實數可被列舉 → 不可
本章：Bluediag 可被 BlooP 計算 → 不可

對角方法的本質：把同一個整數同時當作兩種角色使用——一次當索引、一次當輸入——以此構造出超出列表的對象。

FlooP：解除迴圈束縛#

放寬 BlooP 的限制：允許無上限迴圈（MU-LOOP）：

MU-LOOP:
  BLOCK n: BEGIN
    ...
  BLOCK n: END

MU 來自數理邏輯中的 μ-運算子（mu-operator），用於不受限的搜尋。命名上呼應趙州的「無（MU）」——FlooP 對某些輸入的「不回答」恰似公案式的非答。

代價是：FlooP 程式對某些輸入可能永不終止。

例如可以寫一個 FlooP 測試判定 N 是否「奇妙」（每次若偶數則除 2，若奇數則乘 3 加 1，最終回到 1）：

若 N 奇妙 → 回 YES
若 N 落入非 1-4-2-1-4-2 之外的封閉循環 → 回 NO
若 N 引發無限上升序列 → 永不終止

終止測試：圖靈的詭計#

理想中，希望能寫一個程序 TERMINATOR? 來檢測任意 FlooP 程式是否會終止——這需要把程式編碼為哥德爾數作為輸入。

圖靈（Alan Turing）證明：這樣的終止測試不可能存在。

論證的精神類似哥德爾：把終止測試器自身的哥德爾數餵給它，會導致矛盾。

為什麼終止測試這麼強大？#

若它存在，所有數論問題都可一律解決：

- 要驗證 Goldbach 變體：寫測試 TORTOISE? 程式
- 用 TERMINATOR? 檢測它是否對所有輸入終止
- 若終止 → 命題為真；若不終止 → 反例存在

換言之，問題的答案藏在「程式碼的形式」中——根本不必執行它。這太美好以致不可能成立。

紅程式與第二次對角論證#

引入終止測試器後，可從 FlooP 中過濾出紅程式（保證對所有輸入終止）。再次施加對角論證：

Reddiag[N] = 1 + Redprogram{#N}[N]

得到一個明確可計算、卻不在 FlooP 中的函數。

這雙重打擊讓我們別無選擇——必須撤回「終止測試器存在」的假設。

GlooP 是個迷思#

是否能繼續放寬 FlooP，造出更強的 GlooP？

邱奇—圖靈論題（Church-Turing Thesis）：
凡是人類可計算的，皆是機器可計算的
凡是機器可計算的，皆是 FlooP 可計算的
因此：凡人類可計算的，皆是 FlooP 可計算的（一般或部分遞迴）

不論你如何「自然地」設計一種新語言，最後得到的力量都等同於 FlooP——這是計算理論中相當穩固的事實。

術語整理#

原始遞迴（primitive recursive）：BlooP 可計算（必終止）
一般遞迴（general recursive）：FlooP 可計算且總是終止
部分遞迴（partial recursive）：FlooP 可計算但可能不終止
平日所稱「遞迴」多半指一般遞迴

TNT 的強度#

TNT 強大到：不只原始遞迴謂詞、連一般遞迴謂詞都能被表徵。

換句話說，任何「可在有限時間內由演算法判定真假」的數論陳述，在 TNT 中也是可判定的。這保證了 TNT 是「足夠強大」的——使得哥德爾的方法可施加於它，導致下一章將證明的不完備性。