数学心

第六百七十七章 停机问题(逻辑学)(1/1)

星阅小说网【wap.xyxsb.com】第一时间更新《数学心》最新章节。

图灵一开始假设,有可能制造出一台图灵机,它可以计算出一个程序在给定某种输入后是否会停止或永远运行。然后他证明,这台机器会导致一个矛盾,所以不可能存在。

图灵提到的这个想法,后来被称为停机问题。今天的软件开发人员将其称为无限循环,这是他们在编写循环或递归函数时遇到的一个问题。

戴维斯在想什么是可以计算的,只要把不可以计算的全部排除,剩下的就是全部可以计算的了。

停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。

该问题等价于如下的判定问题:是否存在一个程序P,对于任意输入的程序w,能够判断w会在有限时间内结束或者死循环。

最后戴维斯说:“存在一种图灵机,其停机问题是递归无解的。”

停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。

停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。

人气小说推荐More+

爱情公寓之我竟是胡一菲的学弟
爱情公寓之我竟是胡一菲的学弟
关于爱情公寓之我竟是胡一菲的学弟:林霄没想到只是下班吃个麻辣烫而已,竟然就穿越到新的世界。原本以为只是重新过平淡的一生,就意外遇见了爱情公寓里面的人,还是武力值最高的胡一菲,林霄才知道原来现在这个世界是各种影视剧的综合世界。既然知道了爱情公寓的存在,前世就是个爱情公寓迷的林霄当然不能错过最好的朋友在身边、最爱的人在对面的生活啦。
一只快乐的梨
我能召唤历史喵
我能召唤历史喵
关于我能召唤历史喵:陈行最近玩了一款名为‘猫猫荣耀’的历史抽卡养成类猫咪游戏,只不过令陈行没想到的是,自己抽到的猫猫竟然都是真实存在的。元璋喵:“咱就是大明皇帝朱元璋,喵~清照喵:“豪放派?我们婉约派打的就是你们豪放派,喵呜~!望着这一大家子的猫,陈行忍不住叹了口气。直到金光闪过,一个自称是‘刘秀喵’的熊猫出现在了客厅之中……“我擦,熊猫也算猫?圣火昭昭,圣光耀耀,凡我弟子,喵喵喵喵。作为一个有
呜喵王之怒
腌臜玫瑰
腌臜玫瑰
关于腌臜玫瑰:孤女夏橙认祖归宗后,最讨厌那个取代了自己位置的养女。养女纯洁无害,温柔伪善,衬得夏橙恶人一个,无可救药。夏橙收敛锋芒,学着养女的模样做一个好孩子,可面上越纯善,她就越知道自己心里到底想要什么......无论是养女喜欢的,还是喜欢养女的,她统统都要抢过来。风头,前途,家产,男人,她都要争上一争,将养女压的翻不过身。但是......风头家产这些都是好控制的死物,唯有那几个男人,渐渐发现
绛河客
渡执录
渡执录
大昭王朝设镇邪司,分御妖、镇鬼、狩灵三脉治之,处理天下玄异事。五百年前,神器乾坤珏降世,皇室夺得乾玉,坤玉却于混战中失踪。此后天下器灵皆陷入沉睡,狩灵一脉因无所用被朝廷遣散,唯有梅笑山师徒坚守传承。今九州灾异频发,国运式微。国师夜观星象,断言坤玉即将现世,唯有双玉合璧方可重铸山河。狩灵传人程庭芜,镇邪司首座贺云骁,因命运羁绊卷入这场纷争,共赴险途。当沉睡的器灵再度苏醒,当断代的狩灵之道重见天日。
会码字的馒头猫
重生一回,我在医学界疯狂摆烂
重生一回,我在医学界疯狂摆烂
(神医+系统+重生+无脑爽文+医学界摆烂+多职业+娱乐圈+科学界)本文属于无脑爽文,反派有强行降智的嫌疑,当然,男主的主线并不是一帆风顺的,注意:本文设定为都市框架的前提下,略带一点点圣母内容,根据读者大大们的反馈情况可能会出现一些微虐情节,请不要给作者寄刀片。祝大家阅读愉快
文刂氵羊