チューリングマシン
字母から空白文字を除いた Γ − {b} の部分集合 Σ を入力字母(input alphabet)といい、入力字母の元を入力記号(input symbol)という。
写像 δ: Q × Γ → Q × Γ × {left, right} を遷移函数という。δ(q, a) = (q′, a′, m) は、「現在の状態が q であり、着目位置の記号が a であれば、状態を q′ に移し、着目位置に記号 a′ を書き込んでから、着目位置を m ∈ {left, right} 方向に1つずらす」と読む。