文章目录
一、图灵机图示
二、图灵机形式定义
一、图灵机图示
----
下图是图灵机的简单示意图 : 图灵机由 无穷长的带子 , 读头 , 状态 组成 ;
带子 :
无穷长度 , 每个格子有一个字符...读头作用是 读取带子上的字符 , 然后擦掉该字符 , 写入新的字符 ;
然后该读头可以 向左或向右移动一格单位 ;
状态 :
箭头上的矩形框中表示当前的状态 , 状态个数是有限多个 , 其作用是指挥图灵机如何进行计算...;
上述图灵机是理想的图灵机 , 带子是无穷长的 , 带子上的字符是有限多个 , 状态是有限多个 , 指令也是有限多个 ;
二、图灵机形式定义
----
图灵机要素 :
① 有限多状态集 ,
\rm..., 包含在
\rm \Gamma - \Sigma
( 相对补集 ) 集合中 ;
⑦ 一些接受状态 ,
\rm F
, 其中
\rm F \subseteq Q
;
指令与转换函数 : 图灵机是根据指令进行计算的...delta
表示的含义解析 :
\rm \delta(q, Z) = (p, Y, D)
转换函数 , 其中
\rm q,Z
是两个输入 ,
\rm p, Y, D
是三个输出 ,
开始时图灵机的