[关闭]
@bintou 2017-12-01T05:37:08.000000Z 字数 1103 阅读 2644

理解Goodstein定理

科普 意识


这篇短文的内容主要源自《皇帝的新脑》(Oxford university press, 1999, Roger Penrose)的前言。提出一个问题,给出一个惊人的结论。本文的目的是为另一篇书评收集素材,同时供读者玩赏。

问题1

1、给定一个正整数,把它写成以2为基数(base)的表达。

比如:给定整数581,可以首先表达为

进一步,把指数上的数也表达为以2为基数,得到:
,不断做,最后得到:

显然,如果数字比较大,指数上会不断递增,形成一个塔状,但这不是重点。

2、接下来对所得的数进行如下两步操作:
- 将数的基数增加1,
- 对所得数减1.

比如:的base增1,得到:
.
然后减1,得到:
.

解释一下,为何最后的1没有变化呢?因为,所以不是基数没有变,是变了,但是值不发生变化。请注意,这是一个关键点!

3、不断重复第二步的操作:base增1,得数减1。

比如:对上面的结果继续操作得到:
- base增一: .
- 得数减一: .

4、重复以上的操作,似乎可以无限次地做下去,得数不断递增,而且增幅很大。对吗?

答案1

Goodstein定理告诉我们:不对!无论我们取什么正整数开始,重复进行这种操作,最终都会停止,得到一个0!

例子: 比如,取,读者自己验收一下,收获直观印象,确实会停止。

关于这个内容可以讲很多很多,暂时到此打住,敬请期待完整书评的出现。

问题2

一个稍微简化的问题,源自网络。

1、给定任一有限长度字符串,只考虑英文小写字母(a - z)组成的字符串)。

例:str = "abc"。

2、定义以下操作

例: str = "bc"

例: str = "bc"变成 str = "bccd"

请问,对于任何一个有限的字符串,重复以上操作,操作是否会停止,还是会无限次进行?

答案2

同样是令人吃惊的答案:对任意给定的有限字符串,重复操作多次之后,操作一定会停止,最后得到一个空串。
2017.11.30

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注