边看边说序列的宇宙学（三）

作者：安迁

四、几个引理

本节为后面的定理证明作技术性的准备，大概是本文最没有意思的一节。因为它的内容从难度来说，可能高年级的小学生也能理解，但却相当琐碎，都是些考虑各种可能性的叙述和论证。一般的读者大可只阅读几个命题的内容而跳过论证。对于想自己编程验证的读者，则请特别注意分割引理的内容和我在后面的算法建议。

在康威的论文中，所有单独列出来的命题都叫“定理”。下面将介绍的“一天引理”、“分割引理”等等在他的论文中叫“一天定理”和“分割定理”等等。但是这些命题基本上用来证明过其他结论后就可以丢在一边，或展示的是技术性细节，所以我改称“引理”以示它们和在上篇里介绍的三个主要定理在重要性上有区别。

我们最终要考虑以任意数字串开始的边看边说序列，故本节中提到的数字串都不排除含有除了“1”“2”和“3”以外的符号——我们也称其为“数字”，并把它们称为“大于3的数字”（如果其中选用了符号“0”，那么它在上述意义下也是个大于3的数字）。对个数的解释我们则采用上篇中提到的第二种选择，也就是说，如果有连续1000个1的话，我们就替1000引入一个新的符号如“M”，称这是M个1。

下面的“一天引理”说，其实你只需在第一天里为引入新符号头痛一下。

（一天引理）任何一个年纪至少为1天的数字串里，不可能含有这样的子串： 1) 从奇数位置开始的baca，其中a，b，c是相同或不同的数字； 2) aaaa，或aaabbb，其中a，b是相同或不同的数字。

这个引理的证明可以用“显而易见”来形容。所谓的“年纪至少为1天的数字串”无非是说，它不是任意给出的，而是对着某个数字串边看边说出来的。要是在奇数位置开始出现了baca这样的子串，相当于在说看到的那个数字串里有“b个a，c个a”，这是不允许的，令d=b+c，你得说是“d个a”。不允许出现aaaa也一样，因为即便它在偶数位置开始，那也是在说“……个a，a个a，a个……”。aaabbb形式的子串也一样证明。

因为连续4个相同的字符不可能出现在一个年纪至少为1天的数字串里，那么连续4个以上相同的字符也不可能。所以所有大于3的数字，要么是最初（第0天）就有的，要么是第1天产生的（比如最初字符串里有连续1000个1，会在第1天被描述成M个1，从而引入数字M），从第2天开始就不会再有新的了。而对年纪至少为2天的数字串，我们还可以排除掉更多的子串的可能性：

（两天引理）在第2天和以后都不可能产生新的除了“1”“2”和“3”以外的符号。任何一个年纪至少为2天的数字串里，不可能含有这样的子串： 1) 3a3（特别地，不可能有333这样的子串）； 2) ab，其中a和b都是大于3的数字。

3a3这样的子串如果是在奇数位置开始出现的，那是边看前一天的数字串边说“3个a，3个……”，也就是aaabbb这样的子串，可根据一天引理这是不可能的；如果是在偶数位置开始出现的，那则是在讲“……个3，a个3”，这是不允许的。

如果有ab这样的子串，其中a和b都是大于3的数字，那么意味着前一天有“a个b”或是“b个……”形式的子串，一天引理也排除了这种可能性。

顺便说一句，从第3天起，数字串中大于3的数字的数量当然不会增加，但也不会再减少了，它们最终会产生出超铀元素的同位素。比如第0天的数字串如果是4444，第1天变成44，第2天变成24，“4”的数目一直在减少，但从第3天起，序列中的每个数字串都有且仅有一个4。

一个数字串中如果没有一天引理中的2)和两天引理中1)和2)提到的那些子串，它就是个好数字串。一天引理和两天引理说的就是，如果一个数字串是一个年纪至少2天的数字串的子串，它一定是个好数字串。好数字串总是演化出好数字串来。我们接下来要考虑的数字串都是好数字串。

下面介绍三种数字串模式，都是规定它是怎么开始的。这些模式在后面的引理中很重要：

A型：1a……的形式，其中a是不同于1的数字，而省略号部分或者是空的（也就是整个数字串就是1a），或者是一个不以a开头的数字串。
B型：111……的形式，其中省略号部分或者是空的（也就是整个数字串就是111），或者是一个不以1开头的数字串。
C型：3……的形式，其中省略号部分或者是空的（也就是整个数字串就是3），或者是一个不以3开头的数字串，而且前3个数字不都相同（如果这部分的长度至少是3的话）。

容易证明，任何A型好数字串过一天会变B型好数字串，任何B型好数字串过一天会变C型好数字串，任何C型好数字串过一天会变A型好数字串。这3型数字串都不以2开头，以2开头则有三种引申出来的数字串模式：

A’型：22……的形式，其中省略号部分是个A型数字串。
B’型：22……的形式，其中省略号部分是个B型数字串。
C’型：22……的形式，其中省略号部分是个C型数字串。

容易证明，任何A’型好数字串过一天会变B’型好数字串，任何B’型好数字串过一天会变C’型好数字串，任何C’型好数字串过一天会变A’型好数字串。另外我们早先提到过，单独的数字串22（也就是₁氢元素）总是演化成它自己。

这样我们就得到了3种循环模式，而下面的引理则更进一步：

（起首引理）：一个数字串的演化最终总会进入下面三种循环之一： 1) ……→A型→B型→C型→…… 2) ……→A’型→B’型→C’型→…… 3) ……→22→22→…… 如果它还没有进入循环，那么“1”“2”和“3”将均会出现在它后面演化过程中各项的首个数字中。

命题的最后一句话其实是说，如果一个数字串最终会进入ABC循环可是却还没进（也就是它还不是ABC型中的一种），那么它迟早会演化出一项以2开头的数字串来，然后再进入循环（那时不断地以1或3开头）；而如果一个数字串最终会进入A’B’C’循环可是却还没进，那么它迟早会演化出一项以1开头的数字串，和一项以3开头的字符串，然后再进入循环（那时总以2开头）。循环3)则是数字串22独有的。

起首定理的具体证明就不多说了，完全是力气活，把所有可能性都考虑一遍；多亏一天和两天引理，可以少考虑不少可能性。这证明小学生也能看得懂，可就是太啰哩吧嗦，真想看就只好请读者直接读原论文了。为了叙述方便起见我们再引入两个数字串开始的类型：

X型：以大于3的数字开始。
X’型：22……的形式，其中省略号部分或者是空的（也就是整个数字串就是22），或者是个X型数字串。

现在我们终于可以引入下面这个重要的引理，也就是分割的准则：

（分割引理）一个好数字串可以在某处分割成前后两个子串，当且仅当在满足以下某种情况时：

前	后
以大于3的数字结尾	以“1”，“2”或“3”开始
以“2”结尾	A型 _或 B型 _或 C型 _或 X型
不以“2”结尾	A’型 _或 B’型 _或 C’型 _或 X’型

有了起首引理，分割引理“当”部分的证明很容易。第一种情况很简单，以“1”，“2”或“3”开始的后数字串总还是演化成以“1”，“2”或“3”开始的数字串，不会和永远以大于3的数字结尾的前数字串混起来。第二种情况，前数字串永远以“2”结尾，后数字串永远以“1”或“3”或是大于3的数字开始，也不会混起来。第三种情况，前数字串永远不以“2”结尾，后数字串永远以“2”开始，也不会混起来。注意到如果结合第二种情况，在第三种情况下我们其实总能将数字串分割成3段：前数字串，22，以及一个A型或B型或C型或X型的数字串——除非原本的后数字串就是22本身。

还要证明“且仅当”部分，即除上述情况之外就不能分割。这个留给读者证明，去读康威的论文也没用，他同样也留给读者证明。证明过程的关键是起首引理结论的最后一部分。

如果读者要自己编一个分割数字串的程序，我建议采用如下方法：

首先验证那是个好字符串。然后找到所有不是“1”“2”“3”的数字，在它后面分割，将数字串分割成若干段。对每段分割好的子串进行如下操作：找到所有2，验证它后面的子串是否A、B、C、X型，如是则在这个2后面分割。对每段分割好的子串进行如下操作：验证它是否以恰好2个2结尾，如是，则将这2个2分割。

容易看出，这个算法能够将好数字串作完全的分割，既不会分割错，也不会有该分割却没有分割的地方。

最后相应于起首引理还有个结尾引理，没什么太大用处，为了完整起见也叙述一下：（结尾引理）：经过足够长时间后， 1) 任何一个以“1”结尾的数字串在演化过程中，序列的数字串末尾总会进入4步循环：……→₄₃锝→₄₂钼→₄₁铌→₄₀锆→……； 2) 任何一个以“2”结尾的数字串在演化过程中，序列的数字串末尾总会进入2步循环：……→₃锂→₂氦→……； 3) 任何一个以“3”结尾的数字串在演化过程中，序列的数字串末尾总会进入2步循环：……→₇₄钨→₇₃钽→……； 4) 任何一个以大于3的数字“n”结尾的数字串在演化过程中，序列的数字串末尾总会进入2步循环：……→₉₄钚ⁿ→₉₃镎ⁿ→……。

参考文献：

[1] John Horton Conway, The weird and wonderful chemistry of audioactive decay, Eureka 46:5-16 (1985); reprinted in Open Problems in Communication and Computation, T.M. Cover & B. Gopinath, eds., Springer-Verlag, New York, 173–188 (1987).