【计算理论】图灵机 ( 图灵机图示 | 图灵机形式定义 )

文章目录

• 一、图灵机图示
• 二、图灵机形式定义

一、图灵机图示

下图是图灵机的简单示意图 : 图灵机由 无穷长的带子 , 读头 , 状态 组成 ;

带子 :

无穷长度 , 每个格子有一个字符 ;

读头 :

上图中的箭头是读头 , 用于读写数据 ;

读头作用是 读取带子上的字符 , 然后擦掉该字符 , 写入新的字符 ;

然后该读头可以 向左或向右移动一格单位 ;

状态 :

箭头上的矩形框中表示当前的状态 , 状态个数是有限多个 , 其作用是指挥图灵机如何进行计算 ;

上述图灵机是理想的图灵机 , 带子是无穷长的 , 带子上的字符是有限多个 , 状态是有限多个 , 指令也是有限多个 ;

二、图灵机形式定义

图灵机要素 :

① 有限多状态集 ,

;

② 有限多个字符集 ,

;

③ 带子字符集 ,

, 包含

;

④ 转换函数 , 即指令集 ,

;

⑤ 开始状态 ,

, 包含在

中 ;

⑥ 空白字符 ,

, 包含在

( 相对补集 ) 集合中 ;

⑦ 一些接受状态 ,

, 其中

;

指令与转换函数 : 图灵机是根据指令进行计算的 , 指令 是一个 转换函数

;

转换函数

两个输入参数 :

• 参数一 : 状态

, 该状态是

中的元素 ,

;

• 参数二 : 带子字符

, 该字符是

集合中的元素 ,

;

转换函数

输出是一个三元组 :

• 输出一 : 状态

;

• 输出二 : 带子字符

;

• 输出三 : 方向

, 向左或向右 , 读取头下面要移动的方向 ;

指令

表示的含义解析 :

转换函数 , 其中

是两个输入 ,

是三个输出 ,

开始时图灵机的 状态是

状态 , 读取头指向的字符是

,

执行该转换函数

, 会将 状态转变为

状态 , 将 读取头指向的带子上的字符

擦除 , 并改为

, 然后 沿着

方向 , 移动一格单位 ;

其中

方向可以是

向左移动 , 也可以是

向右移动 ;