文章目录
一、计算模型与语言
二、区分 可计算语言 与 可判定语言
三、证明 A T M \rm A_{TM}A
TM
语言 可计算
四、通用 ( Universal ) 任务图灵机 与 特殊任务图灵机
一、计算模型与语言
计算模型是逐步进行扩张的 :
自动机 → \to→ 下推自动机 ( 1 11 个栈 ) → \to→下推自动机 ( 2 22 个栈 ) ⇔ \Leftrightarrow⇔ 图灵机
所对应的语言也是逐步进行扩张的 :
正则语言 → \to→ 上下文无关语言 → \to→ 可计算语言
正则语言 对应的 计算模型 是 确定性有限自动机 ,
上下文无关语言 对应的 计算模型 是 下推自动机 ,
可计算语言 对应的 计算模型 是 图灵机 ,
可判定语言 对应的 计算模型 是 判定机 ,
判定机 是一种 特殊的 图灵机 , 是图灵机的子集 ;
可判定语言 是 可计算语言 的子集 ;
图灵机 的 可计算语言 , 是计算机科学的研究领域 ;
二、区分 可计算语言 与 可判定语言
找一个特例语言 , 区分 可计算语言 与 可判定语言 ;
图灵机的可接受问题 :
将计算问题进行形式化 , M \rm MM 是图灵机 , w \rm ww 是字符串 , 如果 M \rm MM 图灵机 接受 w \rm ww 是字符串 , 将所有的可接受的 w \rm ww 是字符串放在一个集合中 , 组成的语言 称为 A T M \rm A_{TM}A
TM
语言 ;
A T M = { < M , w > ∣ 图 灵 机 M 接 受 w 字 符 串 } \rm A_{TM} = \{ <M , w> | 图灵机 M 接受 w 字符串 \}A
TM
={<M,w>∣图灵机M接受w字符串}
A T M \rm A_{TM}A
TM
语言 称为 图灵机可接受的 ;
A T M \rm A_{TM}A
TM
语言 是可计算的 , 但 不是可判定的 ;
该结论可以区分 可判定语言 与 可计算语言 ;
三、证明 A T M \rm A_{TM}A
TM
语言 可计算
证明 : A T M \rm A_{TM}A
TM
语言 是可计算的 , 但 不是可判定的 ;
证明过程 : 构造图灵机 U \rm UU ,
① 字符串 : 给定一个输入字符串 , < M , w > \rm <M , w><M,w> , 即 在 图灵机 M \rm MM 上接受的字符串 w \rm ww ;
② 模仿 : 字符串输入到 图灵机 M \rm MM 之后 , 将自己想象成 U \rm UU , 模仿 图灵机 M \rm MM 在 字符串 w \rm ww 上进行计算 ;
③ 接受 / 拒绝 状态 : 如果 图灵机 M \rm MM 进入接受状态 , 则 图灵机 U \rm UU 也进入接受状态 , 如果图灵机 M \rm MM 进入拒绝状态 , 则 图灵机 U \rm UU 也进入拒绝状态 ;
④ Loop 循环状态 : 图灵机 M \rm MM 在 w \rm ww 字符串上计算时 , 可能有第 3 33 种可能性 , 即进入 Loop 循环状态 , 永不停机 ; 此时 图灵机 U \rm UU 也只能进入 Loop 状态 ;
现在 图灵机 U \rm UU 模仿的是 图灵机 M \rm MM 在 字符串 w \rm ww 上的计算 , 图灵机 M \rm MM 进入什么状态 , 图灵机 U \rm UU 就进入什么状态 ;
U \rm UU 很显然是 图灵机 , 因此 A T M \rm A_{TM}A
TM
语言 对应的计算问题是可计算的 ;
证明 A T M \rm A_{TM}A
TM
语言 不可判定 , 在下一篇博客中证明 ;
四、通用 ( Universal ) 任务图灵机 与 特殊任务图灵机
下面开始证明 A T M \rm A_{TM}A
TM
语言 对应的计算问题 是 不可判定的 ;
根据 丘奇-图灵 命题 , 图灵机 等于 算法 ;
图灵机 U \rm UU = " 在输入字符串 < M , w > \rm <M , w><M,w> 上 , M \rm MM 是图灵机 , w \rm ww 是字符串 , 则有 ① 模拟 M \rm MM 在 w \rm ww 上进行计算 , ② 如果 M \rm MM 进入接受状态 , 则 U \rm UU 接受 , M \rm MM 拒绝 U \rm UU 拒绝 , M \rm MM Loop U \rm UU 也 Loop "
上述 等号 左侧是 图灵机 U \rm UU , 等号 右侧 是 算法 ;
等号 就是 丘奇-图灵 命题 ;
U \rm UU 是通用 ( Universal ) 图灵机 ,
① 特殊任务图灵机 : 一般情况下 计算模型 是执行一个 特定任务 , 给定一个任务 , 给定一个输入 , 图灵机进行计算 , 然后输出结果 ;
② 通用任务图灵机 :
图灵机 U \rm UU 不是特殊任务图灵机 , 而是一个 一般任务图灵机 , 该图灵机可以执行各种操作 ,
将各种图灵机 , 进行编码 , 输入到通用图灵机 U \rm UU 中 , 通用图灵机 U \rm UU 就会模仿 特殊图灵机 M \rm MM 在字符串 w \rm ww 上进行计算 ;
通用图灵机 U \rm UU 的主要任务就是 模仿所有其它 特殊图灵机 M \rm MM 进行计算 ;
计算机刚出现时 , 每个计算机只能执行特殊的任务 ,
真正的通用任务计算机是 冯诺依曼 设计的 , 可以执行所有的计算任务 ;
