文章目录

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

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

计算问题如下 :

给定语言 :A={0k1k:k≥0}\rm A = \{ 0^k1^k : k \geq 0 \}A={0k1k:k≥0}

构造 两个带子的 图灵机 M3\rm M_3M3​ 认识上述语言 ;

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

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

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

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

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

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

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

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

M3\rm M_3M3​ 是两个带子的图灵机 , 算法设计如下 :

M3=\rm M_3 =M3​= " 在输入字符串 w\rm ww 上进行如下计算 :

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

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

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

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

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

首先检查 010101 的相对顺序 , 最坏的情况下是读头走 n\rm nn 步 , 其复杂度是 O(n)\rm O(n)O(n) ;

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

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

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

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

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

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