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

元数学:复杂度、随机性与不完备(一) (12-7)

事实上,我们刚刚已经证明,如果我们的停止问题算法,其大小是N比特,那么一定有一个程序是永远不会停止的,而且这个程序的大小最多只是比N比特大几个比特,但我们不能用我们的N比特停止问题算法加以决定这个程序永远不会停止。(我们假设停止问题算法宁愿永远不给出答案,也不愿给出错误答案。这种算法可以重新解释为 FAS)。

因此,我们刚刚证明了图灵著名的 1936 结果,与他最初证明的方式完全不同,我们使用的是程序大小、算法信息和软件复杂度的概念。在我找到的所有图灵结果的证明中,这个是我最喜欢的。

现在我必须坦白另一件事。我认为,在找到自己的证明之前,你无法真正理解一个数学结果。读别人的证明不如自己找证明。事实上,我认识的一位优秀数学家罗伯特-索洛维从不让我向他解释证明。他总是坚持只让我告诉他结果的陈述,然后他自己去思考!我对此印象深刻!

这是我能找到的对图灵结果的最直接、最直接、最基本的证明。我试图抓住问题的核心,去掉所有杂乱无章的东西,去掉所有妨碍理解的外围细节。

这也意味着,我们在第二章讨论希尔伯特第10个问题时缺失的部分现在已经补上了。

为什么停止问题很有趣?嗯,因为在第二章中,我们证明了如果停止问题无法解决,那么希尔伯特第 10 个问题也就无法解决,也就没有算法来决定二叉方程是否有解。事实上,图灵的停止问题与希尔伯特的第 10 个问题是等价的,从这个意义上说,任何一个问题的解都会自动地提供(provide)/担保(entail)另一个问题的解。

停止概率Ω和自限制程序

现在,我们将真正获得不可还原的数学事实,即 "无理由真(are true for no reason)"的数学事实,它在纯数学中尽可能地模拟了公平硬币的独立抛掷:这是停止概率Ω之基二扩展(base-two expansion)的比特!你无法证明一个程序是优美的,这个美丽而富有启发性的事实只是一个热身练习!

与其像图灵那样只看一个程序,问它是否停止,不如把所有可能的程序装进袋子里,摇一摇,闭上眼睛,挑出一个程序。我们随机选择的这个程序最终停止的概率是多少?让我们用一个介于 0 和 1 之间的无限精确二进制实数来表示这个概率。瞧!它的位数就是我们独立的数学事实。

The Halting Probability Ω

You run a program chosen by chance on a fixed computer. Each time the computer requests the next bit of the program. flip a coin to generate it,using independent tosses of a fair coin The computer must decide by itself when to stop reading the program. This forces the program to be self-delimiting

binary information.

You sum for each program that halts

the probability of getting precisely

that program by chance:

Ω=∑ program p halts 2—(size in bits of p)

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

相关小说

烟岁 连载中
烟岁
泱凌
“烟花易冷,岁月无声”少女会经历怎样的冒险呢?……
1.9万字9个月前
梨花殇殇,与子同归 连载中
梨花殇殇,与子同归
玉清舟
{已签约}原创双女主,又名《戏微澜》目前章节修改至“登闻鼓初响【下】
18.3万字8个月前
快穿:每个世界都要被吃干抹净 连载中
快穿:每个世界都要被吃干抹净
揽风入我怀
她是一缕幽魂,因为自卑,在旁人的冷嘲热讽中投湖自尽。她的尸身葬于鱼腹中,她的家人对她的死视而不见。她恨自己的怯懦,却也无能为力。如果这时候,......
1.1万字8个月前
斗龙战士之杨天乐的妹妹 连载中
斗龙战士之杨天乐的妹妹
瀹九九
我现在才知道友情是多么虚伪———杨雨希
0.2万字8个月前
师尊难为,徒儿多娇 连载中
师尊难为,徒儿多娇
周花
(1v1)(已签约)穿书前,楚烟是个潇洒自在,粉丝无数的三金影后,是个御姐范十足的宠粉狂魔。穿书后,为了任务被迫宠反派徒弟,宠着宠着人家被她......
4.4万字8个月前
十二星座:神之契 连载中
十二星座:神之契
回音映画
『本书已签约』「爱与勇气的星之少年奇幻冒险剧——神之契系列第一作:星神篇」你,相信神明吗?你曾痛恨自己的无力,渴望得到力量得到,可以守护你自......
11.2万字8个月前