定义4.4一个确定性单带图灵机由下列集和函数构成 1.1)带中所用字符集B,通常可设B=01x},其中4表示空 2)读写头所处的可能状态集S,其中包含一个初始状态 和若干个停机状态 3)读写头所处状态的转移函数,它是读写头现在所处状 态s和所读字符b的函数,表示为 4)读写头动作的指令函数,它也彩头现在所处状态s 和所读字符b的函数,表示沟 其中 且都不属于B。若 k:×-以写字符张替b, 且保持原位不动。s,b)=b∈B,则原字符b保持不变 读写头向左(或向右)移s,b))方格。 2.磁带上的每个小方格用一个整数坐标表示。小方格i中的字 符记作t(),磁带表示为函数 t:Z(整数集)→B• 定义 4.4 一个确定性单带图灵机由下列集和函数构成。 1. 1）带中所用字符集B，通常可设 ，其中 表示空。 2）读写头所处的可能状态集S，其中包含一个初始状态 和若干个停机状态 。 3）读写头所处状态的转移函数 ，它是读写头现在所处状 态s和所读字符b的函数，表示为 。 4）读写头动作的指令函数 ，它也是读写头现在所处状态s 和所读字符b的函数，表示为 ，其中 且都不属于B。若 ，则读写头写字符 代替b， 且保持原位不动。若 ，则原字符b保持不变， 读写头向左（或向右）移动一个小方格。 2. 磁带上的每个小方格用一个整数坐标i表示。小方格i中的字 符记作t(i)，磁带表示为函数 。 B = 0,1,  0 s T  S   : S B →S   : S  B → Bl,r l  r s b = b  B ' ( , ) ' b (s,b) = l(或r) t : Z(整数集）→ B