計算理論：可計算的邊界與難解的本質

為什麼有些程式永遠寫不出來？

想像你是一位助教，學生抱怨：「老師，我的程式跑了三天還沒停，是當機還是它真的在算？」這是一個再日常不過的問題，但它的背後藏著二十世紀數學最深刻的發現之一：有些問題，再聰明的程式設計師、再快的電腦，都不可能寫出一個程式來判斷答案。不是現在做不到，而是「永遠」做不到——這是被嚴格證明的數學事實。

計算理論(theory of computation)研究的正是這條界線：什麼是「計算」？哪些問題可以被計算？哪些就算可以，也要花到天荒地老？這門學問把「電腦能做什麼」從工程直覺，提升成可以證明的數學定理。本文會帶你從最簡單的有限狀態機，一路走到圖靈機、停機問題與 P vs NP，看看這條界線到底畫在哪裡。

有限狀態機：記憶力最差的計算模型

我們先從最樸素的計算模型開始：有限狀態機(finite state machine, FSM)，也稱有限自動機(finite automaton)。它的精神是「只有有限多種狀態，每讀一個輸入符號就跳到下一個狀態」。

你每天都在用它。捷運閘門有「上鎖」與「開鎖」兩個狀態：投幣或刷卡讓它從上鎖跳到開鎖，通過後再跳回上鎖。紅綠燈、自動販賣機、電梯按鈕邏輯，本質上都是有限狀態機。

形式上，一個有限狀態機由五個元素組成：狀態集合 $Q$、輸入字母表 $\Sigma$、轉移函數 $\delta$、起始狀態 $q_0$，以及接受狀態集合 $F$。它能辨認的語言類別稱為正規語言(regular language)——例如「字串裡有偶數個 a」這類規則，FSM 都能勝任。

但 FSM 有個致命弱點：它沒有記憶體，只能記住「目前在哪個狀態」。經典的反例是「判斷一段括號是否完全配對」，例如 ((()))。要做到這件事，你必須記住「目前還有幾個左括號沒配對」，而這個數字可以無限大，有限的狀態根本記不下來。這就說明了 FSM 的計算能力有上限，我們需要更強的模型。

圖靈機：計算的終極定義

1936 年，圖靈(Alan Turing)提出了一個極簡卻無比強大的模型——圖靈機(Turing machine)。它只比有限狀態機多了一樣東西：一條無限長的紙帶(tape)，以及一個能在紙帶上讀、寫、左右移動的讀寫頭。

別小看這條紙帶。有了它，機器就有了「無限的記憶體」，可以記下任意多的中間結果。圖靈機的運作規則很簡單：根據「目前狀態」與「讀寫頭下方的符號」，決定要寫什麼符號、往左還往右移、跳到哪個狀態。

驚人的是：目前人類已知的所有計算模型，計算能力都不超過圖靈機。你的筆電、超級電腦、量子電腦（在「可計算性」層次上）能算的，圖靈機都能算（只是慢得多）。這個觀察被稱為邱奇–圖靈論題(Church–Turing thesis)：凡是「直覺上可被機械化計算」的東西，都等價於圖靈機可計算。它不是定理（無法證明「直覺」），而是一個被廣泛接受的論題。

於是「可計算(computable)」有了精確定義：一個問題是可計算的，當且僅當存在一台圖靈機，對任何輸入都能在有限步內停下來並給出正確答案。

停機問題：第一個被證明不可解的問題

定義清楚之後，自然要問：是不是每個問題都可計算？圖靈的答案是響亮的「不」。他找出了第一個不可解(undecidable)的問題——停機問題(halting problem)：

輸入一個程式 $P$ 和它的輸入 $x$，判斷 $P(x)$ 會不會停下來（而不是無限迴圈）。

這正是本文開頭那位助教面對的難題。直覺上，我們很想寫一個「萬能偵測器」halts(P, x)，回傳 True 表示會停、False 表示會無限跑。圖靈證明了：這樣的程式不可能存在。

動手看一個例子：對角論證

證明停機問題不可解，用的是優美的對角論證(diagonal argument)（與康托爾證明實數不可數同源）。我們用反證法：

假設真的有一個萬能函數 halts(P, x)，永遠正確回答 $P$ 在輸入 $x$ 下會不會停。那我們就能用它造出一個搗蛋程式 paradox：

def halts(P, x):
    # 假設這個函數存在且永遠正確
    # 回傳 True 表示 P(x) 會停止，False 表示會無限迴圈
    ...

def paradox(P):
    if halts(P, P):      # 問：把 P 自己餵給 P 會停嗎？
        while True:      # 如果會停，paradox 偏偏故意無限迴圈
            pass
    else:
        return           # 如果不會停，paradox 偏偏馬上停止

關鍵的一步：把 paradox 餵給它自己，問 paradox(paradox) 到底會不會停？

• 情況一：假設 paradox(paradox) 會停。 那麼 halts(paradox, paradox) 回傳 True，於是程式進入 while True 無限迴圈——不會停。矛盾。
• 情況二：假設 paradox(paradox) 不會停。 那麼 halts(paradox, paradox) 回傳 False，於是程式走到 return——馬上停。矛盾。

兩種情況都自相矛盾。唯一的脫困之道，是當初的假設錯了：halts 這個萬能函數根本不存在。停機問題不可解。

這裡的「對角」精神在於：我們讓 paradox 對「自己被自己處理的結果」唱反調，就像在一張「程式 × 輸入」的無限大表格中，沿著對角線把每個答案都翻轉，造出一個不在表格裡的反例。這個證明的威力極大——它告訴我們，不可解性不是因為人類不夠聰明，而是邏輯上的內在限制。許多實務問題（如「兩個程式是否等價」「這段程式會不會存取到空指標」）都可以化約到停機問題，因此同樣不可解。這也是為什麼編譯器與靜態分析工具永遠只能「保守近似」，無法做到完美。

可解之後的下一道牆：要花多少時間？

不可解是一道牆，但更多時候我們面對的問題是「可解，但慢得要命」。這就進入計算複雜度(computational complexity)的領域：一個可解問題，需要多少時間（或空間）才能解出？

我們用大 O 記號(big-O notation)描述演算法隨輸入規模 $n$ 成長的趨勢。例如排序好的演算法是 $O(n \log n)$，暴力檢查所有配對是 $O(n^2)$，而枚舉所有子集合則是 $O(2^n)$。前兩者隨 $n$ 平緩成長，最後一個則是指數爆炸——$n=100$ 時 $2^{100}$ 已經比宇宙原子數還多。

複雜度理論把問題分成幾個重要類別：

P vs NP：千禧年最著名的未解問題

P 是「能快速解出來」的問題，NP 是「答案給你後能快速驗證」的問題。

舉個生活例子。把一桌客人分配座位，要求「每對吵架的人不能同桌」——要你從頭排出一個合法方案很費勁（可能要試遍各種組合），但如果有人遞給你一份排好的座位表，你只要掃一遍每對吵架名單，幾分鐘就能確認合不合法。「解出來難、驗證起來易」，正是 NP 的精髓。

顯然 $P \subseteq NP$：能快速解出來的，當然能快速驗證。但反過來呢？所有能快速驗證的問題，是否都能快速解出來？也就是：

$$P \overset{?}{=} NP$$

這就是著名的 P vs NP 問題，是克雷數學研究所(Clay Mathematics Institute)懸賞百萬美元的七大千禧年難題之一，至今懸而未決。多數研究者相信 $P \neq NP$（驗證真的比求解容易），但沒有人能證明。

NP-complete 與歸約：難題之間的橋樑

P vs NP 之所以如此牽動人心，關鍵在 NP-complete（NP 完全）這個概念。一個問題若是 NP-complete，代表它同時滿足兩件事：(1) 它在 NP 裡；(2) NP 中所有問題都能在多項式時間內「歸約」到它。

歸約(reduction)是計算理論的核心武器，意思是「把問題 A 轉換成問題 B」：如果我能用一個快速的轉換程序，把任何 A 的實例變成 B 的實例，使得「A 有解 ⟺ B 有解」，那麼一旦我有了解 B 的快速演算法，就等於同時解了 A。我們寫成 $A \le_p B$，讀作「A 多項式歸約到 B」，直覺是「B 至少和 A 一樣難」。

1971 年，庫克(Stephen Cook)證明了布林滿足性問題(SAT)是第一個 NP-complete 問題。之後卡普(Richard Karp)用一連串歸約，證明了 21 個經典問題同樣是 NP-complete。這條歸約鏈帶來一個震撼的結論：

只要有任何一個 NP-complete 問題被找到多項式時間演算法，那麼透過歸約，所有 NP 問題都瞬間變成 P，於是 $P = NP$。反之，只要證明任何一個 NP-complete 問題不可能有多項式解，就證明了 $P \neq NP$。

換句話說，數千個看似無關的難題（晶片佈線、班表排程、蛋白質摺疊、物流最佳化⋯⋯）其實是「同一個難題的不同面貌」，命運被一條歸約鏈綁在一起。這也是為什麼當你在工作中遇到一個問題「怎麼都找不到快速解法」時，一個務實的做法是證明它是 NP-complete——這等於告訴老闆「不是我不努力，而是全世界最頂尖的人努力了五十年都沒解出來」，於是大家轉而尋求近似解或啟發式演算法。

動手看一個例子：一次具體的歸約

我們示範如何把「3-SAT」歸約成「圖的獨立集(independent set)」，感受歸約的味道。3-SAT 問的是：給一個布林公式（若干子句，每個子句是三個文字的 OR），能否指派真假值讓整個公式為真？

公式：(x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ x₃)
                                    ↓ 歸約建圖
建圖規則：
  1. 每個子句畫成一個三角形（3 個節點，代表 3 個文字）
  2. 同一三角形內 3 點兩兩連線（迫使每子句最多選 1 點）
  3. 互為相反的文字（如 x₁ 與 ¬x₁）跨三角形連線
  4. 問：圖中是否存在大小為「子句數」的獨立集？

對應關係：
  原公式可滿足  ⟺  圖中存在大小 = 子句數的獨立集
  （選進獨立集的點 = 每個子句中被選為「真」的那個文字）

這個轉換可以在多項式時間內完成。於是「解獨立集」與「解 3-SAT」在難度上等價——它們要嘛一起變簡單，要嘛一起難下去。實作歸約時要嚴守合法用途：這些技巧用於演算法分析、密碼學安全性論證（例如說明某破解任務「至少和某 NP-hard 問題一樣難」），而非用來規避運算或攻擊系統。

重點回顧

• 有限狀態機能力有限（沒有記憶體），只能辨認正規語言；圖靈機多了無限紙帶，定義了「可計算」的邊界，這是邱奇–圖靈論題的核心。
• 停機問題不可解：用對角論證可嚴格證明，沒有任何程式能判斷「任意程式是否會停」。這是邏輯的內在限制，不是技術不足。
• 複雜度用大 O 記號刻畫成長趨勢；P 是可快速解出、NP 是可快速驗證的問題類別。
• NP-complete 是 NP 中最難的一群，靠歸約彼此相連；只要其一有多項式解，全體 NP 都隨之崩解為 P。
• P vs NP 至今未解，是理論計算機科學最重要的開放問題，深刻影響密碼學、最佳化與人工智慧。

深入探討（研究所視角）

研究所層次會把上述直覺嚴格化，並延伸出更精細的層級結構與技術工具。

不可解性的層級——算術階層(arithmetical hierarchy)。 停機問題只是不可解性的「第一層」。它對應 $\Sigma_1^0$ 類（可半判定：會停的話我們終究會發現，但不會停就無從確認）。更高層如「判斷一個程式是否對所有輸入都停止」（全停機問題）則屬 $\Pi_2^0$，比停機問題嚴格地更難。萊斯定理(Rice's theorem)進一步把這個壞消息一般化：任何關於「程式所計算函數」的非平凡語意性質都不可解——這從根本上解釋了為何完美的程式驗證、病毒偵測、死碼消除都不可能存在，只能退而求其次做保守近似。圖靈跳躍(Turing jump)算子 $\emptyset'$ 形式化了「相對於停機問題的更難問題」，建構出無窮上升的不可解度(Turing degree)階梯。

P vs NP 的證明障礙。 為什麼這個問題五十年來無人攻克？研究者反過來證明了「哪些方法注定無效」。相對化障礙(relativization, Baker–Gill–Solovay)指出：存在一個諭示(oracle) $A$ 使 $P^A = NP^A$，又存在另一個 $B$ 使 $P^B \neq NP^B$；因此任何對諭示「視而不見」的證明技巧（如單純的對角論證）都不可能解決 P vs NP。自然證明障礙(natural proofs, Razborov–Rudich)則說明：若單向函數存在，則一大類「自然」的電路下界證明策略也無法奏效。這兩道障礙告訴我們，解決 P vs NP 需要本質上的新數學工具。

與密碼學的存亡關係。 現代密碼學的安全性，幾乎全部建立在「某些問題難解」的假設上。RSA 倚賴大整數因式分解、橢圓曲線倚賴離散對數的困難性。值得注意的是：$P \neq NP$ 是密碼學安全的必要條件，卻非充分條件——即使 $P \neq NP$，我們仍需要「平均情況(average-case)困難」而非僅「最壞情況困難」，以及單向函數的存在性。若有朝一日證明 $P = NP$ 且歸約常數夠小，今日的公開金鑰密碼將全面失守；這也是後量子密碼學(post-quantum cryptography)研究格密碼(lattice-based)等新困難假設的動機之一。

與本讀本其他主題的連結。 計算理論是整個資訊科學的地基：編譯器的詞法分析直接用有限狀態機與正規表達式；資料庫查詢最佳化、排程、編譯器暫存器配置都會碰上 NP-hard 子問題而改用啟發式；人工智慧的搜尋與推理本質是在指數空間中找捷徑；而資訊安全的整個信任模型，正是把「攻擊者必須解開某個難題」轉化為可量化的安全保證。理解這條從「可不可計算」到「划不划得來計算」的界線，能讓學習者在面對任何工程難題時，先判斷「這是值得繼續優化的問題，還是該換個方向的不可能任務」。