简介和定义

理解

  1. 图灵机有一个有穷控制器,一条两端无穷的输入输出带和一个带头
  2. 带划分单元格,每个单元格可放置一个符号
  3. 带头根据当前状态和带头所处的单元格的符号内容,根据转移规则选择下一个动作
  4. 每个动作都包含一个状态,修改带头出单元格的符号以及带头向左或者向右移动一个单元格

定义

Untitled