MoC:图灵机(Turing Machine,1936) STC 自动计算机的结构与行为(ABC) 一一条两端可以无限延伸的纸带 一个读写头（符号包括0、1、b) 01( 一个控制器（执行控制读写头工作的命令） 五元组：（状态、读符号）→（写符号、移动、状态） -状态集：开始状态，中间状态，结束状态 当进入结束状态时，停机(H) 六个操作原语(primitives):读、写、左、右、擦除、停止 控制命令示例： 00011101111100 qi01Rq 控制器 q10Rq q bbRq2 q2bbLq3 初始状态 中间状态 结束状态 q200Hq1 q211Hq1MoC：图灵机(Turing Machine,1936) • 自动计算机的结构与行为（ABC） – 一条两端可以无限延伸的纸带 – 一个读写头（符号包括0、1、b） – 一个控制器（执行控制读写头工作的命令） • 五元组：（状态、读符号）→（写符号、移动、状态） – 状态集：开始状态，中间状态，结束状态 – 当进入结束状态时，停机(H) – 六个操作原语（primitives）：读、写、左、右、擦除、停止 0 0 0 1 1 1 0 1 1 1 1 1 0 0 控制器 q101Rq1 q110Rq1 q1bbRq2 q2bbLq3 q200Hq1 q211Hq1 控制命令示例：