文章目录

• 一、计算模型与语言
• 二、区分 可计算语言 与 可判定语言
• 三、证明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 可计算
• 四、通用 ( Universal ) 任务图灵机 与 特殊任务图灵机

一、计算模型与语言

---

计算模型是逐步进行扩张的 :

自动机 $\to$ 下推自动机 ( $1$ 个栈 ) $\to$下推自动机 ( $2$ 个栈 ) $\iff$ 图灵机

所对应的语言也是逐步进行扩张的 :

正则语言 $\to$ 上下文无关语言 $\to$ 可计算语言

正则语言 对应的 计算模型 是 确定性有限自动机 ,

上下文无关语言 对应的 计算模型 是 下推自动机 ,

可计算语言 对应的 计算模型 是 图灵机 ,

可判定语言 对应的 计算模型 是 判定机 ,

判定机 是一种 特殊的 图灵机 , 是图灵机的子集 ;

可判定语言 是 可计算语言 的子集 ;

图灵机 的 可计算语言 , 是计算机科学的研究领域 ;

二、区分 可计算语言 与 可判定语言

---

找一个特例语言 , 区分 可计算语言 与 可判定语言 ;

图灵机的可接受问题 :

将计算问题进行形式化 , $\mathrm{M}$ 是图灵机 , $\mathrm{w}$ 是字符串 , 如果 $\mathrm{M}$ 图灵机 接受 $\mathrm{w}$ 是字符串 , 将所有的可接受的 $\mathrm{w}$ 是字符串放在一个集合中 , 组成的语言 称为 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 ;

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}=\{<\mathrm{M},\mathrm{w}>|图灵机\mathrm{M}接受\mathrm{w}字符串\}$

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 称为 图灵机可接受的 ;

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 是可计算的 , 但 不是可判定的 ;

该结论可以区分 可判定语言 与 可计算语言 ;

三、证明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 可计算

---

证明 : ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 是可计算的 , 但 不是可判定的 ;

证明过程 : 构造图灵机 $\mathrm{U}$ ,

① 字符串 : 给定一个输入字符串 , $<\mathrm{M},\mathrm{w}>$ , 即 在 图灵机 $\mathrm{M}$ 上接受的字符串 $\mathrm{w}$ ;

② 模仿 : 字符串输入到 图灵机 $\mathrm{M}$ 之后 , 将自己想象成 $\mathrm{U}$ , 模仿 图灵机 $\mathrm{M}$ 在 字符串 $\mathrm{w}$ 上进行计算 ;

③ 接受 / 拒绝 状态 : 如果 图灵机 $\mathrm{M}$ 进入接受状态 , 则 图灵机 $\mathrm{U}$ 也进入接受状态 , 如果图灵机 $\mathrm{M}$ 进入拒绝状态 , 则 图灵机 $\mathrm{U}$ 也进入拒绝状态 ;

④ Loop 循环状态 : 图灵机 $\mathrm{M}$ 在 $\mathrm{w}$ 字符串上计算时 , 可能有第 $3$ 种可能性 , 即进入 Loop 循环状态 , 永不停机 ; 此时 图灵机 $\mathrm{U}$ 也只能进入 Loop 状态 ;

现在 图灵机 $\mathrm{U}$ 模仿的是 图灵机 $\mathrm{M}$ 在 字符串 $\mathrm{w}$ 上的计算 , 图灵机 $\mathrm{M}$ 进入什么状态 , 图灵机 $\mathrm{U}$ 就进入什么状态 ;

$\mathrm{U}$ 很显然是 图灵机 , 因此 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 对应的计算问题是可计算的 ;

证明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 不可判定 , 在下一篇博客中证明 ;

四、通用 ( Universal ) 任务图灵机 与 特殊任务图灵机

---

下面开始证明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 对应的计算问题 是 不可判定的 ;

根据 丘奇-图灵 命题 , 图灵机 等于 算法 ;

图灵机 $\mathrm{U}$ = " 在输入字符串 $<\mathrm{M},\mathrm{w}>$ 上 , $\mathrm{M}$ 是图灵机 , $\mathrm{w}$ 是字符串 , 则有 ① 模拟 $\mathrm{M}$ 在 $\mathrm{w}$ 上进行计算 , ② 如果 $\mathrm{M}$ 进入接受状态 , 则 $\mathrm{U}$ 接受 , $\mathrm{M}$ 拒绝 $\mathrm{U}$ 拒绝 , $\mathrm{M}$ Loop $\mathrm{U}$ 也 Loop "

上述 等号 左侧是 图灵机 $\mathrm{U}$ , 等号 右侧 是 算法 ;

等号 就是 丘奇-图灵 命题 ;

$\mathrm{U}$ 是通用 ( Universal ) 图灵机 ,

① 特殊任务图灵机 : 一般情况下 计算模型 是执行一个 特定任务 , 给定一个任务 , 给定一个输入 , 图灵机进行计算 , 然后输出结果 ;

② 通用任务图灵机 :

图灵机 $\mathrm{U}$ 不是特殊任务图灵机 , 而是一个 一般任务图灵机 , 该图灵机可以执行各种操作 ,

将各种图灵机 , 进行编码 , 输入到通用图灵机 $\mathrm{U}$ 中 , 通用图灵机 $\mathrm{U}$ 就会模仿 特殊图灵机 $\mathrm{M}$ 在字符串 $\mathrm{w}$ 上进行计算 ;

通用图灵机 $\mathrm{U}$ 的主要任务就是 模仿所有其它 特殊图灵机 $\mathrm{M}$ 进行计算 ;

计算机刚出现时 , 每个计算机只能执行特殊的任务 ,

真正的通用任务计算机是 冯诺依曼 设计的 , 可以执行所有的计算任务 ;

总结

以上是生活随笔为你收集整理的【计算理论】可判定性 ( 计算模型与语言 | 区分 可计算语言 与 可判定语言 | 证明 通用图灵机语言是 可计算语言 | 通用任务图灵机 与 特殊任务图灵机 )的全部内容，希望文章能够帮你解决所遇到的问题。

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