定义6-2图灵机的格局D (∑)Q(∑) w是读/写头左边带上的符号串 q是图灵机当前所处的状态 w2是读/写头右边的带上的符号串
定义6-2 图灵机的格局ID w1qw2∈ w1是读/写头左边带上的符号串 q是图灵机当前所处的状态 w2是读/写头右边的带上的符号串 (∑′)*Q(∑′)*
δ(q,x) 图灵机在格局w1qw2时停机 若w1qW2=w1qXW3对于？无定义
l图灵机在格局w1qw2时停机 若w1qw2 =w1qxw3对于 无定义。 δ(q，x) ?
定义6-3格局的转换 若M在w1qw2上不停机，则如下定义 格局的转换 ·某个时刻，图灵机处于格局 WiqW2-r1yqxr2, 其中： r1y=w1,(若W=E,则y=B, r1=8) Xr2=W2, (若V2=8,则r2=8,X=B)
定义6-3 格局的转换 l 若M在w1qw2上不停机，则如下定义 格局的转换： l 某 个 时 刻 ， 图 灵 机 处 于 格 局 w1qw2 =r1yqxr2，其中： r1y=w1，(若w1 =ε，则y=B， r1 =ε) xr2 =w2， (若w2 =ε，则r2 =ε，x=B )
使用=>表示图灵机的格局转换 若δ(q,x)=(q',x',L),则 ryqxr=> r q'yxr2 若δ(q,X)=(q',x',N), 则 ryqxr=> r yq'x'r2 ●若δ（q,X)=(q',x',R), 则 ryqxr2=> ryxqr2
使用 => 表示图灵机的格局转换 l 若δ（q，x）=( q′ ，x′ ，L)，则 r1yqxr2 => l 若δ（q，x）=( q′ ，x′ ，N)，则 r1yqxr2 => l 若δ（q，x）=( q′ ，x′ ，R)，则 r1yqxr2 => r1q′yx′r2 r1yq′x′r2 r1y x′q′r2
使用=〉+代表格局的多次变换 使用=>*代表格局的任意次变换
使用=>+代表格局的多次变换 使用=>*代表格局的任意次变换