計算的本質、能力與極限
探討什麼可以被計算、計算需要多少資源、以及哪些問題是無法解決的
計算理論是電腦科學的理論基礎，涵蓋可計算性理論與複雜度理論，探討計算模型層次、停機問題、P vs NP 等核心議題。
艾倫·圖靈於 1936 年提出的抽象計算模型，由無限磁帶、讀寫頭和有限狀態控制器組成，定義了可計算性的數學意義。
最基本的計算模型，在有限數量的狀態間轉換，用於識別正則語言，廣泛應用於編譯器詞法分析、協定設計等領域。
描述語言語法的數學工具，喬姆斯基將文法分為四個層次（Chomsky 階層），每個層次對應不同的計算能力。
阿隆佐·丘奇發明的計算模型，從函數角度描述計算，是函數式編程的理論基礎，與圖靈機計算等價。
研究抽象計算機器的數學模型，從有限狀態機到圖靈機構成層次結構，與形式語言理論密切相關。
探討哪些問題本質上難以快速解決。包含 P 類、NP 類、NP-Complete 與 P vs NP 千年難題。
克勞德·夏農創立的數學學科，研究資訊的量化、儲存與傳輸，核心概念包括熵、交叉熵、KL 散度等。
以函數為主的程式設計範式，強調不可變性、第一類函數、高階函數，理論基礎源自 Lambda 演算。
二十世紀最重要的思想家之一，語言學家、認知科學家，提出轉換生成語法和 Chomsky 階層。
計算理論建立了不同層次的計算模型，從最強大的圖靈機到最簡單的正則語言，構成清晰的階層結構：
圖靈機 (Turing Machine) —— 最強大的計算模型
↓
λ 演算 (Lambda Calculus) —— 函數式計算的基礎
↓
上下文無關文法 (Context-Free Grammar) —— 程式語言語法理論
↓
正規語言 (Regular Language) —— 有限狀態機，詞法分析基礎