一、两个带子的图灵机的时间复杂度

讨论两个带子的图灵机的时间复杂度 ;

计算问题如下 :

给定语言 : $\mathrm{A}=\{0^{\mathrm{k}}{1}^{\mathrm{k}}:\mathrm{k}\ge 0\}$

构造 两个带子的 图灵机 ${\mathrm{M}}_3$ 认识上述语言 ;

算法分析过程 : 假设字符串为 $000111$ , 最坏的情况 ;

开始时的状态 : 第一个带子是 $000111$ 输入字符 , 第二个带子是空的 ;

第一步 : 读头一 读取 带子一 字符 $0$ , 读头二 将 $0$ 字符写入到 带子二 中 ;

第二步 : 读头一 读取 带子一 字符 $0$ , 读头二 将 $0$ 字符写入到 带子二 中 ;

第三步 : 读头一 读取 带子一 字符 $0$ , 读头二 将 $0$ 字符写入到 带子二 中 ;

第四步 : 读头一 读取 带子一 字符 $1$ , 读头二 将 $0$ 字符从当前带子中抹掉 ;

第五步 : 读头一 读取 带子一 字符 $1$ , 读头二 将 $0$ 字符从当前带子中抹掉 ;

第六步 : 读头一 读取 带子一 字符 $1$ , 读头二 将 $0$ 字符从当前带子中抹掉 ; 此时带子一读取完毕 , 带子二为空 , 此时进入接受状态 ;

${\mathrm{M}}_3$ 是两个带子的图灵机 , 算法设计如下 :

${\mathrm{M}}_3=$ " 在输入字符串 $\mathrm{w}$ 上进行如下计算 :

① 扫描整个带子上的字符串 , 查看 $0$ 和 $1$ 的顺序 , 所有的 $0$ 必须在所有的 $1$ 前面 ; 如果顺序错误 , 进入 拒绝状态 ;

② 扫描 带子一 上的 $0$ 字符 , 直到遇到 $1$ 字符 , 同时将 $0$ 拷贝到 带子二 中 ;

③ 扫描 带子一 上的 $1$ 字符 , 直到字符串结束 , 每读取一个 $1$ 字符 , 就删除 带子二 中的 $0$ 字符 ;

④ 如果所有的 $0$ 字符都被删除 , 带子一 中的 $1$ 字符还没有读取完毕 , 进入 拒绝状态 ; 如果 带子一 中的字符读取完毕 , 带子二 中还有 $0$ 字符剩余 , 进入 拒绝状态 ; 如果 带子二 中的 $0$ 字符都被删除 , 带子一 正好读取完毕 , 进入 接受状态 ; "

计算上述算法的时间复杂度 :

首先检查 $01$ 的相对顺序 , 最坏的情况下是读头走 $\mathrm{n}$ 步 , 其复杂度是 $\mathrm{O}(\mathrm{n})$ ;

然后读取带子一 然后写入擦除带子二 操作 , 整体执行了 $\mathrm{n}$ 步 , 的时间复杂度是 $\mathrm{O}(\mathrm{n})$

上述两个步骤的时间复杂度是 : $\mathrm{O}(\mathrm{n})+\mathrm{O}(\mathrm{n})=\mathrm{O}(\mathrm{n})$

在 【计算理论】计算复杂性 ( 小 O 记号 | 严格渐进上界 | 分析算法的时间复杂度 ) 博客中 , 使用一个带子的图灵机 ${\mathrm{M}}_1$ 识别上述语言 , 时间复杂度是 $\mathrm{O}(\mathrm{n})+\mathrm{O}({\mathrm{n}}^2)=\mathrm{O}({\mathrm{n}}^2)$ ;

两个带子的图灵机 与 一个带子的图灵机 计算能力 是等价的 ,

计算能力 等价 指的是 可以 识别相同的语言 , 解决相同的计算问题 ,

但是两种图灵机的 计算效率不同 , 两个带子的图灵机计算效率一般 高于 一个带子的图灵机的计算效率 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111052723