文章目录

一、非确定性图灵机二、非确定性图灵机 指令三、非确定性图灵机 计算示例 初始状态四、计算步骤 1五、计算步骤 2六、计算步骤 3 ( 出现非确定性分支 )七、计算步骤 3-1 ( 分支 1 )八、计算步骤 3-2 ( 分支 2 )九、计算步骤 3-1-1 ( 第 3 步分支 1 后面 1 步 )十、计算步骤 3-2-1 ( 第 3 步分支 2 后面 1 步 )十一、计算树

一、非确定性图灵机

向非确定性图灵机中输入字符串 , 每次的后续操作 , 不是唯一的 , 有很多可能性 ;

二、非确定性图灵机 指令

非确定性图灵机计算 :

下图中的指令 “0→1,R\rm 0 \to 1, R0→1,R” 含义 :

读写头操作 :如果当前 处于 q0\rm q_0q0​ 状态 , 读写头指向 000 字符 , 将 000 字符擦除 修改为 111 字符 ;

状态改变 :当前状态修改为 q0\rm q_0q0​ 状态 ;

读写头移动方向 :R\rm RR , Right , 读写头向右移动 ;

下图中的指令 “1→0,R\rm 1 \to 0, R1→0,R” 含义 :

读写头操作 :如果当前 处于 q0\rm q_0q0​ 状态 , 读写头指向 111 字符 , 将 111 字符擦除 修改为 000 字符 ;

状态改变 :当前状态修改为 q1\rm q_1q1​ 状态 ;

读写头移动方向 :R\rm RR , Right , 读写头向右移动 ;

三、非确定性图灵机 计算示例 初始状态

假设向该图灵机中输入 w=0101\rm w = 0101w=0101 字符串 , 下面是详细的计算过程 :

最初状态如下 :默认状态 q0\rm q_0q0​ , 读写头指向第 111 个字符 000 字符 ; 后面的 B\rm BB 指的是空白字符 ;

格局 :q00101\rm q_0 0101q0​0101

( 格局 即 当前快照 , 状态写在当前 读写头 指向的字符 的 左边 )

四、计算步骤 1

当前是 q0\rm q_0q0​ 状态 , 读到 000 字符 ;

符合条件的指令 :q0\rm q_0q0​ 状态 下执行 “0→1,R\rm 0 \to 1, R0→1,R” 指令 状态转为 q0\rm q_0q0​ 状态 ,

读写头将 000 字符改为 111 字符 , 向右移动一格字符 ;

自动机变为如下状态 , 格局是 1q0101\rm 1q_01011q0​101 ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

五、计算步骤 2

当前是 q0\rm q_0q0​ 状态 , 读到 111 字符 ;

符合条件的指令 :q0\rm q_0q0​ 状态 下执行 “1→0,R\rm 1 \to 0, R1→0,R” 指令 状态转为 q1\rm q_1q1​ 状态 ,

读写头将 111 字符改为 000 字符 , 向右移动一格字符 ;

自动机变为如下状态 , 格局是 10q101\rm 10q_10110q1​01 ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

六、计算步骤 3 ( 出现非确定性分支 )

当前是 q1\rm q_1q1​ 状态 , 读到 000 字符 ;

符合条件的指令有两条 :

① 指令 111 :q1\rm q_1q1​ 状态 下执行 “0→0,R\rm 0 \to 0, R0→0,R” 指令 状态转为 q1\rm q_1q1​ 状态 ;

② 指令 222 :q1\rm q_1q1​ 状态 下执行 “0→0,L\rm 0 \to 0, L0→0,L” 指令 状态转为 q0\rm q_0q0​ 状态 ;

上述两个指令 分别是 向左移动 , 向右移动 ;

七、计算步骤 3-1 ( 分支 1 )

执行指令 111 , 读写头将 000 字符改为 000 字符 , 向右移动一格字符 ;

自动机变为如下状态 , 格局是 100q11\rm 100q_11100q1​1 ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

八、计算步骤 3-2 ( 分支 2 )

执行指令 222 , 读写头将 000 字符改为 000 字符 , 向左移动一格字符 ;

自动机变为如下状态 , 格局是 1q1001\rm 1q_10011q1​001 ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

九、计算步骤 3-1-1 ( 第 3 步分支 1 后面 1 步 )

在 计算步骤 3-1 计算完成的基础上 , 继续后续计算 :

在 q1\rm q_1q1​ 状态下 , 读取 111 字符 ;

符合条件的指令 :q1\rm q_1q1​ 状态下执行 “1→1,R\rm 1 \to 1, R1→1,R” 指令 状态转为 q1\rm q_1q1​ 状态 ,

自动机变为如下状态 , 格局是 1001q1\rm 1001q_11001q1​ ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

十、计算步骤 3-2-1 ( 第 3 步分支 2 后面 1 步 )

在 计算步骤 3-2 计算完成的基础上 , 继续后续计算 :

当前是 q1\rm q_1q1​ 状态 , 读到 000 字符 ;

符合条件的指令有两条 :

① 指令 111 :q1\rm q_1q1​ 状态下执行 “0→0,R\rm 0 \to 0, R0→0,R” 指令 状态转为 q1\rm q_1q1​ 状态 ;

② 指令 222 :q1\rm q_1q1​ 状态下执行 “0→0,L\rm 0 \to 0, L0→0,L” 指令 状态转为 q0\rm q_0q0​ 状态 ;

上述两个指令 分别是 向左移动 , 向右移动 ;

此处又要开始分支 , 就不再详细分析了 ; 格局会如下继续分叉 ;

十一、计算树

非确定性图灵机 读取特定字符串 www , 可以生成一个 树形的 格局的 数据结构 ; 该数据结构称为 计算树 ;

计算树样式如下 :

计算树中 ,每个箭头都代表一个图灵机的计算指令步骤 ;

分析计算模型的计算复杂度时 , 需要将图灵机的计算过程 , 转为上图计算树样式的数据结构 , 在该数据结构上可以更容易理解计算复杂度 ;

计算树有可能出现一个分支 , 有无限长的箭头成的计算 , 也就是说图灵机在计算该计算树分支的时候 ,永不停机, 这种情况是允许出现的 ;

计算树中还有可能出现一个分支 ,在很早的时候 , 就达到了接受状态 , 图灵机自动停机;

【计算理论】图灵机 ( 非确定性图灵机 | 非确定性图灵机指令分析 | 计算过程 | 非确定性指令出现多个分支 | 非确定性图灵机转为计算树 | 计算树 )