文档章节

图灵停机问题

听那水
 听那水
发布于 2015/03/30 14:14
字数 595
阅读 9
收藏 0

概述:不存在这样一个程序(算法),它能够计算任何程序(算法)在给定输入上是否会结束(停机)。

那么,如何来证明这个停机问题呢?
反证!假设我们某一天真做出了这么一个极度聪明的万能算法(就叫God_algo吧),你只要给它一段程序(二进制描述),再给它这段程序的输入,它就能告诉你这段程序在这个输入上会不会结束(停机),我们来编写一下我们的这个算法吧:
bool God_algo(char* program, char* input)
{
    if(<program> halts on <input>)
        return true;
    return false;
}


这里我们假设if的判断语句里面是你天才思考的结晶,它能够像上帝一样洞察一切程序的宿命。现在,我们从这个God_algo出发导出一个新的算法:
bool Satan_algo(char* program)
{
if( God_algo(program, program) )
{
       while(1);        // loop forever!
       return false;   // can never get here!
}
else
       return true;
}
正如它的名字所暗示的那样,这个算法便是一切邪恶的根源了。当我们把这个算法运用到它自身身上时,会发生什么呢?
Satan_algo(Satan_algo);
我们来分析一下这行简单的调用:
显然,Satan_algo(Satan_algo)这个调用要么能够运行结束返回(停机),要么不能返回(loop forever)。
如果它能够结束,那么Santa_algo算法里面的那个if判断就会成立(因为God_algo(Santa_algo,Santa_algo)将会返回true),从而程序便进入那个包含一个无穷循环while(1);的if分支,于是这个Satan_algo(Satan_algo)调用便永远不会返回(结束)了。
如果不能结束(停机),则if判断就会失败,从而选择另一个if分支并返回true,即Satan_algo(Satan_algo)又能够返回(停机)。
总之,我们有:
Satan_algo(Satan_algo)能够停机=> 它不能停机
Satan_algo(Satan_algo)不能停机=> 它能够停机

所以它停也不是,不停也不是,左右矛盾。

© 著作权归作者所有

共有 人打赏支持
听那水
粉丝 1
博文 9
码字总数 4697
作品 0
青岛
网页/平面设计
私信 提问
带你深入理解图灵机--天才所在的时代

这几年由于区块链的大热,以太坊独特的solidity语言实现智能合约功能,图灵完备这个词走进大家的视线。 没有计算机专业知识的同学其实很难理解这个词的意思,其实计算机专业的同学都没有深入...

jerry_one
2018/06/19
0
0
智能哲学:如何判断一台机器是不是人工智能?

计算机是人工智能吗? 编者按:本文作者周剑铭、柳渝,来自北邮人机与认知实验室。 蒸汽机被看作近代社会开始的标志,或许也可以把计算机看作当代社会开始的一个标志。计算机正在成为一件视而...

行者武松
2018/03/02
0
0
有没有比图灵机能力更强的计算模型?

有,而且还不少。他们被称为超计算(Hyper computation)模型。 超计算,是一个研究比图灵机计算能力更强的计算能力的计算机器的理论计算机科学分支。 主要有以下部分模型: A.谕示机. (Ora...

扩展的灰
2018/09/25
0
0
喷下现在的人工智能哈

正好学习一个国际会议的ppt稿件,看到一篇涉及人脑思维与现有计算机不同的文章。中间举了个例子确实不错,摘抄出来,哈,看看现有的所谓的新的人工智能算法,或者其他所谓先进的基于演绎逻辑...

中山野鬼
2013/11/08
743
12
带你深入理解图灵机--什么是图灵机、图灵完备

上一篇介绍了天才图灵所做的时代背景,我们了解那个时代对于数学逻辑,可计算理论的发展。站在更大的时间和空间维度来看,我们看问题的角度会有更高的视角。 这篇我们来具体看下图灵机到底是...

jerry_one
2018/06/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【spring】- springmvc 工作原理

核心:前端控制器:DispatcherServlet 功能:MVC设计模式中的Controller角色,掌控全局 类图 原理 本质是将DispatcherServlet及关联的Spring上下文环境的初始化工作织入Servlet的生命周期内,...

ZeroneLove
15分钟前
1
0
OSChina 周日乱弹 —— 做一只舔狗,开心时就去舔她,不开心时就舔自己

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @温家成 :分享连诗雅的单曲《水星逆行》 《水星逆行》- 连诗雅 手机党少年们想听歌,请使劲儿戳(这里) @罗马的王 :在家嫌猫吵,去书城看书...

小小编辑
52分钟前
33
3
Ruby中的继承、原型、面向对象、访问域

先有类还是先有对象 从鸡蛋悖论解决可以悟到一个道理,不要从常识上假设非此即彼和绝对静止。 Ruby中的类和对象正是这么个东西 我们创建一个类,那它就是Class这个对象的实例,而Class,于是...

可数局部基
今天
5
0
什么时候使用字节流、什么时候使用字符流,二者的区别

在程序中所有的数据都是以流的方式进行传输或保存的,程序需要数据的时候要使用输入流读取数据,而当程序需要将一些数据保存起来的时候,就要使用输出流完成。 InputStream 和OutputStream,...

watermelon11
今天
6
0
Alpakka Kafka,反应式Kafka客户端

Alpakka Kafka 是一个要用于 Java 和 Scala 语言的开源的流感知和反应式集成数据线项目。它建立在 Akka Stream之上,提供了 DSL 来支持反应式和流式编程,内置回压功能。Akka Streams 是 Re...

羊八井
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部