@bintou
2017-12-01T13:37:08.000000Z
字数 1103
阅读 2866
科普
意识
这篇短文的内容主要源自《皇帝的新脑》(Oxford university press, 1999, Roger Penrose)的前言。提出一个问题,给出一个惊人的结论。本文的目的是为另一篇书评收集素材,同时供读者玩赏。
1、给定一个正整数,把它写成以2为基数(base)的表达。
比如:给定整数581,可以首先表达为
,
进一步,把指数上的数也表达为以2为基数,得到:
,不断做,最后得到:
显然,如果数字比较大,指数上会不断递增,形成一个塔状,但这不是重点。
2、接下来对所得的数进行如下两步操作:
- 将数的基数增加1,
- 对所得数减1.
比如:的base增1,得到:
.
然后减1,得到:
.
解释一下,为何最后的1没有变化呢?因为是,所以不是基数没有变,是变了,但是值不发生变化。请注意,这是一个关键点!
3、不断重复第二步的操作:base增1,得数减1。
比如:对上面的结果继续操作得到:
- base增一: .
- 得数减一: .
4、重复以上的操作,似乎可以无限次地做下去,得数不断递增,而且增幅很大。对吗?
Goodstein定理告诉我们:不对!无论我们取什么正整数开始,重复进行这种操作,最终都会停止,得到一个0!
例子: 比如,取,读者自己验收一下,收获直观印象,确实会停止。
关于这个内容可以讲很多很多,暂时到此打住,敬请期待完整书评的出现。
一个稍微简化的问题,源自网络。
1、给定任一有限长度字符串,只考虑英文小写字母(a - z)组成的字符串)。
例:str = "abc"。
2、定义以下操作
例: str = "bc"
例: str = "bc"变成 str = "bccd"
请问,对于任何一个有限的字符串,重复以上操作,操作是否会停止,还是会无限次进行?
同样是令人吃惊的答案:对任意给定的有限字符串,重复操作多次之后,操作一定会停止,最后得到一个空串。
2017.11.30