外觀
可計算性與圖靈機 (Computability and Turing Machines)
可計算性 (computability) 問的是:一個問題是否存在一定會在有限時間結束的演算法來解。這是理論上的可解性,和硬體快不快無關;有些問題不管給多少運算資源都不可能用一般演算法解決。
| 類型 | 意義 |
|---|---|
| 可計算 (computable / decidable) | 存在演算法對所有輸入都能在有限時間停下並給出答案 |
| 不可計算 (non-computable / undecidable) | 不存在能處理所有輸入的演算法 |
自動機:計算模型的層級
自動機 (automaton) 是抽象的機器,用來分析「有多少記憶體、怎麼轉換狀態」能解決哪一類問題。
| 模型 | 記憶體 | 能辨識 | 實務對應 |
|---|---|---|---|
| 有限狀態自動機 (finite automaton) | 只有有限個狀態 | 正規語言 (regular language) | 正規表達式、詞法分析、序列 motif 掃描 |
| 下推自動機 (pushdown automaton) | 加上一個堆疊 | 上下文無關語言 (context-free) | 巢狀結構:括號配對、程式語言語法解析、RNA 二級結構(stem-loop 的鹼基配對) |
| 圖靈機 (Turing machine) | 無限長的紙帶,可讀寫 | 所有可計算的問題 | 一般用途電腦的理論模型 |
記憶體模型越強,能表達的問題類別越大。這也解釋了為什麼正規表達式無法正確匹配任意深度的巢狀括號:那需要堆疊。
圖靈機
| 組成 | 作用 |
|---|---|
| 紙帶 (tape) | 無限長,當作記憶體 |
| 讀寫頭 (head) | 讀寫目前格子的符號,左移或右移 |
| 狀態與轉移規則 | 依「目前狀態 + 讀到的符號」決定寫什麼、往哪移、進入哪個狀態 |
圖靈機重要不是因為真實電腦長這樣,而是它給「演算法」一個嚴格定義。邱奇-圖靈論題 (Church–Turing thesis):任何直觀上可以用演算法計算的東西,圖靈機都能計算。一般的程式語言(Python、Java、甚至 Excel 公式加上 LAMBDA)都是圖靈完備 (Turing complete),計算能力等價。
停機問題 (Halting Problem)
是否存在一個通用演算法,能判斷任意程式在任意輸入下會停止還是永遠執行?
答案是否定的(Turing, 1936)。證明思路是反證:假設存在判斷器 halts(p, x),就能構造一個程式「若 halts 說我會停,我就無限迴圈;反之就停」,把它餵給自己時產生矛盾。
| 影響 | 說明 |
|---|---|
| 有些問題注定無解 | 「更多算力」無法移除理論上的限制 |
| 靜態分析有極限 | 編譯器、linter、防毒軟體無法完美預測所有程式的行為,只能近似(會有誤報或漏報) |
| 萊斯定理 (Rice's theorem) | 任何關於程式「行為」的非平凡性質都不可判定 |
可計算 ≠ 算得完
可計算性問「能不能」,複雜度問「要多久」。很多問題可計算,但已知演算法需要指數時間:
| 類別 | 意義 | 例子 |
|---|---|---|
| P | 多項式時間可解 | 排序、最短路徑 |
| NP | 給定答案可在多項式時間驗證 | 數獨、旅行推銷員(判定版) |
| NP-complete | NP 中最難的一群;任一個有多項式解則全部都有 | 布林可滿足性 (SAT)、多重序列比對的最佳解 |
P 是否等於 NP 仍是未解問題。實務上面對 NP-hard 問題,改用啟發式 (heuristic) 或近似演算法:多重序列比對工具(MAFFT、Clustal)、演化樹搜尋、基因組組裝都是如此,結果是「夠好」而非保證最佳。