1513图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号,图灵机的一 个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头,向左移动一个方格(L或向右移动一个 方格(R)或停在当前单元不动(S)。 k带图灵机可邢式化地描述为一个7元组(Q,T,I,S,b,q,q,其中 (1)Q是有限个状态的集合。(2)T是有限个带符号的集合 (3)I是输入符号的集合,IT。(4)b是唯一的空白符,b∈T-I (5)q是初始状态。 (6)q是终止(或接受)状态。 (7)6是移动函数。它是从QxT的某一子集映射到Q×(T×{L,R,S})的函数8 15.1.3 图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一 个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个 方格(R)或停在当前单元不动(S)。 k带图灵机可形式化地描述为一个7元组(Q，T，I，δ，b，q0，qf )，其中: (1)Q是有限个状态的集合。 (2)T是有限个带符号的集合。 (3)I是输入符号的集合，IT。(4)b是唯一的空白符，b∈T-I。 (5)q0是初始状态。 (6)qf是终止(或接受)状态。 (7)δ是移动函数。它是从QTk的某一子集映射到Q (T{L，R，S})k的函数