3.图灵机在某一时刻的形是指一个三元组(S,t,i),它们 别表西该时刻读写头所处状态,磁带和读写头所扫描的 4.一个图灵机的计算程序(算法)是一个形的有限或无限 序列(s,ti)(s1,,i)(s2l2l2)…, 其中(s,,)图灵机在初 始时刻的形,即S为初始状态,为初始磁带,它由输入 数据(字)x∈B给出,通常存放在1-小方格中,其 它小方格中为空字符λ,通常i=1。图灵机在k时刻的 形(.)k=12…由下面的递推式给出 若以(S121k1(1)=b∈B则;=i1 SI =o(s k-11k-1(k-1 (i= (4.3) 若(S1,k1(ik1)=l则t4=k1,bk=ik1-1 若4(S1,t1=1(i=1)=r则tk=tk-1,ib=i 若存在形(sk,)使Sk∈T,则计算在时刻K=m(k,sk∈7) 终止,同时停机,称()或()为计算的输出结果,K 为图灵机(算法)的运行(计算)时间。否则计算将 )不停机,直到无限。3. 图灵机在某一时刻的形是指一个三元组 ，它们分 别表示该时刻读写头所处状态，磁带和读写头所扫描的 小方格坐标，t(i)为读写头在该时刻所读字符。 4. 一个图灵机的计算程序（算法）是一个形的有限或无限 序列 ，其中 为图灵机在初 始时刻的形，即 为初始状态，为初始磁带，它由输入 数据（字） 给出，通常存放在 小方格中，其 它小方格中为空字符 ，通常 。图灵机在k时刻的 形 由下面的递推式给出。 若存在形 使 ，则计算在时刻 终止，同时停机，称 或 为计算的输出结果，K 称为图灵机（算法）的运行（计算）时间。否则计算将 不终止，不停机，直到无限。 (s,t,i) (s0 ,t 0 ,i 0 ),(s1 ,t 1 ,i 1 ),(s2 ,t 2 ,i 2 ), ( , , ) 0 0 0 s t i 0 s 0 t * x  B 1− x  i 0 = 1 (sk ,t k ,i k ), k =1,2,  ( , ( )) k = k−1 k−1 k−1 s  s t i         = = = + = = = −     = = =  = − − − − − − − − − − − − − − − − − ( , ( )) , 1 ( , ( )) , 1 (4.3) ( ) ( ) ( , ( )) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 k k k k k k k k k k k k k k k k k k k k k k k s t i r t t i i s t i l t t i i t i i i b i i t i s t i b B i i 若 则 若 则 若 则    ( , , ) k k k s t i sk T K min( k;s T) = k  ( , ) k k t i ( ) k k t i