文章目录

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

一、设计图灵机要求

设计一个图灵机 M2\rm M2M2 , 认识一种特定语言 , 该语言由 000 组成 , 字符串的长度是 2n\rm 2^n2n 个 , n=0,1,2,⋯\rm n = 0, 1, 2, \cdotsn=0,1,2,⋯ ;

二、图灵机分析

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

222 个 000 组成的字符串 ,

444 个 000 组成的字符串 ,

888 个 000 组成的字符串 ,

161616 个 000 组成的字符串 ,

⋮\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots⋮

2n\rm 2^n2n 个 000 组成的字符串 ;

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

三、计算过程分析

将字符串写到带子上 , 带子上每隔一个 000 划掉一个 , 数一下剩下的 000 :

① 如果剩下的 000 是 111 个 , 直接接受该字符串 ;

② 如果剩下的 000 是 奇数个 , 直接拒绝接受该字符串 ;

③ 如果剩下的 000 是 偶数个 , 继续重新开始循环 ;

四、高级语言

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

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

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

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

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

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

图灵机直观计算过程 :假设图灵机的带子上放了 000000000000 字符串 ;

阶段一 :从左到右扫描图灵机带子 , 每隔 111 个 000 划掉一个 ;

阶段二 :如果在 “阶段一” 只包含 111 个 000 , 那么 接受该字符串 ;

阶段三 :如果在 “阶段一” 包含的 000 的个数大于 111 , 并且 000 的个数是奇数 , 那么 拒绝该字符串 ;

阶段四 :如果在 “阶段一” 包含的 000 的个数大于 111 , 并且 000 的个数是偶数 , 那么 返回带子最左端 ;

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

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

设计的真实的 M2\rm M2M2 图灵机的指令如下 :如下状态的图灵机设计很复杂 , 不做要求 ;