整理自书本1。 图灵机是一个7元组，(Q, ∑ \sum ∑, Γ \varGamma Γ, δ \delta δ, q 0 q_0 q0, q a c c e p t q_{accept} qaccept, q r e j e c t q_{reject} qreject)，其中Q， ∑ \sum ∑， Γ \varGamma Γ都是有限集并且满足一下七个条件：
Q是状态集合， ∑ \sum ∑是输入字母表，且不含包空符号（blank symbol） ⊔ \sqcup ⊔， Γ \varGamma Γ是磁带的字母表，且 ⊔ ∈ Γ , ∑ ⊂ Γ \sqcup\in{\varGamma},\sum\subset{\varGamma} ⊔∈Γ,∑⊂Γ， δ : Q × Γ → Q × Γ × { L , R } \delta:Q\times{\varGamma}\rarr{Q\times{\varGamma\times{\{L,R\}}}} δ:Q×Γ→Q×Γ×{L,R}是转换函数， q 0 ∈ Q q_0\in{Q} q0∈Q是开始状态， q a c c e p t ∈ Q q_{accept}\in{Q} qaccept∈Q是接收状态， q r e j e c t ∈ Q q_{reject}\in{Q} qreject∈Q是拒绝状态，且 q r e j e c t ̸ = q a c c e p t q_{reject}\not =q_{accept} qreject̸=qaccept。图灵机的当前状态、当前的磁带内容、读头所在位置构成了图灵机的配置。
Introduction to the Theory of Computation ( 3rd edition ) Michael Sipser. p143 ↩︎
