為什麼要抽象地研究「計算」？
你已經會寫能在真實電腦上跑的程式了。計算理論則退後一步，撇開任何特定的語言或晶片，問一些更直白、也更恆久的問題：到底有什麼是「可以被計算」的？有什麼是「可以被快速計算」的？是否存在某些問題，任何機器上的任何程式，無論現在還是未來，都永遠無法解出？這些答案不取決於你寫的是 Python 還是 C，也不取決於明年的處理器有多快——而這份恆久性，正是重點所在。
要把這些問題問得精準，我們需要一個計算模型：它得簡單到能拿來證明定理，卻又誠實地反映真實機器在做的事。整門課的策略，是先從一台微小、孱弱、能被我們完全看透的機器開始，再一次一小步、小心翼翼地為它增添能力，並仔細觀察每一項新本領究竟換來了什麼。每個模型都對應著一族「它能處理」與「它無法處理」的問題。
最基本的原子：字母表、符號與字串
我們所計算的一切，都建立在一個固定、有限的字母表之上，記作 Σ（希臘大寫的 sigma）。字母表不過是一組被允許的符號的集合——例如位元用 Σ = {0, 1}，或是 Σ = {a, b}。字串則是一串有限個符號照順序黏在一起的序列，像 0110 或 aabba。一個字串裡的符號個數就是它的長度；字串 0110 的長度是 4。
有一個長度為 0 的特殊字串：空字串，記作 epsilon（希臘字母 ε）。它是一個完全沒有任何符號的字串——不是一個空格，也不是符號 0，而是貨真價實的「什麼都沒有」。epsilon 對字串所扮演的角色，就像數字 0 對加法所扮演的：把它黏在任一字串的任一端，那個字串都原封不動。要小心初學者的經典陷阱——epsilon 是一個如假包換的字串，只是它是空的；把「沒有字串」和「那個空字串」搞混，往後會吃苦頭。
字串靠串接組合：直接把一個接在另一個後面，於是 01 與 10 串接就得到 0110。把一個字串重複 n 次就是它的次方，寫作 a^n，所以 a^3 表示 aaa，而 a^0 表示 epsilon。再往前推一步，把 Kleene 星號（克萊尼星號）套用到整個字母表上，得到 Σ（讀作「sigma-star」），它指的是你能用 Σ 拼出的「所有」字串所成的集合——涵蓋一切有限長度，包含 epsilon 在內。所以 [[sigma-star|Σ]] 就是我們一切活動所發生的那個宇宙。
從字串到語言
現在來看整門學科的核心定義。Σ 上的一個形式語言（或就叫「語言」）很單純，就是一個字串的「集合」——也就是你所挑選的 Σ* 的任一子集。這個語言可以是 {a, ab, abb}（有限的），可以是「所有含偶數個 1 的位元字串」（無限的），也可以是「所有語法正確的 Python 程式」。此刻還沒有附加任何文法或意義；一個語言純粹就是一堆字串的搜集，而正是這份樸素，讓它如此靈活。
有兩個語言看起來幾乎一模一樣，卻有著關鍵的不同，能分清它們算是一道成年禮。空語言，記作 ∅ 或 {}，裡頭「一個字串都沒有」——它就是空集合。而語言 {epsilon} 裡恰好「有一個」字串，也就是那個空字串。所以 ∅ 的大小是 0，{epsilon} 的大小卻是 1。打個比方：一個空盒子，對上一個裝著一個空袋子的盒子。它們不是同一個盒子。
因為語言就是集合，你可以用那些常見的運算再加上幾個帶字串味道的運算來組合它們：聯集 L1 ∪ L2 與交集 L1 ∩ L2，就跟對任何集合一樣；串接 L1·L2 則由「把 L1 的某個字串黏在 L2 的某個字串前面」所得到的每一個字串所組成；而 Kleene 星號 L*，則由「從 L 中取出零個或多個字串再串接起來」所得到的每一個字串所組成（注意，因為有「取零個字串」這一情況，L* 永遠含有 epsilon）。這些運算就是我們接下來整門課用來描述與建構語言的動詞。
那個大想法：一個問題「就是」一個語言
接下來這一步，把一切都統一起來了。隨便拿一個「是 / 否」問題——「這個數是質數嗎？」、「這張圖有沒有一條走遍每座城市的路徑？」、「這個程式語法正確嗎？」。首先，把每個輸入編碼成某字母表上的一個字串（數字寫成數位、圖寫成文字、程式寫成它的原始碼）。接著，把那些「答案為是」的字串恰好全部蒐集進同一個集合裡。這個集合就是一個語言，而它完整地刻畫了那個問題：解決這個問題，就等於判斷某個字串是否屬於這個語言。這就是把問題編碼成語言的想法。
這樣一講，每個「是 / 否」問題都變成了同一件差事：成員問題——給定一個字串 w，w 是否屬於語言 L？這也叫做 L 的判定問題。它聽起來簡單到不像話，但把千差萬別的問題全都改寫成「這個字串在不在這個集合裡？」，正是讓我們能用同一把尺去衡量它們的關鍵。當一台機器面對任何字串都能正確回答「在 / 不在」時，我們就說它「解決」了這個問題。
那張地圖：機器、語言，與喬姆斯基階層
隨著我們為機器逐步增添能力，它們所能判定的語言族，會排成一圈圈層層相套、整齊的階梯，這就是所謂的喬姆斯基階層。最底層坐著最簡單的模式；最頂層坐著真實電腦所能辨認的一切。每一階都「嚴格地」大於它下面那一階：外圈裡確實住著一些如假包換的語言，是任何較弱的機器都碰不到的。底下這張表勾勒出這趟攀登。
LANGUAGE FAMILY MACHINE EXAMPLE IT CAPTURES ----------------------- ---------------------------- ------------------------- regular finite automaton (DFA/NFA) even number of a's context-free pushdown automaton (PDA) matched brackets, a^n b^n recursively enumerable Turing machine any program's behavior nesting: regular ( context-free ( recursively enumerable ( all languages
第一階是 正規（regular）語言，由有限自動機辨認——想像一道旋轉柵門，或一台只記得自己「當前狀態」、沒有額外草稿紙的自動販賣機。我們會認識確定型有限自動機（DFA），替「偶數個 a」設計一台，並用幫浦引理證明它的硬性極限。先做一個要緊的誠實校正：「正規」並「不」等於「有限」——語言 a*（所有由 a 組成的字串，含 epsilon）是無限的，卻完完全全是正規的。正規談的是「模式的種類」，而不是字串的多寡。
往上爬一階，你來到 上下文無關（context-free）語言，由下推自動機辨認——一台有限機器，外加一疊盤子，但你只能碰最上面那一盤。光是這一疊堆疊，就讓它能計數並匹配巢狀結構，於是它能辨認成對的括號，或是上下文無關語言 a^n b^n（n 個 a 後面接 n 個 b），這是任何有限自動機都辦不到的。在最頂端住著遞迴可枚舉語言，由圖靈機辨認——想像一本無窮無盡、可以隨意讀取、擦除、重寫的筆記本。圖靈機是我們對「任何演算法」的代稱，而正是在這裡，我們會遇到像停機問題這樣、沒有任何機器能判定的問題。
從「能不能」走向「快不快」
一旦我們把「到底什麼能被計算」這張圖測繪完畢，階梯就轉向第二個問題：在那些我們「確實能」解的問題裡，哪些能被「快速」解出？這就是複雜度的主題，它依據「執行時間如何隨輸入大小成長」，把可判定的世界劃分開來。複雜度類 P 是那些能在多項式時間內解出之問題的家園——它大致就是「可有效率求解」的代稱。
環繞在 P 周圍的，是著名的複雜度類 NP，最好的比喻是一塊拼圖：要從零開始拼完也許極其折磨，但一旦有人把拼好的成品交到你手上，要驗證它對不對卻輕而易舉。從第一天就該帶在身上的三句誠實提醒：NP 並「不」代表「非多項式（not polynomial）」（它指的是「非確定型多項式時間」，而且事實上 P 裡的每個問題也都在 NP 裡，所以 P 是 NP 的子集）；P 是否等於 NP 是一個著名的「未解」問題，而非已成定論的事實；還有，就算是多項式時間的演算法，若指數大得驚人，實務上也可能毫無用處，因為大 O 界定的是最壞情況的成長速度，而非確切的執行時間。
把所有難題串在一起的工具，是歸約——一個翻譯員，把一個問題翻譯成另一個問題，使得只要能解開後者，就等於解開了前者。歸約讓我們能說出「這個問題至少和那個一樣難」，而完全不必真的找出對應的演算法。只要小心使用（而且只能用在正確的方向上——一個歸約只朝一個方向證明困難性，反過來不行），它們就能把成千上萬個頑固的問題，整理成一層層乾淨的等價階層。這就是這條階梯的終點站；而此刻，你已經握有了詞彙和地圖。下一篇導讀會把鏡頭重新拉近到字母表、符號與字串，把這些原子定義得更精確。