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

元数学:复杂度、随机性与不完备(一) (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),接着再看更方便。

相关小说

系统跟着娇美男作怪 连载中
系统跟着娇美男作怪
元小满
当一个爱吃瓜看戏的嘴强王者因为乱扫码而签订了系统后,走上了过日子也要被强迫的生活,也就出现了随时随地与系统对立大小骂。怨气是有,但是系统所规......
31.8万字8个月前
悲观主义水流的笑之岩 连载中
悲观主义水流的笑之岩
时令性决堤
第五人格(主宿伞之魂,多cp)、oc、随感大杂烩,主观性强,观赏性差,不建议阅读。
0.1万字8个月前
雅家:孟小姐,她非常反骨 连载中
雅家:孟小姐,她非常反骨
夏芝月
自己看吧!我不喜欢剧透
0.7万字8个月前
腐草为萤虫,黄粱梦醒时,廖无人烟 连载中
腐草为萤虫,黄粱梦醒时,廖无人烟
祈忧_800698
注意:【无cp,元素混杂,有降智情节,主角恶人,不洗白】————若……神是臆想出来的,那他们杀的是什么?现实中又是谁死了?————某天,一位......
7.2万字8个月前
三世缘,情不悔 连载中
三世缘,情不悔
mx沫兮殿下
三生三世,谁的情缘乱了谁的心三生三世,谁的承诺化作尘土飞灰湮灭三生三世,谁的情结不卑不亢三生三世,谁的爱终化作相思泪……三世情缘,诉说不一样......
38.3万字8个月前
隐世华族1 连载中
隐世华族1
结恋之时
你的选择,决定我们的命运!
0.4万字8个月前