Post by 《§》carbonara <3〖ƧƐ〗 on Jun 14, 2015 10:31:07 GMT
Soo, let's start:
f0(n) =n+1
fa+1(n) = fan(n)
fa(n) = fa(n)(n) iff a is a limit ordinal.
Therefore:
f1(n) = 2n
f2(n) > 2n = 2^2
f3(n) > n2 = 2^^2 (2 tetrated to n) = 22222...2 n times
f4(n) > 2^^^n = 2...222222 (n times) = 222...2 (222...2 (222...2 (etc...) times) times (with n layers - crazily big!!!)
fa(n) > 2^^^...(n-1) arrows...^^^n for a < ω
ω = limn->+infinity(n)
According to rule 3, fω(n)=fω(n)(n)
(We take the n-th member of the ω's fundamental sequence)
<=>fω(n)=fn(n)
Theorem: fω(n) grows faster than any primitive-recursive function (any g(x)=a^^^^...^^^^b with a fixed number of arrows)
According to rule 2, fω+1[/sup](n)=fnω(n)
F.e., f=ω+1(5)=fω(fω(fω(fω(fω(5)))))=fffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))
fω+2(5) = fffff5(5)(f5(5))(ff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(ffffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)(f5(5))(ff5(5)(fffffffffff5(5)(f5(5))(ff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(ffffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)(f5(5))(ff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))))(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))))(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))
ABANDON ALL HOPE!!!! xD
fω+3(n)'s growth rate is beyond imagination!!!! And incredibly slow compared to fω+ω(n)...
f0(n) =n+1
fa+1(n) = fan(n)
fa(n) = fa(n)(n) iff a is a limit ordinal.
Therefore:
f1(n) = 2n
f2(n) > 2n = 2^2
f3(n) > n2 = 2^^2 (2 tetrated to n) = 22222...2 n times
f4(n) > 2^^^n = 2...222222 (n times) = 222...2 (222...2 (222...2 (etc...) times) times (with n layers - crazily big!!!)
fa(n) > 2^^^...(n-1) arrows...^^^n for a < ω
ω = limn->+infinity(n)
According to rule 3, fω(n)=fω(n)(n)
(We take the n-th member of the ω's fundamental sequence)
<=>fω(n)=fn(n)
Theorem: fω(n) grows faster than any primitive-recursive function (any g(x)=a^^^^...^^^^b with a fixed number of arrows)
According to rule 2, fω+1[/sup](n)=fnω(n)
F.e., f=ω+1(5)=fω(fω(fω(fω(fω(5)))))=fffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))
fω+2(5) = fffff5(5)(f5(5))(ff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(ffffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)(f5(5))(ff5(5)(fffffffffff5(5)(f5(5))(ff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(ffffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)(f5(5))(ff5(5)(ffffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))))(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))))(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))(5)))(fff5(5)(f5(5))(ff5(5)(f5(5))))(ffff5(5)(f5(5))(ff5(5)(f5(5)))(fff5(5)(f5(5))(ff5(5)(f5(5)))))
ABANDON ALL HOPE!!!! xD
fω+3(n)'s growth rate is beyond imagination!!!! And incredibly slow compared to fω+ω(n)...