λ 演算（lambda calculus）
/ lambda -> LAM-duh /
暫且忘掉紙帶、狀態與機器。想像計算完全由函數構成——函數就是接收輸入、回傳結果的東西——而且別無他物：沒有數字、沒有記憶格，只有函數接收函數、回傳函數。聽起來簡樸得不可思議，卻足以表達任何計算。λ 演算（lambda calculus）由阿隆佐·邱奇於 1930 年代發明，正是如此：一個極小的語言，其全部材料只有變數、製造函數的方法，以及把一個函數套用到另一個函數上的方法。
運算式只有三種形式。變數，例如 x。抽象（lambda x. M），讀作「接收 x 並回傳 M 的那個函數」，這是你建構函數的方式。以及套用（M N），讀作「把函數 M 套用到引數 N 上」。計算只有一條改寫規則，叫 β 歸約（beta reduction）：要計算 ((lambda x. M) N)，就把 M 中的每個 x 都代換成 N。例如 (lambda x. x) 套用到 y 會歸約成 y，所以 (lambda x. x) 是恆等函數。令人驚訝的是，你可以把數字編碼成函數（邱奇數 Church numerals：0 是 lambda f. lambda x. x，1 是 lambda f. lambda x. f x，n 把 f 套用 n 次），再由此編碼出加法、乘法、布林值、序對與遞迴，全都是純函數。
λ 演算之所以重要有兩個理由。其一，它計算的恰好就是圖靈可計算的函數，不多也不少，儘管它根本沒有紙帶、步數計數器或當前狀態的概念。它與圖靈模型的這種獨立匯聚，是邱奇-圖靈論題證據的基石。其二，它是函數式程式設計的理論種子：Lisp、Haskell，以及如今幾乎每種現代語言裡的 lambda，都直接源自它。誠實的提醒是：「能力等價」不等於「方便」，純粹的 λ 演算寫起程式來低階得令人痛苦，就像一台赤裸的圖靈機一樣。
定義 TRUE = lambda x. lambda y. x 與 FALSE = lambda x. lambda y. y。那麼「if」就只是套用：(TRUE a b) 歸約成 a，(FALSE a b) 歸約成 b。布林值——通常是個基本型別——結果只不過是「從兩個引數中挑一個」的函數罷了。
在 λ 演算中，連真與假都是函數；一切都由純粹的抽象與套用建構而成。
λ 演算在計算能力上與圖靈機相等，並非更強。它沒有紙帶或狀態並不使它變弱；這種匯聚正是重點所在。