跳轉到

7.2 遞迴函數與CHURCHTURING論題#

本章導言#

「可計算」在 1936 年獲得了至少四個獨立的候選定義：Turing 機、Church 的 λ 演算、Gödel–Herbrand 的遞迴函數、Post 的正規系統。全部被證明外延等價。這種多路收斂是「可計算性」概念的客觀性的最強證據，也是 Church–Turing 論題（機械可計算 = Turing 可計算）成立的經驗基礎。本節講遞迴函數的層級（原始遞迴 → μ-遞迴）、λ 演算的簡潔性、以及論題的精確地位——它是定義辯護、經驗概括還是定理？

原始遞迴函數：可計算的「安全區」#

從三個初始函數出發，用兩個運算封閉：

  • 初始函數：零函數 \(Z(x) = 0\) ；後繼 \(S(x) = x+1\) ；投影 \(P_i^n(x_1, \dots, x_n) = x_i\) 。
  • 合成： \(f(\vec x) = g(h_1(\vec x), \dots, h_k(\vec x))\) 。
  • 原始遞迴： \(f(0, \vec x) = g(\vec x)\) ； \(f(n+1, \vec x) = h(f(n, \vec x), n, \vec x)\) 。

由此得加法（ \(x + 0 = x\) ， \(x + (n+1) = S(x + n)\) ）、乘法、冪、階乘等一切「顯式循環」可算的函數。原始遞迴函數全可計算，且計算步數可預先界定——這正是 Hilbert「有限方法」的天然形式化（3.3、6.3 節的 PRA 就是其公理化）。

但原始遞迴不夠：Ackermann 函數

\[ A(0, n) = n+1; \quad A(m+1, 0) = A(m, 1); \quad A(m+1, n+1) = A(m, A(m+1, n)) \]

是良定義的全函數、直觀可計算，但增長快於一切原始遞迴函數（Péter 1935；Gödel 1931 已用此例）。「預先知道步數」比「可計算」嚴格——需要一個更寬的概念。

μ-遞迴函數：受控的無界搜索#

μ 運算（極小化）： \(\mu y\, [g(\vec x, y) = 0]\) = 最小的 \(y\) 使 \(g(\vec x, y) = 0\) （若不存在則未定義）。

μ-遞迴函數 = 由初始函數經合成、原始遞迴、μ 運算得到的（部分）函數。μ 允許無界搜索——這正是「步數不可預知」的計算的抽象，也是部分函數（可能不停機）的來源。Turing 機計算的恰是 μ-遞迴部分函數，反之亦然（Kleene 1936 的等價性證明）。

遞迴可枚舉（r.e.）集：某 μ-遞迴函數的定義域，等價於某 Turing 機接受的集合。停機問題的集合是 r.e. 但其補不 r.e.（7.3 節）——這一不對稱是半可判定性的根源。

λ 演算：Church 的極簡計算#

Church 的 λ 演算只有三樣：變元、抽象 \(\lambda x. M\) 、應用 \(MN\) 。歸約規則一條（β 歸約）：

\[ (\lambda x. M)\, N \to M[x := N]. \]

例子：數字的 Church 編碼 \(\bar 2 = \lambda f. \lambda x. f(f\, x)\) ；加法 \(= \lambda m. \lambda n. \lambda f. \lambda x.\, m\, f\, (n\, f\, x)\) 。純符號操作，無狀態、無紙帶，卻 Turing 完備。

λ 演算的歷史命運獨特：作為可計算性模型它被 Turing 機取代，作為函數式程式設計的語法它統治了部分計算機科學——Lisp（1958）、ML、Haskell、以及今日每種語言的匿名函數。理論輸給了工程隱喻（機器），語法贏得了語言設計。

Church–Turing 論題的精確地位#

論題：直觀的「機械可計算函數」類 = Turing 可計算函數類 = μ-遞迴函數類 = λ 可定義函數類。

其認識論地位有三層：

  1. 數學定理部分：四個形式概念的外延等價（可證）。
  2. 定義辯護部分：「機械可計算」無先驗形式定義，論題主張這個形式概念抓住了它——不可證明，但可被論證。
  3. 經驗概括部分：迄今一切被接受的「算法」皆落在此類內；物理 Church–Turing 論題（一切物理過程可被計算模擬）是更強的經驗主張。

Gödel 的立場值得記錄：他在 1934 年普林斯頓講課時用 Herbrand–Gödel 遞迴函數但不確信其完備性；1936 年讀到 Turing 的分析後表示信服——「人類計算員」的分析比「形式系統的操作」更能說服邏輯學家。Kreisel 1987 稱此為「對論題的分析性證明」的典範。

一個具體例子#

例題 7.2.1：證明 \(f(n) = n!\) 是原始遞迴函數，並給出其原始遞迴定義的展開計算 \(3!\) 。

解：定義

\[ \operatorname{fact}(0) = 1; \qquad \operatorname{fact}(n+1) = (n+1) \cdot \operatorname{fact}(n). \]

形式化： \(\operatorname{fact} = \operatorname{PR}(g, h)\) ，其中 \(g(\vec x) = 1\) （常函數，由 \(Z\) 與 \(S\) 合成得 \(1 = S(Z(x))\) ）， \(h(k, n, \vec x) = S(n) \times k\) （乘法先由原始遞迴定義： \(x \cdot 0 = 0\) ， \(x \cdot (n+1) = (x \cdot n) + x\) ，加法同理）。

計算 \(3!\) ： \(\operatorname{fact}(0) = 1\) ； \(\operatorname{fact}(1) = h(1, 0) = S(0) \times 1 = 1\) ； \(\operatorname{fact}(2) = h(1, 1) = 2 \times 1 = 2\) ； \(\operatorname{fact}(3) = h(2, 2) = 3 \times 2 = 6\) 。 \(\blacksquare\)

例題 7.2.2：證明 Ackermann 函數 \(A\) 不是原始遞迴的（思路證明），並計算 \(A(2, 2)\) 。

解：思路：對每個原始遞迴函數 \(f\) ，存在 \(k\) 使 \(f(n) < A(k, n)\) 對一切 \(n\) （原始遞迴的構造對增長率的封閉性：初始函數增長慢、合成與原始遞迴提高的增長率可被某固定層 \(A(k, \cdot)\) 蓋住——對構造歸納）。而 \(A\) 本身滿足 \(A(m+1, n) > A(m, n)\) 對一切層次，故 \(A\) 超過所有 \(f\) —— \(A\) 非原始遞迴。

計算： \(A(0, n) = n+1\) ； \(A(1, n) = n + 2\) ； \(A(2, n) = 2n + 3\) 。故 \(A(2, 2) = 7\) 。 \(A(3, n) = 2^{n+3} - 3\) ； \(A(4, n)\) 已是 tetration 級——四層之後原始遞迴的分層描述徹底失效。 \(\blacksquare\)

論題的當代延伸#

  • 多項式時間可計算（P）：複雜性理論的 Church–Turing 式論題（Cobham–Edmonds 1964）：「可行計算 = 多項式時間 Turing 計算」——同樣是定義辯護 + 經驗概括，同樣有多路收斂（隨機存取機、電路、λ 演算在多項式歸約下等價）。
  • 量子計算：量子 Turing 機計算的仍是遞迴可枚舉函數（可計算性不變），但多項式時間類可能擴大（BQP vs BPP）——論題在可計算性層穩固，在複雜性層開放。
  • 超計算（hypercomputation）：若接受非標準物理（無窮精度的實數、Malament–Hogarth 時空），理論上可突破 Turing 界——但一切已知物理未提供。論題的邊界由物理學而非邏輯學守衛。

歷史啟示#

  • 概念的客觀性由獨立收斂證明：四個定義從不同動機出發（機器、符號操作、形式系統、組合規則）收斂於同一類——這是概念「已經在那裡」的最強證據，如同 1.2 節實數的多重建構。
  • 層級的教訓：原始遞迴（可預知步數）≠ 可計算（可能不停機）——「保證停機」是可計算性內部的鴻溝，正是停機問題不可判定的直接來源。
  • 理論模型與工程隱喻的競爭：Turing 的「機器」隱喻贏得硬體，Church 的「函數」語法贏得軟體——同一概念的兩個化身，各得其所。

與其他章節及領域的關聯#

  • 3.3、6.3 節：PRA = 原始遞迴函數的公理化，是「有限方法」的正式定義。
  • 6.2 節：可表示性定理連接遞迴函數與算術。
  • 7.1、7.3 節：Turing 機與不可判定性。
  • 9.2 節：構造性證明的計算內容 = 提取出的（原始）遞迴程式。
  • 10.2 節：HoTT 的「計算規則」繼承 λ 演算的歸約傳統。
  • 計算機科學：λ 演算 = 函數式語言；μ 運算 = while 迴圈；原始遞迴 = for 迴圈——可計算性層級直接對應程式語言的迴圈結構（Meyer–Ritchie 的 LOOP 程式語言）。
  • 認知科學：「心智是否超出 Turing 界」的爭論（Lucas–Penrose）以論題為靶（10.3 節）。

練習#

  1. 用原始遞迴定義 \(x^y\) 與 \(\gcd(x, y)\) （後者需先證明帶餘除法原始遞迴可定義——用有界 μ 運算）。
  2. 計算 \(A(3, 3)\) ，並估計 \(A(4, 1)\) 的量級。
  3. 證明：有界 μ 運算（ \(\mu y \le z\, [\dots]\) ）保持原始遞迴性。
  4. 在 λ 演算中構造 \(\bar 3 \cdot \bar 2\) 的 β 歸約序列，驗證結果為 \(\bar 6\) 的 Church 編碼。
  5. 思考題：Cobham–Edmonds 論題（可行 = 多項式）比 Church–Turing 論題更具經驗性。舉出一個「理論多項式但不實用」的例子，並討論複雜性論題的脆弱性。

進階研讀：三個深化場景#

場景一：Kleene 的正常形式定理（1936）。每個 μ-遞迴函數可寫為 \(U(\mu y\, T(e, \vec x, y))\) ， \(T\) 是通用原始遞迴謂詞、 \(U\) 是固定的原始遞迴函數。整個可計算性被壓縮為「一次有界搜索 + 一個固定解碼器」——正常形式定理是遞迴論的「緊緻化」，一切後續理論（遞迴定理、度理論）建立其上。

場景二：Herbrand–Gödel 與 Kleene 的命名政治。「一般遞迴函數」的定義由 Herbrand 1931 信中提出、Gödel 1934 講課推廣、Kleene 1936 正式化。Kleene 造了「recursive」一詞並堅持之；「computable」因 Turing 而興。1980s 起學界逐步改名為「computable」——術語史是概念史的化石層。

場景三：從論題到物理。Deutsch 1985「量子 Turing 機」與「物理 Church–Turing 論題」的重述：每個有限物理系統可被量子計算機模擬。Landauer「資訊是物理的」（1961）與 Wolfram、Hutter 的計算宇宙論——可計算性的邊界問題從邏輯轉入物理，是基礎研究的最新外延。

名詞速查表#

  • 原始遞迴：初始函數 + 合成 + 原始遞迴（步數可預知）。
  • μ 運算：無界極小化搜索；引入部分函數。
  • μ-遞迴函數：全體 Turing 可計算部分函數。
  • 遞迴可枚舉（r.e.）：μ-遞迴函數的定義域；半可判定。
  • Ackermann 函數：全可計算但非原始遞迴。
  • Church 編碼：以高階函數表示數據的 λ 演算表示法。
  • 正常形式定理： \(U(\mu y\, T(e, \vec x, y))\) 的壓縮表示。

年表速查#

  • 1931：Herbrand 信件；Gödel 不完備（含可表示性）。
  • 1934：Gödel 普林斯頓講課（Herbrand–Gödel 遞迴）；Church λ 演算。
  • 1935：Péter 分析 Ackermann 函數。
  • 1936：Kleene 正常形式；Church 論文；Turing 論文。
  • 1943：Post 正規系統。
  • 1964：Cobham–Edmonds 多項式論題。
  • 1985：Deutsch 量子 Turing 機。

深化問答三則#

問：為什麼需要四個等價定義，一個不夠嗎？ 答：夠用，但不多餘：多路收斂是論題（定義辯護）的唯一證據類型。單一定義可能是「一種方法」；四個獨立動機的定義外延相同，指向概念本身的客觀性。概念的「被發現」而非「被發明」的身份，由收斂認證——與實數（Dedekind vs Cantor）與幾何（多種模型）的歷史同構。

問：部分函數（不停機）是缺陷嗎？ 答：不是，是本質。若要求一切可計算函數全定義且可判定「是否給出結果」，則與停機問題矛盾。部分性是無界搜索的必然代價；類型論（9.3 節）以「全函數 + 良基遞迴」在部分領域恢復全性——代價是表達力受限（不能寫任意 while 迴圈）。

問：論題會被「證偽」嗎？ 答：其數學部分（等價性）不會。其經驗部分會——若發現可複製的物理過程計算非 Turing 可計算函數。但「可複製、可驗證、有限資源」的嚴格條件使此可能性極小。論題的現狀：邏輯內穩固、物理上開放、哲學上作為「機械性」的工作定義——這是科學中成功概念的典型狀態。

（本節完）