大数基础2

这一次来讲高德纳上箭号

计算规则就是 a↑b=a^b a↑n1=a a↑cb=a↑c-1(a↑b-1)

这个递归格式实际上是跟运算级次的意思是一样的。连加就是乘法，连乘就是乘方。高级的运算就是低级运算的多次迭代。

比如3↑↑↑3=3↑↑3↑↑3=3↑↑3↑3↑3=3↑↑3↑27=3↑↑7625597484987,这是一个高达7625597484987个3的指数塔，但它的增长率仅为5

像这种大数就没法用初等函数来表示了，以后我们还会遇到更大的计数方法，如何比较这些数的大小，以及比较这些方法的计数能力就尤为重要了。

FGH（快速增长层级）

FGH有3条规则

f0(n)=n+1

fa(n)=fa-1(fa-1(fa-1(...fa-1(n))))一共n层 a是后继序数（可以被减1）

fb(n)=fn(n) b是极限序数（不可以被减1）

这里f0(0)=1 f0(1)=2 f0(2)=3 f0(3)=4

f1(0)=0 f1(1)=2 f1(2)=4 f1(3)=5

f2(0)=0 f2(1)=2 f2(2)=8 f2(3)=24

f3(0)=0 f3(1)=2 f3(2)=2048 f3(3)=402,653,184*2^402,653,184

f4(0)=0 f4(1)=2 f4(2)>6.6185228434044942951864067458396e+619 f4(3)=f3(f3(402,653,184*2^402,653,184))

显然不是所有的增长函数都在FGH里，但是我们可以认为像3n，4n等一次函数具有1的增长率，n²等幂函数具有1到2之间的增长率，指数函数、阶乘的增长率为2，n^n^n、n^n^n^n具有2到3之间的增长率，2↑↑(n+1)、n↑↑n的增长率为3。这是因为我们考虑的是n趋于无穷时函数增长快慢的性质。增长率就像一个标杆，把各个函数划分为各个层级。

f3(n)  2↑n

f4(n) 2↑↑n

f5(n) 2↑↑↑n

所以高德纳上箭号的极限是n↑nn 增长率为ω 也是fn(n)或fω(n)

葛立恒数是G(64)=3↑G(63)3 G(1)=3↑↑↑↑3 它的增长率是ω+1

注：fω+1(n)不是fn+1(n)(那为什么不写做fω(n+1))fω+1(n)=fω(fω(fω(...fω(n)))) fω(fω(fω(...fω(n))))不是fn(fn(fn(...fn(n)))) 是要从内往外算的。

最后算一下fω+2(2)

fω+2(2)=fω+1(fω+1(2))=fω+1(fω(fω(2)))=fω+1(fω(f2(2)))=fω+1(fω(4)))=fω+1(f4(4))) fω+1(2↑↑5) fω+1(2↑2↑2↑2↑2)  fω+1(2↑2↑2↑4) fω+1(2↑2↑16) fω+1(2↑65536) f(2↑65536) (2↑65536) 

给个赞吧