計算理論（theory of computation）

想像你想知道的不只是某一台電腦能不能解決某個問題，而是「任何機器、無論多快、記憶體多大」究竟能不能解決它。計算理論就是電腦科學中提出這類問題的部分。它從真實的筆電與手機後退一步，不管晶片廠牌、不管程式語言，把計算當成一個純粹的概念來研究：給定一個問題，它到底能不能被解決？若能，任何解法又必須花多少時間或記憶體？

為了讓這件事精確，這門理論做了一件聰明、起初甚至令人驚訝的事：它把每個問題都看成關於「符號字串」的問句。計算的輸入被寫成一個字串（像 1011 或 aabba），而一個問題就變成「判斷哪些字串屬於某個特別集合（稱為語言）」這項工作。機器接著對每個字串選擇接受或拒絕。藉由挑選簡單、理想化的機器（有限自動機、下推自動機、圖靈機），我們就能精確地證明每種機器能與不能識別什麼。因為機器是抽象的，這些證明對所有時代、所有硬體都成立。

三大主題貫穿整門學科。自動機與語言依「能識別它的最簡單機器」來分類問題；可計算性問「哪些問題根本能被任何機器解決」（有些問題，例如停機問題，已被證明無法解決）；複雜度則問「在可解的問題裡，哪些能被有效率地解決」。誠實的重點是：這門理論不會讓你的程式跑得更快，而是告訴你硬牆在哪裡，免得你白費一生去爬一道數學早已證明爬不過去的牆。