【计算理论】可判定性 ( 对角线方法 | 使用对角线方法证明 通用任务图灵机 语言 不可判定 )
文章目录
一、存在性证明
存在性证明 : 肯定存在一些语言 , 不能被图灵机接受 ;
使用 语言 可以表示 计算问题 , 计算问题的个数与 实数 一样多 , 是 不可数的 ;
图灵机 的个数 与 自然数 一样多 , 是 可数的 ;
计算问题 要比 计算模型 多很多 , 计算问题 与 图灵机 之间不是 一一对应的 ;
肯定存在一个计算问题 , 找不出与之对应的图灵机 , 因此该计算问题肯定是 不可计算的 ,
二、证明 通用任务图灵机
语言 对应的计算模型一定是 不可判定 ( 对角线法 )
语言简介 :
将计算问题进行形式化 ,
是图灵机 ,
是字符串 , 如果
图灵机 接受
是字符串 , 将所有的可接受的
是字符串放在一个集合中 , 组成的语言 称为
语言 ;
语言 称为 图灵机可接受的 ;
语言 是可计算的 , 但 不是可判定的 ;
该结论可以区分 可判定语言 与 可计算语言 ;
使用 对角线法 证明 ;
与博客 【计算理论】可判定性 ( 对角线方法 | 证明自然数集 N 与实数集 R 不存在一一对应关系 ) 中证明 自然数集 与 实数集 不能一一对应类似 ;
在 【计算理论】可判定性 ( 计算模型与语言 | 区分 可计算语言 与 可判定语言 | 证明 某语言是 可计算语言 | 通用任务图灵机 与 特殊任务图灵机 ) 博客中证明了 通用图灵机语言 是计算语言 , 本博客中证明 通用图灵机语言 不可判定 ;
使用反证法证明 :
图灵机的结果有
个状态 , 接受状态 , 拒绝状态 , Loop 不停机状态 ;
语言只包含 接受状态 的情况 ;
所有的图灵机 与 自然数集 一样多 , 所有的图灵机 是可以枚举出来的 ,
图灵机 ;
枚举事务 , 一定有先决条件 , 如自然数集 , 无穷一定是可数的 , 不可数的无穷 , 如实数集 , 不能像上面图灵机一样枚举 , 实数是无法进行枚举的 ;
可以枚举的无穷 , 一定是可数无穷 ; 图灵机个数与自然数一样多 , 是可数无穷 , 因此可以枚举出来 ;
垂直表格中是枚举出来的图灵机 , 水平表格中是图灵机语言的编码 ;
表格中的内容 , 如第一行第一列 ,
与
交叉的项 , 表示 图灵机
在
编码上进行运算 , 其运算结果是 接受状态 ;
对角线意外的项都是有结果的 , 与本次证明无关, 省略了 , 接受或拒绝 ;
< m 1 > <m_1> <m1> | < m 2 > <m_2> <m2> | < m 3 > <m_3> <m3> | ⋯ \cdots ⋯ | < m n > <m_n> <mn> | |
---|---|---|---|---|---|
M 1 \rm M_1 M1 | 接受 | ||||
M 2 \rm M_2 M2 | 拒绝 | ||||
M 3 \rm M_3 M3 | 接受 | ||||
⋮ \rm \vdots ⋮ | |||||
M n \rm M_n Mn | 拒绝 |
接受
拒绝
接受
拒绝
假设 : 存在一个 图灵机
,
语言 是可判定的 ;
表格中的 图灵机
的结果是已知的 , 接受 或 拒绝 ;
构造 图灵机
, 根据图灵机语言编码
上的操作 :
图灵机
, 在
编码上的计算结果 , 主要查看第
行 , 第
列的 , 即 图灵机
在
编码上的结果 , 该计算结果是 接收 的 , 那么 图灵机
在
编码 上的结果就设定相反的结果 , 拒绝 ;
图灵机
, 在
编码上的计算结果 , 主要查看第
行 , 第
列的 , 即 图灵机
在
编码上的结果 , 该计算结果是 拒绝 的 , 那么 图灵机
在
编码上的结果就设定相反的结果 , 接收 ;
图灵机
, 在
编码上的计算结果 , 主要查看第
行 , 第
列的 , 即 图灵机
在
编码上的结果 , 如果该计算结果是 接受 的 , 那么 图灵机
在
编码上的结果就设定相反的结果 , 拒绝 ;
图灵机
, 在
编码上的计算结果 , 主要查看第
行 , 第
列的 , 即 图灵机
在
编码上的结果 , 如果该计算结果是 拒绝 的 , 那么 图灵机
在
编码上的结果就设定相反的结果 , 接收 ;
构造出的
一定是图灵机 , 上述描述的算法对应的计算模型就是图灵机 ;
一定存在一个
, 图灵机
就是 对应的 图灵机
, 在上述表格对角线位置的结果 , 即在
编码上的计算结果 , 与 图灵机
的结果是不同的 ;
这样就产生了矛盾 , 图灵机
的计算结果 是 图灵机
在
编码上计算结果相反的结果 ; 而这两个图灵机是同一个图灵机 ;
因此假设 "存在一个 图灵机
,
语言 是可判定的 " 不成立 ,
通用任务图灵机
,
语言 是 不可判定的
相关文章
- vue项目刷新当前页面的方法
- 多重共线性:python计算VIF以及使用vif做因子独立性检验的方法「建议收藏」
- 【Python小脚本】基于装饰器的方法日志脚本
- 详解用 MiniFramework 计算程序运行时间的方法
- 【Kotlin】类的初始化 ① ( 成员属性 | Kotlin 自动为成员字段生成 getter 和 setter 方法 | 手动设置成员的 getter 和 setter 方法 | 计算属性 )
- 数据安全:Postgresql如何设置远程访问的方法,置防火墙或者关闭防火墙
- JAVA线程sleep和wait方法区别详解编程语言
- Linux计算文件大小的有效方法(linux计算文件大小)
- Linux快速计算文件数的方法(linux计算文件数)
- Linux下快速查找字符串的方法(linux中查找字符串)
- 数深入Linux:查看当前连接数的方法(linux查看当前连接)
- 科技巨头们正在入局解决数据安全的新方法——机密计算
- 轻松掌握!使用Linux查看服务器登陆记录的方法(linux查看服务器登陆)
- MySQL中获取当前时间的方法(mysql中当前时间)
- 解析Oracle中月份计算的方法(oracle计算月份)
- SQL Server计算小时差:一个实用方法(sqlserver小时差)
- Oracle数据库中计算百分比的方法(oracle中统计百分比)
- 学习MySQL两种查询方法(mysql两种方法)
- Oracle中实现日期计算的方法(oracle中日期的计算)
- Oracle中实现两个数之间除法计算的方法(oracle中两个数相除)
- Oracle中计算两日期差的简便方法(oracle 两日期差)
- Oracle 8 中行数据转列的方法(oracle 8 行转列)
- msSQLserver数据库备份、压缩与SQL数据库数据处理的方法
- Python中还原JavaScript的escape函数编码后字符串的方法