理解Goodstein定理

科普 意识

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

问题1

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

比如：给定整数581，可以首先表达为
$581 = 2^9 + 2^6 + 2^2 + 1$，
进一步，把指数上的数也表达为以2为基数，得到：
$581 = 2^{2^3+1} + 2^{2^2 + 2} + 2^2 + 1$，不断做，最后得到：
$581 = 2^{2^{2+1}+1} + 2^{2^2 + 2} + 2^2 + 1$
显然，如果数字比较大，指数上会不断递增，形成一个塔状，但这不是重点。

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

比如：$581 = 2^{2^{2+1}+1} + 2^{2^2 + 2} + 2^2 + 1$的base增1，得到：
$3^{3^{3+1}+1} + 3^{3^3 + 3} + 3^3 + 1$.
然后减1，得到：
$3^{3^{3+1}+1} + 3^{3^3 + 3} + 3^3$.

解释一下，为何最后的1没有变化呢？因为$1$是$1*3^0$，所以不是基数没有变，是变了，但是值不发生变化。请注意，这是一个关键点！

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

比如：对上面的结果继续操作得到：
- base增一： $4^{4^{4+1}+1} + 4^{4^4 + 4} + 4^4$.
- 得数减一： $4^{4^{4+1}+1} + 4^{4^4 + 4} + 3×4^3 + 3×4^2 + 3×4 + 3$.

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

答案1

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

例子： 比如，取$3 = 2^1 + 1$，读者自己验收一下，收获直观印象，确实会停止。

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

问题2

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

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

例：str = "abc"。

2、定义以下操作

• 删除该字符串的头字母；

例： str = "bc"

• 然后对字符串中剩余的每一个字母进行操作：将该字母的后一个字母插入到该字母的右边。‘z’字母后面没有字母，所以不进行任何操作。

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

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

答案2

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