一、存在性证明

存在性证明 : 肯定存在一些语言 , 不能被图灵机接受 ;

使用 语言 可以表示 计算问题 , 计算问题的个数与 实数 一样多 , 是 不可数的 ;

图灵机 的个数 与 自然数 一样多 , 是 可数的 ;

计算问题 要比 计算模型 多很多 , 计算问题 与 图灵机 之间不是 一一对应的 ;

肯定存在一个计算问题 , 找不出与之对应的图灵机 , 因此该计算问题肯定是 不可计算的 ,

二、证明 通用任务图灵机 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言 对应的计算模型一定是 不可判定 ( 对角线法 )

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言简介 :

将计算问题进行形式化 , $\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}}$ 语言 是可计算的 , 但 不是可判定的 ;

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

使用 对角线法 证明 ;

与博客 【计算理论】可判定性 ( 对角线方法 | 证明自然数集 N 与实数集 R 不存在一一对应关系 ) 中证明 自然数集 与 实数集 不能一一对应类似 ;

在 【计算理论】可判定性 ( 计算模型与语言 | 区分 可计算语言 与 可判定语言 | 证明 某语言是 可计算语言 | 通用任务图灵机 与 特殊任务图灵机 ) 博客中证明了 通用图灵机语言 是计算语言 , 本博客中证明 通用图灵机语言 不可判定 ;

使用反证法证明 :

图灵机的结果有 $3$ 个状态 , 接受状态 , 拒绝状态 , Loop 不停机状态 ;

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 语言只包含 接受状态 的情况 ;

所有的图灵机 与 自然数集 一样多 , 所有的图灵机 是可以枚举出来的 , ${\mathrm{M}}_1,{\mathrm{M}}_2,{\mathrm{M}}_3,\cdots ,{\mathrm{M}}_{\mathrm{n}}$ 图灵机 ;

枚举事务 , 一定有先决条件 , 如自然数集 , 无穷一定是可数的 , 不可数的无穷 , 如实数集 , 不能像上面图灵机一样枚举 , 实数是无法进行枚举的 ;

可以枚举的无穷 , 一定是可数无穷 ; 图灵机个数与自然数一样多 , 是可数无穷 , 因此可以枚举出来 ;

垂直表格中是枚举出来的图灵机 , 水平表格中是图灵机语言的编码 ;

表格中的内容 , 如第一行第一列 , ${\mathrm{M}}_1$ 与 $<m_1>$ 交叉的项 , 表示 图灵机 ${\mathrm{M}}_1$ 在 $<m_1>$ 编码上进行运算 , 其运算结果是 接受状态 ;

对角线意外的项都是有结果的 , 与本次证明无关, 省略了 , 接受或拒绝 ;

假设 : 存在一个 图灵机 $\mathrm{H}$ , $A_{TM}$ 语言 是可判定的 ;

表格中的 图灵机 $\mathrm{H}$ 的结果是已知的 , 接受 或 拒绝 ;

构造 图灵机 $\mathrm{D}$ , 根据图灵机语言编码 $<{\mathrm{m}}_{\mathrm{n}}>$ 上的操作 :

图灵机 $\mathrm{D}$ , 在 ${\mathrm{m}}_1$ 编码上的计算结果 , 主要查看第 $1$ 行 , 第 $1$ 列的 , 即 图灵机 ${\mathrm{M}}_1$ 在 $<m_1>$ 编码上的结果 , 该计算结果是 接收 的 , 那么 图灵机 $\mathrm{D}$ 在 $<m_1>$ 编码 上的结果就设定相反的结果 , 拒绝 ;

图灵机 $\mathrm{D}$ , 在 ${\mathrm{m}}_2$ 编码上的计算结果 , 主要查看第 $2$ 行 , 第 $2$ 列的 , 即 图灵机 ${\mathrm{M}}_2$ 在 $<m_2>$ 编码上的结果 , 该计算结果是 拒绝 的 , 那么 图灵机 $\mathrm{D}$ 在 $<m_2>$ 编码上的结果就设定相反的结果 , 接收 ;

图灵机 $\mathrm{D}$ , 在 ${\mathrm{m}}_3$ 编码上的计算结果 , 主要查看第 $3$ 行 , 第 $3$ 列的 , 即 图灵机 ${\mathrm{M}}_3$ 在 $<m_3>$ 编码上的结果 , 如果该计算结果是 接受 的 , 那么 图灵机 $\mathrm{D}$ 在 $<m_3>$ 编码上的结果就设定相反的结果 , 拒绝 ;

$$⋮$$

图灵机 $\mathrm{D}$ , 在 ${\mathrm{m}}_{\mathrm{n}}$ 编码上的计算结果 , 主要查看第 $n$ 行 , 第 $n$ 列的 , 即 图灵机 ${\mathrm{M}}_{\mathrm{n}}$ 在 $<m_n>$ 编码上的结果 , 如果该计算结果是 拒绝 的 , 那么 图灵机 $\mathrm{D}$ 在 $<m_n>$ 编码上的结果就设定相反的结果 , 接收 ;

构造出的 $\mathrm{D}$ 一定是图灵机 , 上述描述的算法对应的计算模型就是图灵机 ;

一定存在一个 $\mathrm{k}$ , 图灵机 $\mathrm{D}$ 就是 对应的 图灵机 ${\mathrm{M}}_{\mathrm{k}}$ , 在上述表格对角线位置的结果 , 即在 $<{\mathrm{m}}_{\mathrm{k}}>$ 编码上的计算结果 , 与 图灵机 $\mathrm{D}$ 的结果是不同的 ;

这样就产生了矛盾 , 图灵机 $\mathrm{D}$ 的计算结果 是 图灵机 ${\mathrm{M}}_{\mathrm{k}}$ 在 $<{\mathrm{m}}_{\mathrm{k}}>$ 编码上计算结果相反的结果 ; 而这两个图灵机是同一个图灵机 ;

因此假设 "存在一个 图灵机 $\mathrm{H}$ , $A_{TM}$ 语言 是可判定的 " 不成立 ,

通用任务图灵机 $\mathrm{H}$ , $A_{TM}$ 语言 是 不可判定的

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/110935394