可計算性與問題的邊界 (Computability)#
複雜度分析回答的是「要多久」，但有一個更根本的問題：有些問題，到底能不能用程式解決？
這就是「可計算性」的範疇。它劃出的是比複雜度更外層的邊界。
三個層級：可高效解、難解、不可解#
把所有問題攤開來看，會發現它們落在三個層級：
| 層級 | 例子 | 狀態 |
|---|---|---|
| 可高效解（P） | 排序、最短路徑 | 有多項式時間演算法 |
| 難解（NP-hard） | 旅行推銷員、排桌問題 | 可解，但目前找不到高效演算法 |
| 不可解（undecidable） | 停機問題 | 數學上可證明：永遠寫不出正確演算法 |
「難解」和「不可解」是兩回事。旅行推銷員問題很難，但給你一條路線，你能驗證它的長度——它是可解的，只是慢。停機問題則是從根本上無解，不是「還沒想到演算法」，而是「可以證明這樣的演算法不存在」。
P 與 NP：求解 vs 驗證#
| 問題類別 | 定義 | 一句話 |
|---|---|---|
| P | 計算量是規模 n 的多項式函數 | 求解本身就快，「計算機能有效解決」 |
| NP | 能在多項式時間內驗證答案，但不保證能在多項式時間內找出答案 | 驗證快，求解不一定快 |
最好懂的切入點是數獨：給你一份填好的答案，你能秒驗對錯（驗證很快）；但從一張空白盤面把它填出來，卻可能很慢（求解很難）。「驗證容易、求解困難」正是 NP 的精神。
「是否存在一個問題，驗證容易但求解一定困難？」——這就是著名的 P =? NP 問題，至今未解。
停機問題：一個可證明無解的問題#
給定任意一個程式和它的輸入，能不能寫出一個萬能的檢查器，判斷這個程式會停止、還是會永遠跑下去？
答案是：不可能。而且這可以嚴格證明。
證明的精髓是反證 + 自我指涉：
- 假設這個萬能檢查器
WillHalt(程式, 輸入)存在。 - 用它造一個搗蛋程式
Trouble(程式)：如果WillHalt說「會停」，它就故意進入無窮迴圈；如果說「不會停」，它就立刻停止。 - 現在問一個刁鑽的問題：把
Trouble拿來對它自己執行，會發生什麼？
無論 WillHalt 給出哪個答案，Trouble 都會做出相反的行為——矛盾。所以那個萬能檢查器根本不可能存在。
自我指涉的搗蛋程式（偽碼）
// 假設這個萬能檢查器存在（實際上不可能）
external fun willHalt(program: Program, input: Program): Boolean
// 用它造一個故意跟預測作對的程式
fun trouble(program: Program) {
if (willHalt(program, program)) {
while (true) { /* 預測「會停」→ 偏偏無窮迴圈 */ }
} else {
return // 預測「不會停」→ 偏偏立刻停止
}
}
// 關鍵一問：trouble(::trouble) 會停還是不會停？
// 兩種答案都導致矛盾 → willHalt 不可能存在「程式可以把程式當成輸入、甚至以自身為輸入」這種自我指涉，是計算機科學最深刻的推理範式之一。同樣的對角線手法，也被用來證明「實數比整數多」等深刻結論。
理論極限 ≠ 沒用#
「不可判定」只是說：沒有演算法能對所有情況都正確。但這不代表相關工具沒用——
我們仍然能寫出「對大多數程式、找出大多數錯誤」的工具。現代的靜態分析器（static analyzer）、linter 正是如此：它們放棄了「對所有情況都正確」的奢望，換來在實務上極其有用的部分解。
記住兩條邊界線：
- 可計算性：這個問題能不能解？（停機問題：不能）
- 複雜度：能解的問題，要花多久？（旅行推銷員：能解，但很慢）
看清楚一道題卡在哪一層，你才知道該「換演算法」、該「求近似解」、還是該「換個問題」。