不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

古德斯坦定理(Goodstein’s theorem)(3)- 九头蛇游戏

已有 2116 次阅读 2021-12-28 03:36 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

古德斯坦定理(Goodstein’s theorem)的证明基于序数[1],为了形象阐释这个证明的意义,科比(Kirby)和帕里斯(Paris)在他们的论文《皮阿诺算术的可访独立性结果》中给出一个古德斯坦定理的变体: “九头蛇游戏”,重塑了希腊神话中的半神英雄赫拉克勒斯(Hercule)与勒拿九头蛇(Lerne)的神话故事 [2][3][4]


九头蛇游戏如下:一个有许多头和脖子的怪物,作为他十二项任务中的第二项,赫拉克勒斯必须迎击九头蛇,砍下它的所有的头。问题是,当九头蛇被斩首后,头又长出来了,赫拉克勒斯能战胜九头蛇吗?


将九头蛇表达为一棵有限的树,可以被看作是一个有限的线段的集合,每个线段连接两个节点,这样每个节点都由一条唯一的路径连接到一个被称为根的固定节点,九头蛇的头部节点只有一个线段连接。比如:

赫拉克勒斯与一个给定的九头蛇之间的战斗进行如下:在阶段nn>=1),赫拉克勒斯从九头蛇上砍下一个头,然后,九头蛇按以下方式长出n新头



当一个头被砍掉时,叶子和相应的边被从图中删除。九头蛇将从被删除的边下方的节点开始再生,生成该节点上方的树的部分的n个副本。因此,九头蛇在第一次再生时只生出一个副本,然后在第二次再生时两个副本,以此类推。然而,应该注意的是,当赫拉克勒斯砍掉与九头蛇的根直接相连的头时,它将无法再生。


令人惊讶的是,无论九头蛇的初始规模如何,都有一些策略战胜九头蛇。更令人惊奇的是,有一个策略始终有效,那就是随机地砍掉九头蛇的头,直到九头蛇完全灭绝。但更令人吃惊的是,这个结果是真实的,但不可能用递归证明等算术工具来证明它,这使得这个结果成为算术中的一个不可判定的问题。幸运的是,它可以在集合理论中得到证明,我们现在就来做这件事!


让我们定义九头蛇的权重,这种度量将不使用整数或实数,而是使用序数(nombres ordinaux)。我们将通过给每个头、每个脖子和每个节点定义一个权重来定义一个九头蛇的权重:首先给每个头分配数字0,给每个通向头的颈部分配数字1 然后,对于这些颈部中的一个或多个节点,我们关联颈部的数量。


这种权重的定义使我们能够将一个序数与每一个可想象的九头蛇联系起来。例如,给定一个九头蛇,其权重表达为,ω^(ω ^2+1)+ω^3+2


现在赫拉克勒斯入场,砍下了其中一个头,例如,最右边树枝上的一个头,那么九头蛇的权重将变成ω^(ω ^2+1)+ω^2x2+2,这是一个严格意义上较小的权重,因为ω^2x2是一个比ω^3严格意义上的小序数。

随着这些攻击持续不减,九头蛇的力量将继续减少。由于它是一个严格递减的序数,在经过有限次的攻击后,九头蛇的力量将不可避免地降至零,也就是说,赫拉克勒斯能够打败这只狰狞的九头蛇。


人们会问:为什么以这种方式定义九头蛇的权重,而不是以另一种方式?一个直观的解释是:因为如果你以任何其他方式定义它,有可能你就无法得出赫拉克勒斯的战斗结束的结论。更确切地说,通过这样定义九头蛇的权重,我们确保砍头的操作对应一个严格递减的序数,对此我们可以应用定理任何严格递减的序数都是有限的。例如,如果我们将权重定义为头数,我们将得到一个有时增加、有时减少的序列,对于这个序列,我们将无法说出很多有意义的东西。


当然,战斗肯定会非常漫长,但如果没有起码的耐心,你就无法拿下这个神话中的怪物,。。。


参考文献:

1https://en.wikipedia.org/wiki/Goodstein%27s_theorem

2http://www.cs.tau.ac.il/~nachumd/term/Kirbyparis.pdf

3https://www.youtube.com/watch?v=0tBScDTj0n0

4http://eljjdx.canalblog.com/archives/2016/02/12/33360210.html






https://m.sciencenet.cn/blog-2322490-1318432.html

上一篇:批判性思维(Critical thinking)(2)- 苏格拉底提问法
下一篇:简介尤瓦尔·赫拉利的《今日简史》(1) - 简介

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 18:50

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部