文章目录

• 一、设计图灵机要求
• 二、图灵机分析
• 三、计算过程分析
• 四、高级语言
• 五、使用高级语言描述图灵机
• 六、完整图灵机 ( 仅做参考 )

一、设计图灵机要求

设计一个图灵机

, 认识一种特定语言 , 该语言由

组成 , 字符串的长度是

个 ,

;

二、图灵机分析

分析 : 设计一个图灵机 , 图灵机所接受的语言是 :

个

组成的字符串 ,

个

组成的字符串 ,

个

组成的字符串 ,

个

组成的字符串 ,

个

组成的字符串 ;

图灵机设计很复杂 , 一般不需要设计出完整图灵机 , 只需要写出设计过程即可 ;

三、计算过程分析

将字符串写到带子上 , 带子上每隔一个

划掉一个 , 数一下剩下的

:

① 如果剩下的

是

个 , 直接接受该字符串 ;

② 如果剩下的

是 奇数个 , 直接拒绝接受该字符串 ;

③ 如果剩下的

是 偶数个 , 继续重新开始循环 ;

四、高级语言

将上述算法写成 高级语言 , 用于描述图灵机的计算过程 ;

高级语言是有要求的 , 其与图灵机的不同 ,

图灵机需要将所有的指令都写出来 , 状态图要绘制出来 , 这个要求很难实现 ;

高级语言不用将图灵机画出来 , 只需要 描述读写头如何操作 即可 , 将指令集部分直观描述出来 , 不写出具体的指令 ;

五、使用高级语言描述图灵机

下面就是高级语言的直观的计算过程 ;

图灵机直观计算过程 : 假设图灵机的带子上放了

字符串 ;

阶段一 : 从左到右扫描图灵机带子 , 每隔

个

划掉一个 ;

阶段二 : 如果在 “阶段一” 只包含

个

, 那么 接受该字符串 ;

阶段三 : 如果在 “阶段一” 包含的

的个数大于

, 并且

的个数是奇数 , 那么 拒绝该字符串 ;

阶段四 : 如果在 “阶段一” 包含的

的个数大于

, 并且

的个数是偶数 , 那么 返回带子最左端 ;

阶段五 : 从 “阶段一” 重新开始计算 ;

六、完整图灵机 ( 仅做参考 )

设计的真实的

图灵机的指令如下 : 如下状态的图灵机设计很复杂 , 不做要求 ;