数学联邦政治世界观
超小超大

元数学:计算机、悖论与数学基础 (8-4)

图灵的原始论文包含了一种编程语言,就像哥德尔的论文一样,也就是我们现在所说的编程语言。但这两种编程语言截然不同。图灵的编程语言并非像 LISP 这样的高级语言;它更像是一种机器语言,是输入计算机中央处理器的 1 和 0 的原始代码。事实上,图灵在 1936 年的发明,是一种糟透的机器语言,今天没有人会想用它,因为它太初级,太不成熟了。

尽管图灵所假想的计算机非常简单,其机器语言亦颇为原始,但它们却非常灵活。图灵在 1936 年的论文中声称,这样的机器应该能够完成人类所能够完成的任何计算。

图灵的思路,现在发生了戏剧性的转变。他问,对于这样一台机器来说,有什么是不可能的?它不能做什么?他立刻发现了一个图灵机所无法解决的问题:停止问题(the halting problem)。这是一个对图灵机(或计算机程序)最终是否会找到其想要的解并停止加以提前决定的问题。

halt

l →

K → H →lop?→ ◯

→ F ↺

倘若允许时间限制,这个问题就很容易解决。假设你想知道一个程序是否会在一年内停止运行。那你就运行它一年,它要么停止,要么不停止。图灵所证明的是,如果你并不设时间限制,如果你试图在并不对程序加以运行的情况下,推断程序是否会停止,你就会遇到大麻烦。

让我来概述一下图灵的推理: 假设你可以编写一个计算机程序,对任何给定的计算机程序最终是否会停止加以检查。称之为终止测试器(termination tester)。理论上,你给它输入一个程序,它就会吐出一个答案: "是的,这个程序会终止",或者,"不,它会在某个无限循环中转个不停,永远不会停止"。现在创建第二个程序,该程序对终止测试器加以动用,来评估某个程序。如果正在调查中的程序终止了,那么你的新程序就会被安排进一个无限循环。精妙的部分来了: 给你的新程序输入一个其自身之副本。它会做什么?

记住,你所编写这个新程序,其目的是,如果被测程序终止,那么新程序将进入无限循环。但在这里,它本身就是被测程序。因此,如果它终止,就会进入无限循环,这意味着它不会终止——这是一个矛盾。对相反的结果加以假设同样无济于事: 如果程序没有终止,终止测试器就会指出这一点,程序就并不会进入无限循环,从而终止。这个悖论让图灵得出结论:无法设计出通用的终止测试器。

有趣的是,图灵立即推导出一个推论: 如果无法通过计算以对一个程序是否会停止加以预判,那么也就无法通过推理来对程序是否会停止加以预判。没有任何一个形式化的公理系统,能让你推导出,程序最终是否会停止。为什么呢?因为如果你能以这种方式对形式公理系统加以使用,那你就有办法事先计算出,程序是否会停止。而这是不可能的,因为你会陷入一个悖论。比如 "这句话是错的!" 你可以创建一个当且仅当它不停止时,才会停止的程序。这个悖论与哥德尔在研究数论时所发现的情况类似。(回想一下,他当时研究的只是 0、1、2、3......以及加法和乘法,并没有更复杂的东西)。图灵的绝招在于,他证明了任何形式公理系统都不可能是完备的。

二战爆发后,图灵开始研究密码学,冯-诺依曼开始研究如何计算原子弹爆炸,人们暂时忘记了形式公理系统的不完备性。

数学中的随机性

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

将军家的小刺客 连载中
将军家的小刺客
曦兮云
阅读须知:架空/古言/不定时更新第一次写古言,不好见谅。——简介——魏都第一不败将军遇上魏都第一女刺客,只见那女刺客从腰中拔剑,厉声喊道:“......
0.3万字9个月前
异世界之许下不言弃的山盟海誓 连载中
异世界之许下不言弃的山盟海誓
卿言多爱
“虚假的神明,迷乱世人的眼睛”“他是废墟唯一的信徒”原创女频西幻文有cp食用愉快
0.2万字9个月前
快穿:心机绿茶白月光她又被团宠啦 连载中
快穿:心机绿茶白月光她又被团宠啦
一夜玄霜坠碧空
竹芊芊打小就对自己有着严格的要求,声乐舞蹈样样精通外,还考入了高等学府。毕业后如愿勾搭上富n代青年才俊,过上了被捧在手心里的富太太生活。你说......
0.1万字9个月前
重生之上官浅的觉醒 连载中
重生之上官浅的觉醒
骇客神条
(已签约)(已完结)经历过一世的上官浅又回到了最初,她还会和上一世一样被人欺骗吗?她还会走相同的路吗?
7.8万字9个月前
潋幻春颂歌 连载中
潋幻春颂歌
frost千笙
谁把谁的灵魂,装进谁的身体谁把谁的身体,变成囹圄囚禁自己。Youarenotguilty,guiltyistheworld.
0.4万字9个月前
记录我的梦境 连载中
记录我的梦境
荼靡茶香
记梦到的东西
0.0万字9个月前