图灵机的计算 格局:带的内容,当前的状态和读写头扫视的方格 σ=aq,其中a,B∈r,q∈Q 初始格局σo=q0w,其中ν∈Σ是输入字符串 接受格局σ=aqB:q∈A 停机格局σ=qsβ:冽(q,s没有定义 1}σ2:从σ1经过一步能够到达a2,称a2是a1的后继 G1a2:从σ经过若干步能够到达28 格局: 带的内容, 当前的状态和读写头扫视的方格 σ = αqβ, 其中 α,βΓ* , qQ 初始格局σ0= q0w, 其中wΣ*是输入字符串 接受格局σ = αqβ : qA 停机格局σ = αqsβ : δ(q,s)没有定义 σ1 ⊢ σ2 : 从σ1经过一步能够到达σ2 , 称σ2是σ1的后继 σ1 σ2 : 从σ1经过若干步能够到达σ2 图灵机的计算