Skip to content

Computing › CS 基礎 › 可計算性與圖靈機

可計算性與圖靈機 (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-completeNP 中最難的一群;任一個有多項式解則全部都有布林可滿足性 (SAT)、多重序列比對的最佳解

P 是否等於 NP 仍是未解問題。實務上面對 NP-hard 問題,改用啟發式 (heuristic) 或近似演算法:多重序列比對工具(MAFFT、Clustal)、演化樹搜尋、基因組組裝都是如此,結果是「夠好」而非保證最佳。