1936 - Kleene 的 μ-遞迴函數（部分遞迴函數）#

案件摘要#

1936 年，Stephen Kleene 在 Church 門下將 Gödel 的原始遞迴函數補上一個「極小化算子」 \(\mu\) ，得到部分遞迴函數。本案追查：這個小小的 \(\mu\) 如何讓遞迴函數類追上圖靈機的表達能力。

前因 -- 為什麼會有這個案子#

• 1931 年 Gödel 用原始遞迴函數表達可計算的算術運算，但原始遞迴函數「必然停機」，表達力不足（例如 Ackermann 函數不在其中）。
• 1933 年 Church 提出 λ 演算可定義函數作為「可計算」的候選定義。
• Kleene 證明 λ 可定義函數恰好等於某類遞迴函數——這類函數需要一個新的算子：極小化。

線索與推理 -- 數學式、程式、理論#

1. 原始遞迴函數#

基本函數（初始函數）： - 零函數： \(Z(x) = 0\) - 後繼函數： \(S(x) = x + 1\) - 投影函數： \(P_i^n(x_1,\dots,x_n) = x_i\)

兩個建構規則： - 複合： \(h(\vec{x}) = f(g_1(\vec{x}),\dots,g_m(\vec{x}))\) - 原始遞迴：

原始遞迴函數 = 由基本函數經有限次複合與原始遞迴得到的函數，全函數且必然可計算（可用 Gödel 編號證明）。

2. μ 算子（極小化算子）#

部分遞迴函數 = 原始遞迴函數加上 μ 算子的閉包。關鍵差異： - 若 \(f(\vec{x},y)=0\) 無解， \(\mu\) 搜尋永不停止 → 函數變成部分函數（某些輸入無定義）。 - 這正好對應圖靈機的「不停機」現象！

3. 部分遞迴函數 = 圖靈可計算#

三種等價證明概述： - (⇒) 原始遞迴對應簡單迴圈（for）；μ 對應無界搜尋（while）。迴圈機（while 程式）可被圖靈機模擬：把程式與資料編碼在紙帶上逐步執行。 - (⇐) 圖靈機的組態可用 Gödel 編號編碼為自然數；「從組態 \(c\) 經一步到組態 \(c'\) 」是原始遞迴關係；「最終停機的組態」用 μ 算子搜尋停機時間：

其中 \(U\) 是原始遞迴的「輸出解碼」函數。這就是 Kleene 正規形式定理。

4. Python 實作：Ackermann 函數（非原始遞迴但可計算）#

import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def A(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return A(m - 1, 1)
    return A(m - 1, A(m, n - 1))

# Ackermann 增長快過所有原始遞迴函數
print(A(0, 5))    # 6
print(A(1, 5))    # 7
print(A(2, 3))    # 9
print(A(3, 3))    # 61
# print(A(4, 2))  # 19329 位數，印證其爆炸性增長

# μ 算子的 Python 對應：無界搜尋（可能不停止）
def mu(f, x):
    y = 0
    while f(x, y) != 0:
        y += 1
    return y

print(mu(lambda x, y: (x % (y + 2)), 17))  # 找 17 的最小非平凡因數-2

Ackermann 用雙重遞迴（內層遞迴值作為外層遞迴參數）超越了原始遞迴的界限，但仍在 μ-遞迴/圖靈可計算範圍內——這是「部分遞迴類嚴格更大」的直接證據。

結案 -- 後果與影響#

• Kleene 正規形式定理給出所有部分可計算函數的統一表示，是遞迴論（可計算性理論）的基石。
• 「必然停機的全遞迴函數」與「可能不停機的部分遞迴函數」的區分，直接孕育了停機問題與不可判定性研究（1936 Turing 同年證明）。
• μ-遞迴函數成為後來 Rice 定理、遞迴可枚舉集、算術階層等理論的語言基礎。

關鍵人物與文獻#

• Stephen Kleene（1909–1994），Church 的學生，普林斯頓。
• Kleene, S. C. (1936). "General recursive functions of natural numbers." Mathematische Annalen, 112: 727–742.
• Kleene, S. C. (1952). Introduction to Metamathematics.（正規形式與命名系統化）
• 相關：Gödel (1931)、Church (1936)、Turing (1936)。