通用計算模型，可計算性的數學定義
圖靈機是艾倫·圖靈（Alan Turing）在 1936 年提出的抽象計算模型，被認為是電腦科學的理論基石。圖靈機不僅解決了判定問題，也定義了「可計算性」的數學意義，是所有現代電腦的理論原型。圖靈在論文《論可計算數及其在判定問題中的應用》中提出了圖靈機模型，並證明了不存在一個演算法可以判定任意數學命題的真假——這就是著名的停機問題。
圖靈機是一個七元組 M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)：
| 符號 | 意義 |
|---|---|
| Q | 有限的非空狀態集合 |
| Σ | 輸入字母表（不含空白符號） |
| Γ | 磁帶字母表（包含 Σ 和空白符號 □） |
| δ | 轉移函數 Q × Γ → Q × Γ × {L, R} |
| q₀ | 起始狀態，q₀ ∈ Q |
| q_accept | 接受狀態 |
| q_reject | 拒絕狀態 |
┌─────────────────────────────────────────────────────────────┐ │ 圖靈機結構 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────┐ ┌─────────┐ ┌─────────────────────────┐ │ │ │ 狀態寄存器 │───▶│ 轉移函數 │───▶│ 無限磁帶 │ │ │ └─────────┘ └─────────┘ │ ┌───┬───┬───┬───┬───┐ │ │ │ │ │ □ │ a │ b │ c │ □ │ │ │ │ │ └───┴───┴───┴───┴───┘ │ │ │ │ ↑ │ │ │ │ 讀寫頭 │ │ │ └─────────────────────────┘ │ └─────────────────────────────────────────────────────────────┘
| 特性 | 有限狀態機 (FSM) | 圖靈機 |
|---|---|---|
| 磁帶 | 無 | 無限 |
| 寫入能力 | 否 | 是 |
| 移動方向 | 只能前進 | 左/右 |
| 記憶能力 | 有限狀態 | 無限（磁帶） |
| 計算能力 | 正規語言 | 任何可計算問題 |
圖靈機比有限狀態機更強大之處在於：它可以寫入和修改磁帶，這使其具有了真正的「記憶能力」，能夠解決有限狀態機無法解決的問題，如識別語言 {aⁿbⁿ | n ≥ 1}。
停機問題是計算機科學中最重要的不可判定問題。它詢問：是否存在一個圖靈機 H，能夠判斷任意圖靈機 M 在任意輸入 w 上是否會停止？
證明使用反證法。假設存在這樣的 H，構造悖論機器 P：
構造 P 如下：
當輸入是 <P> 時：
如果 H(<P>, <P>) 說「會停機」
则进入无限循环
否則
停止
如果 H 說 P(P) 會停機，則 P 會進入無限迴圈；如果 H 說 P(P) 不會停機，則 P 會停止。無論哪種情況都產生矛盾。因此，這樣的 H 不可能存在。這意味著存在無法用演算法解決的問題，電腦有本質上的限制。
Church-Turing 論點是計算理論中最基本的假設：任何可有效計算的函數都可以由圖靈機計算。這不是一個定理，而是一個「論點」，因為「可有效計算」這個概念本身並非數學定義。論點得到以下支持：圖靈機可以模擬任何已知的計算模型；所有提出用於描述「可計算性」的數學模型都被證明與圖靈機等價；沒有任何已知的計算問題是圖靈機無法解決但其他模型可以解決的。