【计算理论】图灵机 ( 图灵机示例 )

文章目录

• 一、图灵机示例
• 二、图灵机示例 2

一、图灵机示例

指令

初始状态下 , 状态是

读取头 指向的字符是

, 如下图 :

执行完

指令之后 ,

状态变为

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

擦除 , 改为

, 向左移动一个单位 ( 这里不进行移动 ) ;

左端点向左移动默认不动说明 :

一般情况下我们计算时涉及的图灵机都是 向右无限延长的带子 , 带子有一个左端点 ;

当读写头当前已经指向左端点时 , 如果再向左移动 , 此时默认不进行移动 ;

二、图灵机示例 2

任务 : 设计一个图灵机 , 给定输入之后 , 图灵机会 在输入中寻找

字符 ;

算法 :

如果 找到了

字符 , 就会将该字符转变成

字符 , 然后将当前状态改为接受状态

, 然后停下来 ;

如果带子上的字符都读取完毕后 , 没有找到

, 只找到了空白字符 , 将该空白字符改为

, 然后向左移动一格 , 然后停下来 ;

( 自动机停下的前提是处于可接受状态 )

根据上述算法 , 构造图灵机 ;

图灵机设计 :

① 状态集

, 其中

是开始状态 ,

是接受状态 ;

② 输入字符集

;

③ 带子字符集

, 其中

是空白字符 ;

④ 指令

⑤ 指令

⑥ 指令

上述图灵机设计中 , 最关键的部分是三条指令 ;

图灵机处于开始状态

, 读头指向

字符 , 左端的

是输入字符 , 查看图灵机是否接受

字符串 ;

下面图灵机后续都是

空白字符 ;

根据指令 指令

, 当前状态

, 当前指向字符

, 输出内容是

,

即 状态变为

, 读头指向的字符变为

, 向右移动一个字符 ;

如下图 :

此时继续 根据指令 指令

, 当前状态

, 当前指向字符

, 输出内容是

,

即 状态变为

, 读头指向的字符变为

, 向右移动一个字符 ;

如下图 :

此时继续 根据指令 指令

, 当前状态

, 当前指向字符

, 输出内容是

,

即 状态变为

, 读头指向的字符变为

, 向左移动一个字符 ;

如下图 :

此时继续 根据指令 指令

, 当前状态

, 当前指向字符

, 输出内容是

,

即 状态变为

, 读头指向的字符变为

, 向右移动一个字符 ;

如下图 :

此时继续 根据指令 指令

, 当前状态

, 当前指向字符

, 输出内容是

,

即 状态变为

, 读头指向的字符变为

, 向右移动一个字符 ;

此时的状态

是接受状态 , 自动机停止运行 ;

如下图 :

图灵机 与 自动机 接受的条件是不同的 ;

图灵机计算过程中 , 一旦到达接受状态 , 立刻停机 , 不再继续进行计算 ; 并且称该图灵机是可接受的 ;

自动机即使到达接受状态 , 也要把自动机读取的字符读取完毕 , 才停止计算 ; 然后在查看最终的状态是否是接受状态 ;