1.3 圖靈機與問題的模型化#

概念說明#

要嚴格定義「多項式時間」、「P」與「NP」，我們需要一個精確的計算模型。1936 年 Alan Turing 提出的圖靈機（Turing Machine）就是這個模型：一條無限長的紙帶、一個讀寫頭、一組有限的狀態與轉移規則。雖然它看起來與真實電腦相去甚遠，但Church-Turing 命題主張：任何「可被有效計算」的函數，都可以被圖靈機計算。數十年來所有提出的計算模型（λ-演算、暫存器機、C 或 Python 寫成的真實程式）在可計算能力上都被證明與圖靈機等價。

在複雜度理論中，我們主要使用兩種圖靈機：

判定性圖靈機（決策問題）：輸入一個字串 x，輸出「是」或「否」。大多數 NP 理論以此為主，例如「這個圖是否存在漢米爾頓迴路？」
非決定性圖靈機（NDTM）：在每一步可以「同時」探索多種選擇，若存在任一分支導致接受，整台機器就算接受。它可以想成「永遠猜對下一步」的機器，或等價地、平行窮舉所有分支的機器。NP 的正式定義正是「能被非決定性圖靈機在多項式時間內解決的問題」。

問題的模型化是關鍵一步：一個真實世界的問題（例如「安排期末考試時間表」）必須先轉成形式化的輸入—輸出規格，才能談論其複雜度。決策問題的標準形式是：

給定輸入 x（以某編碼寫成字串），判斷 x 是否屬於某個語言 L ⊆ {0,1}*。

「語言」就是所有答案是「是」的輸入所構成的集合。這個看起來抽象的定義讓我們能把「問題」與「字串集合」畫上等號，而圖靈機判定語言、演算法解決問題，都是同一件事。

演算法步驟：把真實問題模型化為決策問題#

明確定義輸入的格式（例如：圖以頂點列表與邊列表表示；整數以二進位編碼）。
把「最佳化問題」轉成對應的決策問題：把「求最小值」改成「是否存在值 ≤ K 的解？」。例如 TSP 的決策版本：「是否存在總長度 ≤ K 且經過每城一次的巡迴？」
定義「是」實例與「否」實例的明確標準。
說明解的格式（這將成為之後章節的「憑證」），確保解的長度是輸入大小的多項式。

Python 程式碼範例#

我們用 Python 模擬一台簡單的圖靈機，判定語言 L = {0ⁿ1ⁿ : n ≥ 0}（同樣數量的 0 後面接同樣數量的 1）。這是教科書上的經典範例，說明圖靈機如何逐步處理輸入。

def turing_machine_0n1n(tape):
    """模擬判定 L = {0^n 1^n} 的單帶圖靈機。
    規則：
      狀態 q0：把最左的 0 劃掉，右移找 1
      狀態 q1：把配對的 1 劃掉，左移回頭
      狀態 q2：回掃檢查是否全部劃掉（接受）
    符號：'X' 代表已劃掉，'_' 代表空白
    """
    tape = list(tape) + ['_']
    head, state = 0, 'q0'
    transitions = 0
    while True:
        transitions += 1
        if transitions > 10000:   # 防止意外卡死
            return False, transitions
        sym = tape[head]
        if state == 'q0':
            if sym == '0':
                tape[head] = 'X'; head += 1
                while tape[head] in '0X':
                    head += 1
                if tape[head] != '1':
                    return False, transitions
                tape[head] = 'X'; head -= 1
                state = 'q1'
            elif sym == 'X':
                # 沒有 0 了，檢查後面是否還有殘留的 1
                while tape[head] == 'X':
                    head += 1
                return tape[head] == '_', transitions
            else:
                return False, transitions
        elif state == 'q1':
            while head >= 0 and tape[head] in 'X1':
                head -= 1
            head += 1
            state = 'q0'

for s in ["", "01", "0011", "000111", "0000111", "10"]:
    ok, steps = turing_machine_0n1n(s)
    print(f"輸入 {s!r:>12} -> {'接受' if ok else '拒絕'}（{steps} 步）")

輸出結果會正確地接受 ""、"01"、"0011"、"000111"，並拒絕 "0000111" 與 "10"。這台圖靈機對長度為 N 的輸入大約執行 O(N²) 步——多項式時間，因此 L = {0ⁿ1ⁿ} 屬於 P。

複雜度分析#

我們的模擬每劃掉一組 0/1 需要左右各掃一遍紙帶，共 O(N) 步，重複 N/2 組，總步數 O(N²)。
圖靈機與真實電腦之間存在多項式模擬關係：任何 Python 程式在時間 T(n) 內完成的工作，圖靈機可用 O(T(n)²) 或 O(T(n) log T(n)) 步完成。因此在「是否多項式時間」這個層次上，用哪個模型分析結論都一樣——這正是第 1.2 節所說的 robustness。
非決定性圖靈機的能力：一台在多項式時間 p(n) 內運作的 NDTM，其所有分支構成一棵深度 p(n)、分支度 b 的樹，等價於窮舉 b^(p(n)) 種選擇。這解釋了為什麼 NP 問題用決定性機器「直接解」通常得花指數時間。

練習#

修改上述圖靈機程式，使其判定 L = {0ⁿ1²ⁿ : n ≥ 0}（每個 0 配兩個 1），並用 "001111" 等例子測試。
把「背包問題」寫成決策問題的規格：明確寫出輸入格式、問題敘述、以及什麼是一個「是」實例。
說明為什麼「非決定性圖靈機可以在多項式時間解決的問題」與「存在長度多項式、可多項式時間驗證的解之問題」描述的是同一個類別。這個等價性將在第 3 章正式展開。