【计算理论】图灵机 ( 多个带子的图灵机 | 计算能力对比 | 证明过程 | 一个带子图灵机 )

文章目录

一、多个带子的图灵机

二、证明过程设计

三、模仿操作

四、模仿带子排列

五、模仿读写头操作

一、多个带子的图灵机

多个带子的图灵机 指的是 图灵机不止一个带子 , 下图是 3 33 个带子的图灵机 , 每条带子有一个对应的读写头 , 总共有 3 33 个读写头 , 有 一个状态 , 该状态根据指令进行操作 ;

3 33 个带子的图灵机当前所处的状态是 q \rm qq , 三个读头所处的位置分别是 1 , a , b \rm 1 , a , b1,a,b , 三个带子的图灵机根据指令进行操作 ,

首先将所处的 状态从 q \rm qq 转换成 p \rm pp 状态 ,

三个读写头指向的字符需要 同时被擦掉 , 并写入新字符 , 其操作看起来相当于三个图灵机同时进行工作 , 有一种错觉就是三个带子的图灵机的计算能力要超过一个带子的图灵机 ;

事实上 , 三个带子的图灵机的计算能力 , 等同于 一个带子的图灵机的计算能力 ;

二、证明过程设计

证明过程 :

三个带子的图灵机 , 如果其中两个带子不工作 , 等同于一个带子的图灵机 , 因此 三个带子的图灵机的计算能力 大于等于 一个带子的图灵机的计算能力 ;

然后证明 三个带子的图灵机的计算能力 不会超过 ( 小于等于 ) 一个带子的图灵机的计算能力 ;

最终得到 三个带子的图灵机的计算能力 等同于 一个带子的图灵机的计算能力 ;

三、模仿操作

给定一个 三个带子的图灵机 , 一定能找到一个 一个带子的图灵机 , 可以模仿作出三个带子图灵机相同的计算任务 ;

相同的计算任务的含义就是 两个 图灵机 接受的语言是相同的 ;

使用 一个带子图灵机 模仿 三个带子图灵机 ;

设计 单个带子图灵机 指令集 , 模仿 三个带子图灵机 计算过程 ;

四、模仿带子排列

带子的字符排列 :

三个带子图灵机 一步计算中 , 修改了一次状态 , 同时读写头修改了 3 33 次字符 ;

一个带子图灵机 模仿 三个带子图灵机 上述 一步计算 , 在一个带子图灵机中 , 引入特殊字符 # ,

第 1 11 个 # 与第 2 22 个 # 之间的内容是 第 1 11 个带子的内容 ,

第 2 22 个 # 与第 3 33 个 # 之间的内容是 第 2 22 个带子的内容 ,

第 3 33 个 # 与第 4 44 个 # 之间的内容是 第 3 33 个带子的内容 ;

上述 1 11 个带子 可以模仿 3 33 个带子的内容 ;

特殊字符 # 之间的空间很大 , 可能间隔十几个到几十个字符 , 依次排列即可 ;

排列顺序如下 : # 第 1 11 个带子的字符串 # 第 2 22 个带子的字符串 # 第 3 33 个带子的字符串 #

五、模仿读写头操作

读写头操作 :

1 11 个读写头 模仿 3 33 个读写头 操作 :

1 11 个读写头 读写了 第 1 11 个带子的字符串 ,

其并不知道第 2 22 个读写头的位置 , 根据字符 a \rm aa 是不能区分当前的读写头位置 , 第 2 22 个带子的字符串 中有多个 a \rm aa 字符 ;

在字符集中 引入 特殊字符 , 如下图中 第 1 11 个带子的字符串换中 红色的 1 11 与 黑色的 1 11 是不同的字符 , 这两个颜色 1 11 有公共的部分 , 在指令集中 , 这两个 1 11 所起的作用是一样的 ;

红色的 1 11 标志的是读写头所在的位置 , 使用红色表示当前读写头的位置信息 ;

上图中红色的 1 11 指的是第一个读写头指向的字符 , 读写完毕后 , 继续向右走 , 走到第二个读写头指向的红色的 a \rm aa 位置 , 然后以此类推 ;

靠不同的字体颜色 区分出 不同的带子 对应的 读写头指向的字符 , 这样就可以实现 1 11 个带子模拟多个带子的图灵机 ;

使用 1 11 个带子的图灵机 模拟 3 33 个带子的图灵机 的代价是 读写头必须从左向右整个遍历一遍带子 , 才能模拟 3 33 个带子的图灵机 一步的计算 ;