图灵机概述 基本图灵机纸带[aa2…|a1…anbb T=(Q,r,b,Σ,q0,F,δ) 读写头 Q:有穷非空的状态集 有限 I:有穷非空的带符号集 控制器 b∈r:空白符号 ∑cI{b}:输入符号集 q0∈Q:开始状态 FcQ:终止状态集 δ:(QF×)→Qxr×{,R:迁移函数,L和R表 示读写头的左右移 例如:8(q0,0)-(q1,X,R,δ(q1,1)->(q2,Y,L)0图 灵 机 概 述 • 基本图灵机 T= Q, , b, , q0 , F,   – Q: 有穷非空的状态集 – : 有穷非空的带符号集 – b: 空白符号 –  \{b}: 输入符号集 – q0Q: 开始状态 – FQ: 终止状态集 –  :(Q\F  ) → Q    {L, R}: 迁移函数， L和R表 示读写头的左右移 例如： (q0 , 0)→(q1 , X, R),  (q1 , 1)→(q2 , Y, L) a1 a2 … ai … an b b … 有限 控制器 纸带 读写头 10