文章目录

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

一、非确定性图灵机

---

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

二、非确定性图灵机 指令

---

非确定性图灵机计算 :

下图中的指令 “$0\to 1,\mathrm{R}$” 含义 :

读写头操作 : 如果当前 处于 ${\mathrm{q}}_0$ 状态 , 读写头指向 $0$ 字符 , 将 $0$ 字符擦除 修改为 $1$ 字符 ;

状态改变 : 当前状态修改为 ${\mathrm{q}}_0$ 状态 ;

读写头移动方向 : $\mathrm{R}$ , Right , 读写头向右移动 ;

下图中的指令 “$1\to 0,\mathrm{R}$” 含义 :

读写头操作 : 如果当前 处于 ${\mathrm{q}}_0$ 状态 , 读写头指向 $1$ 字符 , 将 $1$ 字符擦除 修改为 $0$ 字符 ;

状态改变 : 当前状态修改为 ${\mathrm{q}}_1$ 状态 ;

读写头移动方向 : $\mathrm{R}$ , Right , 读写头向右移动 ;

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

---

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

最初状态如下 : 默认状态 ${\mathrm{q}}_0$ , 读写头指向第 $1$ 个字符 $0$ 字符 ; 后面的 $\mathrm{B}$ 指的是空白字符 ;

格局 : ${\mathrm{q}}_{0}0101$

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

四、计算步骤 1

---

当前是 ${\mathrm{q}}_0$ 状态 , 读到 $0$ 字符 ;

符合条件的指令 : ${\mathrm{q}}_0$ 状态 下执行 “$0\to 1,\mathrm{R}$” 指令 状态转为 ${\mathrm{q}}_0$ 状态 ,

读写头将 $0$ 字符改为 $1$ 字符 , 向右移动一格字符 ;

自动机变为如下状态 , 格局是 $1{\mathrm{q}}_{0}101$ ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

五、计算步骤 2

---

当前是 ${\mathrm{q}}_0$ 状态 , 读到 $1$ 字符 ;

符合条件的指令 : ${\mathrm{q}}_0$ 状态 下执行 “$1\to 0,\mathrm{R}$” 指令 状态转为 ${\mathrm{q}}_1$ 状态 ,

读写头将 $1$ 字符改为 $0$ 字符 , 向右移动一格字符 ;

自动机变为如下状态 , 格局是 $10{\mathrm{q}}_{1}01$ ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

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

---

当前是 ${\mathrm{q}}_1$ 状态 , 读到 $0$ 字符 ;

符合条件的指令有两条 :

① 指令 $1$ : ${\mathrm{q}}_1$ 状态 下执行 “$0\to 0,\mathrm{R}$” 指令 状态转为 ${\mathrm{q}}_1$ 状态 ;

② 指令 $2$ : ${\mathrm{q}}_1$ 状态 下执行 “$0\to 0,\mathrm{L}$” 指令 状态转为 ${\mathrm{q}}_0$ 状态 ;

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

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

---

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

自动机变为如下状态 , 格局是 $100{\mathrm{q}}_{1}1$ ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

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

---

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

自动机变为如下状态 , 格局是 $1{\mathrm{q}}_{1}001$ ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

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

---

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

在 ${\mathrm{q}}_1$ 状态下 , 读取 $1$ 字符 ;

符合条件的指令 : ${\mathrm{q}}_1$ 状态下执行 “$1\to 1,\mathrm{R}$” 指令 状态转为 ${\mathrm{q}}_1$ 状态 ,

自动机变为如下状态 , 格局是 $1001{\mathrm{q}}_1$ ; ( 格局中 , 状态写在读写头指向的字符前面 )

格局进度 :

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

---

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

当前是 ${\mathrm{q}}_1$ 状态 , 读到 $0$ 字符 ;

符合条件的指令有两条 :

① 指令 $1$ : ${\mathrm{q}}_1$ 状态下执行 “$0\to 0,\mathrm{R}$” 指令 状态转为 ${\mathrm{q}}_1$ 状态 ;

② 指令 $2$ : ${\mathrm{q}}_1$ 状态下执行 “$0\to 0,\mathrm{L}$” 指令 状态转为 ${\mathrm{q}}_0$ 状态 ;

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

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

十一、计算树

---

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

计算树样式如下 :

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

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

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

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

总结

以上是生活随笔为你收集整理的【计算理论】图灵机 ( 非确定性图灵机 | 非确定性图灵机指令分析 | 计算过程 | 非确定性指令出现多个分支 | 非确定性图灵机转为计算树 | 计算树 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。