可計算性理論與複雜度理論
計算理論是電腦科學的理論基礎，探討計算的本質、能力與極限。這個領域回答了「什麼可以被計算？」、「計算需要多少資源？」以及「哪些問題是無法解決的？」等基本問題。計算理論的發展始於 1930 年代，當時數學家們試圖理解希爾伯特提出的判定問題，最終形成了圖靈機、λ 演算等計算模型，為現代電腦科學奠定了堅實的理論基礎。
┌─────────────────────────────────────────────────────────────┐ │ 計算模型層次 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 圖靈機 (Turing Machine) │ │ • 最強大的計算模型 │ │ • 可模擬任何其他合理計算模型 │ │ • Church-Turing 論點的基礎 │ │ ↓ │ │ λ演算 (Lambda Calculus) │ │ • 函數式計算的基礎 │ │ • 閉包、高階函數 │ │ ↓ │ │ 上下文無關文法 (Context-Free Grammar) │ │ • 程式語言語法理論 │ │ • 自動機理論 │ │ ↓ │ │ 正規語言 (Regular Language) │ │ • 有限狀態機 │ │ • 詞法分析基礎 │ └─────────────────────────────────────────────────────────────┘
每個模型都有其獨特的能力和限制，從最強大的圖靈機到最簡單的正則語言，構成了一個清晰的階層結構。
可計算性理論探討哪些問題可以被解決，哪些問題是無法解決的。其核心結果包括：
停機問題是計算理論中最著名的不可判定問題。它詢問：是否存在一個程式能判斷任意程式是否會停止？證明使用反證法，假設存在函式 Halt(P, I)，構造 Paradox(P) 導致矛盾，因此這樣的 Halt 函式不可能存在。這意味著存在無法用演算法解決的問題，電腦有本質上的限制。
Church-Turing 論點聲稱：任何可有效計算的函數都可以由圖靈機計算。這不是一個定理，而是一個猜想，基於丘奇從 λ 演算角度和圖靈從圖靈機角度的獨立研究，兩者被證明是等價的。
除了停機問題，還有 Post 對應問題、一階邏輯有效性、上下文無關文法交集、DFA 語言等價性等經典不可判定問題。Rice 定理更進一步指出：任何非平凡的語言性質都是不可判定的。
複雜度理論將問題按照求解所需的資源（時間、空間）進行分類：
┌─────────────────────────────────────────────────────────────┐ │ 複雜度層次 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ O(1) 常數時間 陣列存取 │ │ ↓ │ │ O(log n) 對數時間 二分搜尋 │ │ ↓ │ │ O(n) 線性時間 線性搜尋 │ │ ↓ │ │ O(n log n) 線性對數 合併排序 │ │ ↓ │ │ O(nᵏ) 多項式時間 P 類 │ │ ↓ │ │ O(kⁿ) 指數時間 組合爆炸 │ └─────────────────────────────────────────────────────────────┘
P 類問題可以在多項式時間內解決；NP 類問題可以在多項式時間內驗證解答。NP-Complete 是 NP 類中最難的問題。P vs NP 問題是計算機科學中最大的未解決問題之一。
若 n = 10：O(n) = 10 步，O(n²) = 100 步，O(2ⁿ) = 1024 步。若 n = 30：O(n) = 30 步，O(n²) = 900 步，O(2³⁰) ≈ 10 億步。這就是為什麼 NP-Complete 問題被認為「困難」。
Paradox(P):
if Halt(P, P) then
無限迴圈
else
停止
Paradox(Paradox) 是否停機？若 Halt 說會停機則進入無限迴圈，若說不會停機則會停止——矛盾。因此 Halt 不可能存在。