这个《大数入门》的错漏太多了,所以初学者才会有某些疑问。
先说2.
不可计算函数的增长率不一定快于一切可计算的函数。有的不可计算函数,增长率快于一切可计算的函数,比如Σ函数;有的不可计算函数,增长率并不快,比如Σ函数的一种逆——“写入n个格子所需的2色图灵机的最小状态数”函数。
再说1.
E
# 记号的表述是有问题的。按照《大数入门》里的表述,在#^^# 之后就会出现这样的问题:
a^^(b+1) = a^(a^^b),所以按照这个定义,Ea#^^(
#+1)b 应该展开成Ea#^(
#^^#)b ,然后就是Ea
#^(#^^b)a ,大概只有Ea
#^^#(b+1) 这么点增长率,比Ea
#^^#*#b 还弱,没有太大的提升。
其根本原因在于,像# 、ω、X这样的符号,它们的威力在于它们展开时的数值能够随着表达式中的底数的增大而增大。这次ω展开成2,下次可以展开成8,下下次可以展开成比Graham数还大的数,诸如此类(如果你知道Goodstein序列,你会对此有一点体会)。如果把ω、X这样的符号套进超运算里面,因为a{c}b = a{c-1}(a{c}(b-1)),接着立刻就得展开a{c}(b-1)。照这样不断地递归下去,b总是会下降到所有的ω都被展开的程度;更重要的是,这些下降的过程是连续进行的,不等待底数的增加就进行,就会导致所有的ω都展开成同一个数,从而失去了它原有的威力。
E# 记号的真正定义,采用了一个复杂的算符:">"算符。按照真正的定义,
#^^## 会展开成
#^^#>
#^^#>…
#^^#>
#^^# ,其中
#^^#># 又能展开成((…(
#^^#)^^#…)^^#)^^# ,这样中间的(
#^^#) 就得很久以后才会被再次展开,从而下一次展开的时候能被更大的数替代。
顺带一提,基于同样的缘由,BEAF在n^^n&n以后就无法继续定义下去了。不建议阅读。
最后说3.
对角化并非序数的专利,而是几乎所有大数记号之中都会自然而然出现的一种方式。
就拿fast-growing hierarchy(就是《大数入门》里用到序数的那个记号)来说好了。f_0(n) = n+1,f_1(n) = 2n,f_2(n) = n×2^n,它们的函数名分别为f_0、f_1、f_2。
f_n(n)可以超越一切f_k(n)(其中的k为固定值,n为自变量)。不论k取多少,自变量n总是会有超过k的时候,那时便有f_n(n) > f_k(n)。这一点和Cantor最初在对角论证法中的说明有些类似,因而得名。
但是,f_n可不能作为一个函数的记号,因为这里面还有n这个自变量。可是无论把这个字母“n”换成什么数字,都会落入f_k(n)那样的境地。于是,我们需要一个新的记号去表示能够随时随地转化成“任意大的”n的东西。这个记号在fast-growing hierarchy里是ω,在E# 记号里是# ,在BEAF里则是X。