1944-Post 不可解度#

案件摘要#

1944 年，Emil Post 在《Recursively enumerable sets of positive integers and their decision problems》中提出「不可解度」（degrees of unsolvability）的綱領：不可解問題不是一團混沌，而是有層次、有結構的宇宙。他留下著名的「Post 問題」：是否存在介於 \(0\) 與 \(0'\) 之間的度？

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

1936 年 Turing 與 Church 各自證明停機問題不可判定，但這只給了「一個」不可解問題。
人們很快發現許多問題彼此「一樣難」：可以互相歸約。例如停機問題與 Hilbert 第十問題（雖然後者 1970 年才解決）。
Post 的偵探直覺：既然有「一樣難」，就應該有「比較難」與「比較簡單」——不可解性本身應該是一門幾何學。他稱之為「相對可計算性」（relative computability）的研究綱領。

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

Turing 歸約與等價#

集合 \(A\) Turing 歸約到 \(B\) （記作 \(A \leq_T B\) ），若存在一個使用 \(B\) 作為「預言機」（oracle）的可計算函數可判定 \(A\) ：

\[ A \leq_T B \iff \exists e \;[\chi_A = \Phi_e^{B}] \]

其中 \(\Phi_e^B\) 表示第 \(e\) 台圖靈機在執行中可任意查詢「 \(n \in B\) ？」並立即得到答案。若 \(A \leq_T B\) 且 \(B \leq_T A\) ，則稱 \(A \equiv_T B\) （Turing 等價）。

\(\equiv_T\) 是等價關係，其等價類 \([A]_T\) 就是不可解度。歸約 \(\leq_T\) 誘導出度上的偏序：

\[ \mathbf{a} \leq \mathbf{b} \iff \exists A \in \mathbf{a}, B \in \mathbf{b} \;[A \leq_T B] \]

跳躍算子（jump operator）#

對任意集合 \(A\) ，定義其跳躍：

\[ A' = \{ e : \Phi_e^{A}(e) \downarrow \} \]

即「以 \(A\) 為預言機的停機問題」。跳躍算子滿足： - \(A'\) 不可解於 \(A\) （ \(A' \nleq_T A\) ），且 \(A \leq_T A'\) 。 - 跳躍是度的階梯：由此得到度的塔

\[ \mathbf{0} < \mathbf{0'} < \mathbf{0''} < \mathbf{0'''} < \cdots \]

\(\mathbf{0}\) ：可判定集合的度（如「 \(n\) 是偶數」）。
\(\mathbf{0'}\) ：停機問題的度，即經典不可解問題。
\(\mathbf{0''}\) ：「停機問題的停機問題」，比停機問題更不可解——例如判定某 Turing 機機器集合的極限行為、算術階層中 \(\Pi^0_2\) 層的完備問題。

跳躍算子將度映到更高的度，且在 \(\mathbf{0}\) 之上連續可得（ \(A\) 可計算枚舉時 \(A'\) 亦然），這使 \(\mathbf{0'}\) 成為整個可計算枚舉度世界的「最高峰候選」。

Post 問題與 Friedberg–Muchnik 定理#

Post 觀察到所有當時已知的可計算枚舉（c.e.）集合若不可判定，似乎都與 \(K\) （停機問題）同度。他問：

是否存在 c.e. 集合 \(S\) 使 \(\mathbf{0} <_T S <_T \mathbf{0'}\) ？

Post 嘗試用「簡單集」（simple sets，補集為無限且不含無限 c.e. 子集）攻擊此問題，但單靠 lattice 論證失敗。直到 1956 年，Friedberg 與 Muchnik 各自獨立以「有限傷害優先權方法」（finite injury priority method）解決：

存在 c.e. 集合 \(A, B\) 使 \(A \nleq_T B\) 且 \(B \nleq_T A\) （創造性分離），其中 \(A\) 可取為非可判定，從而給出中間度。

此方法的精髓：同時滿足無限多個需求 \(R_e: A \neq \Phi_e\) 與 \(S_e: B \neq \Psi_e\) ，允許需求被「傷害」（破壞）有限次，靠優先權排序證明每個需求最終安定。這開啟了優先權方法這門技術學派。

Python 階層式示意（概念模擬，非真實構造）：

# 概念示意：優先權方法「想要」達到的效果
# 需求 Re: 階段 s 時 A(e) 尚未與 Phi_e 分離 -> 改變 A(e) (傷害低優先權需求)
def priority_construction(reqs, stages):
    A = set()
    for s in range(stages):
        for e, action in sorted(enumerate(reqs), key=lambda x: x[0]):
            if action(A, s):          # 若需求 Re 在階段 s 可行動
                A ^= {s % 10}         # 翻轉一個元素（可能傷害 e 之後的需求）
                break                  # 有限傷害：每個需求只被打斷有限次
    return A  # 理論上得到中間度集合的近似

度的格結構#

不可解度 \(\mathcal{D}\) 在 \(\leq\) 下形成上半格（upper semilattice）： - 任兩度 \(\mathbf{a}, \mathbf{b}\) 有最小上界 \(\mathbf{a} \cup \mathbf{b}\) （取 join，對應集合的不相交並）。 - 但沒有一般的最大下界（infimum 不一定存在）——所以不是格。 - \(\mathcal{D}\) 沒有最大元（Spector 證明跳躍的逆不唯一）。 - c.e. 度 \(\mathcal{R}\) 同樣是上半格，Friedberg–Muchnik 證明其結構比 \(\mathbf{0'}\) 一點的鏈複雜得多。

相對可計算性#

Post 的核心哲學：可計算性是「相對的」概念。預言機圖靈機 \(\Phi_e^B\) 定義了「相對於 \(B\) 可計算」。這個框架後來成為： - 算術階層（arithmetic hierarchy）的度論解讀。 - 遞迴論（recursion theory）改名為「可計算性理論」的基礎。 - 演化成今日研究 random degree、generic degree、enumeration degree 的現代度論。

結案 -- 後果與影響#

結案：Post 問題於 1956 年由 Friedberg–Muchnik 解決——中間度存在，不可解世界不是一條線而是一團稠密的迷宮（ \(\mathbf{0'}\) 之下無「孤立點」的猜測部分成立）。
優先權方法成為可計算性理論最重要的技術，衍生無限傷害、 \(\emptyset'\) -優先權、0-1 法則等。
度論與模型論、描述集合論結合，產生有效描述集合論。
深遠影響：不可解度成為衡量「超越 P/NP 之外」問題難度的理論尺規；在 reverse mathematics 中， \(\mathbf{0', 0''}\) 對應二階算術的不同 subsystem。

關鍵人物與文獻#

Emil Post（1897–1954）：波蘭裔美國邏輯學家，《Recursively enumerable sets of positive integers and their decision problems》, Bull. AMS, 1944。
Richard Friedberg（美國）與 Albert Muchnik（蘇聯）：1956 年各自獨立解決 Post 問題。
Clifford Spector：證明度上半格無最大元、最小度定理。
Gerald Sacks：《Degrees of Unsolvability》, 1963，度論的系統化教科書。
Alan Turing：1939 年引入預言機（oracle machine），為相對可計算性提供計算模型。