計算與演算法是什麼

一杯泡麵與一台機器能共享的祕密

請想像一個再日常不過的場景：你拿起泡麵包裝，照著背面的步驟「撕開調味包、加入八百毫升熱水、蓋上蓋子等三分鐘」，三分鐘後一碗熱騰騰的麵就完成了。你大概不會覺得自己剛剛做了什麼了不起的事，但若把這個過程拆解開來，它其實具備了一個演算法(algorithm)應有的全部要素：明確的步驟、確定的輸入（熱水、麵體）、可預期的輸出（煮好的麵），以及保證在有限時間內結束。

換句話說，「計算」並不是電腦的專利。當你按食譜做菜、用直式除法算數、或照地圖規劃路線時，你的大腦正在執行演算法。電腦之所以特別，只是因為它能用驚人的速度與精準度，把這些步驟一絲不苟地重複執行數十億次。要理解資訊科學，第一步就是理解：計算的本質，是一連串「機械式地、按規則操作符號」的過程。這一篇我們就從這個樸素的觀察出發，建立起對「計算」與「演算法」的精確理解。

計算是什麼：把問題變成步驟

在資訊科學裡，計算(computation) 指的是依據一組明確規則，將「輸入」逐步轉換為「輸出」的過程。注意這個定義刻意不提「數字」——計算處理的對象是符號(symbol)，而符號可以是數字、文字、像素、聲音波形，甚至是 DNA 序列。把一段中文翻成英文、把一張照片變模糊、把一份履歷依關鍵字排序，全都是計算。

這個觀點帶來一個深刻的轉變：我們不再問「電腦會不會算數學」，而是問「這個問題能不能被表達成一連串明確的符號操作步驟」。如果可以，那麼原則上任何具備足夠能力的計算裝置——無論是人、機械齒輪，還是矽晶片——都能執行它。這也是為什麼同一個排序演算法，可以用 Python 寫、用紙筆做、甚至用一排撲克牌示範。

計算的核心要素可以濃縮成三件事：

演算法的五大特性：什麼樣的步驟才算數

並不是任何一串「步驟」都能稱為演算法。資訊科學界（這套定義可追溯到 Donald Knuth 的經典整理）為演算法訂下了五個必要特性，缺一不可：

1. 有限性(finiteness)：演算法必須在執行有限個步驟後停止。一份「無限攪拌直到天荒地老」的食譜不是演算法，因為它永遠不會結束。
2. 明確性(definiteness)：每一個步驟都必須精確、無歧義。「加適量的鹽」對人類廚師可以，但對演算法不行——「適量」需要被定義成「加 2 公克」這種明確的量。
3. 輸入(input)：演算法有零個或多個輸入。是的，可以是零個——例如一個直接印出「Hello」的程式。
4. 輸出(output)：演算法有一個或多個輸出，且輸出與輸入之間有明確的關係。沒有輸出的計算等於白做工。
5. 有效性(effectiveness)：每個步驟都必須是基本到「原則上能用紙筆在有限時間內精確執行」的操作。「請直接寫出圓周率的所有位數」就違反有效性，因為那是無限的。

這五大特性看似嚴格，卻是把「模糊的想法」變成「可被機器執行的程序」的關鍵門檻。許多初學者寫出無法運作的程式，根源往往就是某個步驟不夠明確，或忘了保證會停止（造成無窮迴圈）。

動手看一個例子：歐幾里得演算法

讓我們看一個兩千多年前就被記載、至今仍在用的真實演算法——求兩個正整數最大公因數(GCD)的歐幾里得演算法(Euclidean algorithm)。它完美展示了上述五大特性。

規則只有兩句話：

要求 a 與 b 的最大公因數：
  1. 若 b 等於 0，則答案是 a，結束。
  2. 否則，把 (a, b) 換成 (b, a 除以 b 的餘數)，回到步驟 1。

我們用 $a=48$、$b=36$ 逐步追蹤：

輸出是 12，正是 48 與 36 的最大公因數。我們逐一檢查五大特性：它有兩個輸入（48、36）、一個輸出（12）；每步明確（取餘數、做比較都無歧義）；每步有效（餘數運算紙筆可做）；而且因為餘數一定嚴格變小、且非負，所以必然在有限步驟內讓 b 變成 0——有限性成立。

寫成 Python 幾乎是逐字翻譯：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 36))  # 輸出 12

請注意：上面那段「規則」和這段 Python 程式，描述的是同一個演算法。差別只在於一個用自然語言、一個用程式語言——這個區別，正是下一節的重點。

抽象與分解：對付複雜問題的兩把武器

真實世界的問題往往龐大到無法一次想清楚。資訊科學提供了兩種互補的思維工具來應對。

分解(decomposition) 是把一個大問題拆成數個較小、較容易處理的子問題。例如「做一個校園選課系統」可以拆成「使用者登入」、「課程查詢」、「衝堂檢查」、「送出選課」等模組，每個都小到能獨立設計與測試。這正是泡麵食譜把「煮麵」拆成「加水、等待、攪拌」的同一種智慧。

抽象(abstraction) 則是刻意忽略當下不重要的細節，只保留與問題相關的本質。當你使用 gcd(48, 36) 時，你不需要知道 CPU 內部如何做除法、餘數如何用二進位表示——這些細節被「藏」在函式名稱背後。抽象讓我們得以站在前人的肩膀上：每一層只需信任下一層提供的「介面」，而不必重新理解整個世界。

抽象的威力在於它層層堆疊：電晶體之上是邏輯閘，邏輯閘之上是 CPU 指令，指令之上是程式語言，語言之上是函式庫，函式庫之上是你的應用程式。學習資訊科學，很大程度上就是學習在適當的抽象層次上思考——既不被細節淹沒，也不在需要時無法往下挖掘。

問題與解之別：別把答案當成問題本身

初學者常混淆兩件事：問題(problem) 與解(solution)。

「問題」是對「給定什麼輸入、要產生什麼輸出」的規格描述，它不關心怎麼做。例如「排序問題」的規格是：給定一串數字，輸出一串由小到大排列、且包含相同元素的數字。

「解」則是達成這個規格的具體演算法。對同一個排序問題，氣泡排序(bubble sort)、合併排序(merge sort)、快速排序(quicksort)都是合法的解，它們輸出相同，但效率天差地別。

把問題與解分開，是評估與選擇的基礎。我們可以問：「這個問題最少需要多少計算成本？」（這屬於計算複雜度理論的範疇），也可以問：「我手上這個解，效率離理論下限有多遠？」一個排序問題在基於比較的模型下，最佳解的時間複雜度是 $O(n \log n)$，這意味著無論你多聰明，只要靠兩兩比較，就不可能比這個快太多。認清這層界線，能讓你避免在已知無望的方向上鑽牛角尖。

可計算與不可計算：有些問題沒有演算法

我們前面樂觀地假設「只要能拆成明確步驟，問題就能解」。但二十世紀最震撼的數學發現之一是：有些問題，原則上就不存在任何演算法能解決它們——無論電腦多快、記憶體多大都一樣。

最著名的例子是停機問題(halting problem)：能不能寫一個萬能程式，讀入「任意一段程式碼與它的輸入」，然後百分之百正確地判斷這段程式究竟會「跑完停下來」還是「永遠跑下去」？直覺上這似乎只是個工程難題，但 Alan Turing 在 1936 年證明了：這樣的萬能判斷程式根本不可能存在。這不是我們還不夠聰明，而是邏輯上的不可能。

這個結果劃下了一條根本的界線——把所有問題分成「可計算(computable)」與「不可計算(uncomputable)」兩大類。它告訴我們：計算雖然威力強大，卻有其先天極限。理解這條界線，比盲目相信「電腦無所不能」要成熟得多。我們會在後面的章節更深入地探討這個迷人的主題，此處先在你心中種下一顆種子。

重點回顧

• 計算是依明確規則把輸入逐步轉為輸出的過程，處理對象是符號而非僅限數字；計算無所不在，電腦只是執行得又快又準。
• 演算法必須同時滿足五大特性：有限性、明確性、（零或多個）輸入、（一或多個）輸出、有效性，缺一不可。
• 抽象（忽略無關細節）與分解（拆解大問題）是駕馭複雜度的兩把核心武器。
• 問題是「要什麼」的規格，解是「怎麼做」的演算法；同一問題可有多個效率不同的解。
• 並非所有問題都可計算——停機問題證明了某些問題原則上不存在演算法，計算有其先天極限。

深入探討（研究所視角）

計算模型與圖靈機：為「計算」本身下定義

我們一直在用「明確步驟」這種直覺式說法描述計算，但要做嚴謹的理論，必須先回答一個更根本的問題：「可計算」到底該如何精確定義？ 1936 年，Alan Turing 提出了圖靈機(Turing machine) 作為答案。

圖靈機是一個極度簡化的抽象裝置：一條無限長、被分成方格的紙帶；一個能在紙帶上左右移動、讀寫符號的讀寫頭；以及一張有限的「狀態轉移規則表」，規定「在某狀態下讀到某符號時，該寫什麼、往哪移、進入哪個狀態」。形式上常寫成七元組：

$$ M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}) $$

其中 $Q$ 是有限狀態集、$\Gamma$ 是紙帶符號集、$\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ 是轉移函數。看似簡陋，但它捕捉到了「機械式計算」的全部本質。

這引出了著名的 Church–Turing 論題(Church–Turing thesis)：任何「直覺上可被有效計算」的函數，都能被圖靈機計算。這不是一個可被證明的數學定理，而是一個關於「計算」這個概念邊界的論斷，至今所有提出的計算模型（λ 演算、遞迴函數、現代程式語言）都被證明與圖靈機等價，沒有任何反例。它的深刻之處在於：你手中的筆電、超級電腦、量子電腦（在可計算性的意義上），能算的問題集合完全相同——差別只在於效率，而非能力。

有了圖靈機，停機問題的不可計算性也能被嚴謹證明（透過對角化論證，與 Cantor 證明實數不可數、Gödel 不完備定理同源），並進一步發展出歸約(reduction) 的技術：若能把已知不可計算的問題 A「轉化」成問題 B，則 B 也必定不可計算。這套機制是可計算性理論(computability theory)的基石。

演算法 vs 程式：抽象規格與具體實現

研究所層級必須清楚區分兩個常被混用的詞：演算法(algorithm) 與程式(program)。

演算法是與語言、機器無關的抽象解題程序——它是一個數學物件，可以用自然語言、流程圖或虛擬碼(pseudocode)描述，存在於「想法」的層次。前面的歐幾里得演算法，無論你用 Python、C、組合語言，甚至用算盤實現，都是「同一個」演算法。

程式則是某個演算法在特定語言、特定機器上的具體實現(implementation)。同一個演算法可以有無數種程式實現，它們可能在記憶體配置、變數命名、語言慣用法上各不相同，但體現的計算邏輯相同。反過來，一段程式也未必對應「一個」乾淨的演算法——它可能糾纏了多個演算法、輸入輸出處理與錯誤恢復。

這個區別在工程與研究上都至關重要：

• 正確性分析針對演算法（用迴圈不變量(loop invariant)、數學歸納法證明），而非綁死在某種語言的語法上。歐幾里得演算法的正確性，源自「$\gcd(a, b) = \gcd(b, a \bmod b)$」這條數論恆等式，與 Python 無關。
• 複雜度分析也屬於演算法層次：我們說 quicksort 平均 $O(n \log n)$、最差 $O(n^2)$，講的是演算法的漸進行為，而非某次執行的實際毫秒數（那受硬體、編譯器、快取(cache)行為影響）。
• 可移植性：先在抽象層次設計好正確且高效的演算法，再翻譯成具體程式，能讓同一套邏輯跨平台重用。

一個有用的心智模型是：演算法之於程式，正如樂譜之於演奏。樂譜（演算法）規定了音符的相對關係，是抽象而永恆的；演奏（程式）則是在特定樂器、特定場地的一次具體實現。理解這層分野，你才能在「設計演算法」與「實作程式」這兩種思維模式間自如切換——而這正是資訊科學專業訓練的核心能力之一。