康威链式箭号表示法

康威链式箭号表示法，是由约翰·何顿·康威发明的，用来表示大数。1形式上看起来会像这样：2→3→4→5→6。

定义康威链式箭号表示法的长度定义如下：

任何一个正整数是长度为1的康威链。

假若有一个长度是n的康威链，后面加上→和一个正整数，此时形成的链长度为n+1。

如果两个康威链代表相同的整数，那么就说它们是等价的。 下面四个规则说明如何用康威链表示整数，其中 和 是正整数， 是一个较短的康威链：

1、康威链 表示正整数 。

2、 代表指数 。

3、 等价于 。

4、 等价于 (在这里， 出现 次， 出现 次，括号数量为 对).

第四条规则可以以递回关系式列出，避免省略号的出现：

4a、

4b、

上面的四条规则可用来定义所有的康威链。例如长度为3的康威链，利用第四条规则，基本上长度仍然一样，但 和 会是递减的，当递减到1时，就可以利用第三条规则来使长度缩短，使得它可利用第二条规则来计算出来。

性质1、长度为3的康威链对应hyper运算符和高德纳箭号表示法：

2、X→Y形式上如同X→p（设Y是一个较短的康威链，如同X一样），因此：

3、一个康威链的开头是幂。

4、1→Y等价于1。

5、X→1→Y等价于X。

6、2→2→Y等价于4。

7、X→2→2等价于X→(X)，其中后面的X是先被算出来的整数，如 .

康威链不能被拆分，其箭号并不是二元运算符。其他二元运算符具有交换律及结合律，如2 + 3 = 3 + 2，2 + 3 + 2 = (2 + 3) + 2 = 2 + (3 + 2)，或者是按照规定的顺序，如 这类指数是从右至左计算，先计算 = 81，再计算 。康威链并不符合上述性质。例如：

第一个式子并不等于下面任何式子。

例子例子很快会变得非常复杂，先从简单的开始（其中有些例子也会应用高德纳箭号表示法）：

(1)n

= n(规则1)

(2)p→q

= (规则2)

例如：

(3)1→（任何康威链）

= 1，因为任何康威链最终可以被简化成一个数字，而1的任何次方都是1。 （事实上，任何含有1的康威链，在1后面的那些数字和箭号都可直接消去，一个例子如X→1→Y = X。）

(4)4→3→2

= 4→(4→(4)→1)→1（规则4），从内向外展开。

= 4→(4→4→1)→1（去掉多余的括号）

= 4→(4→4)→1（规则3）

= 4→(44)→1（规则2）

= 4→(256)→1（计算指数）

= 4→256→1（去括号）

= 4→256（规则3）

= 4256（规则2）

利用高德纳箭号表示法可以很容易解决：

(5)2→2→4

= 2→(2)→3（规则4）

= 2→2→3（去括号）

= 2→2→2（规则4，去括号）

= 2→2→1（规则4，去括号）

= 2→2（规则3）

= 4（规则2）（事实上，任何以2→2为开头的康威链其值均为4，本例是一个例子，应用性质6）

高德纳箭号表示法：

(6)2→4→3

= 2→(2→(2→(2)→2)→2)→2（规则4）

= 2→(2→(2→2→2)→2)→2（去括号）

= 2→(2→(4)→2)→2（性质6）

= 2→(2→4→2)→2（去括号）

= 2→(2→(2→(2→(2)→1)→1)→1)→2（规则4）

= 2→(2→(2→(2→2→1)→1)→1)→2（去括号）

= 2→(2→(2→(2→2)))→2（规则3）

= 2→(2→(2→(4)))→2（规则2）

= 2→(2→(16))→2（规则2）

= 2→65536→2（规则2）

= 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1（规则4），其中括号出现65535次

= 2→(2→(2→(...2→(2→(2))...)))（规则3）

= 2→(2→(2→(...2→(4)...)))（规则2）

= 2→(2→(2→(...16...)))（规则2）

（其中2出现 次）（见迭代幂次）

=65536

若用高德纳箭号表示法可得：

(7)2→3→2→2

= 2→3→(2→3)→1（规则4）

= 2→3→8（规则2和规则3）（利用高德纳箭号表示法即为 ）

= 2→(2→2→7)→7（规则4）

= 2→4→7（性质6，利用高德纳箭号表示法即为 ）

= 2→(2→(2→2→6)→6)→6（规则4）

= 2→(2→4→6)→6（性质6）

= 2→(2→(2→(2→2→5)→5)→5)→6（规则4）

= 2→(2→(2→4→5)→5)→6（性质6）

= 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6（规则4）

= 2→(2→(2→(2→4→4)→4)→5)→6（性质6）

= 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4)→5)→6（规则4）

= 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6（性质6）

= 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6（利用前面的例子）

= 大到无法想像的数

高德纳箭号表示法：

(8)3→2→2→2

= 3→2→(3→2)→1（规则4）

= 3→2→9（规则2和规则3）

= 3→3→8（规则4）

高德纳箭号表示法：

(9)3→2→3→3

= 3→2→(3→2→(3→2)→2)→2（规则4）

= 3→2→(3→2→9→2)→2（规则2）

= 3→2→(3→2→(3→2→(...3→2→(3→2)→1...)→1)→1)→2（规则4），其中3→2出现10次，也就是原本的1个，加上括号里的9个。

= 3→2→(3→2→(3→2→(...3→2→(3→2)...)))→2（规则3），3→2出现10次。

= 3→2→(3→2→(3→2→(...3→2→9...)))→2（规则2），3→2出现9次。

= 3→2→(3→2→(3→2→(...3→3→8...)))→2（规则4），3→2出现8次。

= 3→2→(3→2→(3→2→(... ...)))→2（高德纳箭号表示法），3→2出现8次。

= 3→2→(3→2→(3→2→(...3→2→( )...)))→2

= 3→2→(3→2→(3→2→(... ...)))→2（高德纳箭号表示法），3→2出现7次。

= ...

= 3→2→ →2（高德纳箭号表示法）

= 3→2→(3→2→(...3→2→(3→2)→1...)→1)→1（规则4），其中3→2出现 次。

= 3→2→(3→2→(...3→2→(3→2)))（规则3），其中3→2出现 次。

= ，其中向上箭号出现 次。

可见得3→2→3→3为使用高德纳箭号表示法都难以表示的数，这个例子可证明，使用康威链式箭号表示法表示大数的效率会比高德纳箭号表示法高很多（葛立恒数则是另一个例子）。

一般性的例子简单的例子：

，最后利用了性质1。

，最后利用了

，最后利用了 。

对于任何康威链X，设 ，则 （见复合函数）。

设 ，则 ，所以 。

例如 ，进而：

我们可以进一步一般化。假设 ，则 ，就是说 。

根据上面可知， ，以及 ，所以

阿克曼函数阿克曼函数可以使用康威链式箭号表示法来表示：

A(m, n) = (2 → (n + 3) → (m − 2)) − 3 for m > 2

相反的

2 → n → m = A(m + 2,n − 3) + 3 for n > 2

（n=1和n=2有特别的规定，A(m, -2) = -1 以及 A(m, -1) = 1。）

葛立恒数葛立恒数 无法用康威链式箭号表示法来简单的表示，但是可以订出简洁的上下界。设 ，则 ,（见复合函数），可以得到

证明：这里会使用到规则3和规则4：

（这里有64个3→3）

（这里有64个3→3）

（这里有64个3→3）

（这里有65个3→3）

由于是严格递增函数，

这给出了上下界。

利用康威链式箭号表示法，很容易表示远远大于葛立恒数的数：

其中远远大于65，因此远远大于葛立恒数。

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学