Fast-growing hierarchy
1. 개요
큰 수들의 크기를 비교할 때 쓰이는 계층구조. FGH는 커지면 커질수록 뭔가가 더 붙는 다른 큰 수 함수들과는 다르게 간결하고 매우 강력하여 큰 수들을 비교할때 요긴하게 쓰인다.
2. 정의 및 설명
- $$ f_0(n) = n+1 $$
- 서수 $$ \alpha $$에 대해 $$ f_{\alpha +1}(n) = f_{\alpha}^n (n) $$
- $$ \alpha $$가 극서수라면 $$ f_{\alpha}(n) = f_{\alpha [n]}(n) $$
- 서수 0에 해당하는 함수는 '다음 수'라는 연산이다.
- 서수가 다른 서수 $$\alpha$$의 다음 서수인 경우, $$\alpha$$에 대응하는 함수를 $$n$$번 합성한다.
- 서수가 더 작은 서수들의 극한서수인 경우, 그 서수를 정의하는 더 작은 서수들의 수열(fundamental sequence)에서 $$n$$번째 서수를 대입한다.
3. 계산 예시
정의에 의해 서수 0에 해당하는 함수는 '다음 수'라는 연산이다. $$ f_0(n) = n+1,\ f_0(100)=101 $$
서수 1에 해당하는 함수는 '다음 수'를 $$n$$번 반복한 것이므로 $$ n+n=2n $$이다. $$ f_1(n) = 2n,\ f_1(100)=200 $$
서수 2에 해당하는 함수는 2배하기를 $$n$$번 반복하는 것이므로[1] $$2 \times 2 \times ... \times 2 \times n = n \times 2^n$$이다. $$f_2(n) = n \times 2^n,\ f_2(100)=100 \times 2^{100} \sim 1.267$$구
서수 3에 해당하는 함수는 $$ n \times 2^n, (n \times 2^n) \times 2^{(n \times 2^n)}, ... $$ 이런식으로 $$n$$번 합성하는 것이다.[2]줄임표를 사용하지 않고 정확하게 나타내기는 힘들고 근삿값은 $$ (2^n)^{(2^n)^{...^{(2^n)}}} $$으로 $$ 2^n \uparrow \uparrow n $$과 같다. $$ \uparrow \uparrow $$의 의미는 커누스 윗화살표 표기법 참고.
서수 4에 해당하는 함수는 위의 함수를 $$ n $$번 합성한 것이므로 근삿값으로 $$ 2 \uparrow \uparrow 2 \uparrow \uparrow.. \uparrow \uparrow n $$이고 이것은 $$ 2 \uparrow \uparrow \uparrow n$$보다 크다.
서수 5에 해당하는 함수는 위의 함수를 $$n$$번 합성한 것이므로 근삿값으로 $$2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow ... \uparrow \uparrow \uparrow n$$이고 이것은 $$2 \uparrow \uparrow \uparrow \uparrow n$$보다 크다. 즉 유한 서수 $$a+1$$에 대한 함수는 대략 크누스의 윗 화살표 표기법으로 화살표가 $$a$$개 있는 것과 비슷하다. (화살표 앞뒤에 붙는 수의 크기는 2 이상이기만 하면 크게 중요하지 않다.)
그러면 윗화살표 표기법만 가지고 모든 단계를 근사할 수 있을까? 아니다. 아직 정의 (3)은 쓰지도 않았다. 여기서 가장 작은 극서수인 $$\omega$$가 등장한다.
서수 $$\omega$$에 해당하는 함수는 정의(3)에 의해 $$\omega$$에 n을 대입해서 n단계 함수가 된다. $$\omega$$의 fundamental sequence의 $$n$$번째 항은 $$n$$이기 때문이다. 즉 $$f_{\omega}(100)=f_{100}(100)$$이다.
서수 $$\omega+1$$ 에 해당하는 함수 $$f_{\omega+1}(n)$$은 절대 $$f_{n+1}(n)$$가 '''아니다'''. $$\omega+1$$은 극서수가 아니기 때문에 정의 (2)에 의하여 $$f_{\omega+1}(n)$$은 $$f_{\omega}(n)$$를 $$n$$번 중첩하는 것인데, $$f_{100}(100)$$을 계산해서 나오는 엄청 큰 수를 $$A$$라고 하면 서수 $$A$$에 해당하는 함수인 $$f_A(A)$$를 계산해야 하고 그 결과를 또 단계에 넣고 하는 것을 100번 반복해야 $$f_{\omega+1}(100)$$이 나온다.
$$f_{\omega2}(n)$$는 $$\omega2$$가 서수의 수열 $$\omega+1, \omega+2, \cdots$$로 정의되기 때문에, 정의 (3)에 의해 $$f_{\omega+n}(n)$$와 같다.[3] 이를 반복하면 $$f_{\omega (m+1)}(n)$$는 $$f_{\omega m+n}$$가 된다.
$$f_{\omega^2}(n)$$는 같은 원리로 정의 (3)을 사용하여 $$f_{\omega n}(n)$$가 되고, $$f_{\omega^\omega}(n)$$는 $$f_{\omega^n}(n)$$이 된다.
이제 몇몇 큰 수들을 이 표기법으로 어떻게 나타낼 수 있는지 알아보자.
구골의 경우, 약간의 계산을 거치면 $$f_{2}(323)=323\times2^{323}\lt10^{100}\lt324\times2^{324}=f_{2}(324)$$임을 알 수 있다. 하지만 서수 3에 대한 함수로는 $$f_{3}(2)=2048\lt10^{100}\lt f_{3}(3)$$이 되어, 비교하는 의미가 없어진다.
스큐스 수의 경우, 대략 $$f_3(4)\lt e^{e^{e^{79}}}\lt f_3(5)\lt f_4(2)$$이다.
그레이엄 수의 경우, 윗 화살표가 $$g_{63}$$개이므로 유한 서수로 나타내기에는 너무 크다. 대신, $$g_{1}=3\uparrow\uparrow\uparrow\uparrow3\lt f_{64}(64)$$에서 시작하여 $$g_{2}\lt f_{f_{64}(64)}(f_{64}(64))$$를 보이고, 이 과정을 64번 반복하면 $$g_{64}\lt f_{\omega+1}(64)$$인 것을 알 수 있다.[4]
이처럼 큰 수들은 그 크기에 "대응"하는 서수를 가지는 경우가 많기 때문에, 큰 수들의 크기를 편리하게 비교할 수 있다.
4. 큰 수의 서열
- 서수 2에 대응: $$f_2(3)=24$$에서 $$f_3(3)\approx2^{402000000}$$까지.
- 서수 3에 대응: $$f_3(3)$$에서 $$f_4(3)$$까지. 테트레이션으로 쉽게 나타낼 수 있는 수들이 여기 대응된다.
- $$\omega$$에 대응: 아커만 함수, 커누스 윗화살표 표기법
- $$\omega+1$$: 모우저, 그레이엄 수
- $$\omega2$$: BEAF에서 {a,b,n,2}
- $$\omega^2$$: 콘웨이 연쇄 화살표 표기법
- $$\omega^2+1$$: 피쉬 수1
- $$\omega^{\omega^{\omega}}$$: BEAF에서 {a,b\(0,1\)2}
- $$\epsilon_0$$: 굿스타인 함수
- $$\psi(\Omega^{\Omega^\omega})$$(작은 베블런 서수): 약한 tree 수열의 값 [5]
5. FGH의 단계
5.1. 오메가 이전 단계
- $$f_{0}(n) = n+1$$
- $$f_{1}(n) = n+n = 2n$$
- $$f_{2}(n) = f{_{1}^{n}}(n) = 2(2(...2(2n))) = 2^{n}n>2 \uparrow n = 2^{n}$$
- $$f_{3}(n) \approx 2^{n} \uparrow \uparrow n > 2 \uparrow \uparrow n$$
- $$f_{4}(n) \approx f_{3}(n) \uparrow\uparrow\uparrow n \geq (2^{n} \uparrow \uparrow n) \uparrow\uparrow\uparrow n$$
- $$f_{m}(n) \approx f_{m-1}(n) \uparrow^{m-1} n \geq ((...(2\uparrow n)\uparrow^2n)\uparrow^3n)...)\uparrow^{m-1} n$$ [6]
5.2. 오메가 단계 1(선형~다항식 단계)
- $$f_{ω}(n)\approx f_{n-1}(n) \uparrow^{n-1} n \geq ((...(2\uparrow n)\uparrow^2n)\uparrow^3n)...)\uparrow^{n-1} n$$
- $$f_{ω+1}(n)=\underbrace {f_{ω}(f_{ω}(f_{ω}(...f_{ω}(n)...)))}_{n}$$
- $$f_{ω+a+1}(n)=\underbrace {f_{ω+a}(f_{ω+a}(f_{ω+a}(...f_{ω+a}(n)...)))}_{n}$$
- $$f_{ω2}(n)=f_{ω+ω}(n)=f_{ω+n}(n)$$
- $$f_{ω3}(n)=f_{ω2+ω}(n)=f_{ω2+n}(n)=\underbrace {f_{ω2+n-1}(f_{ω2+n-1}(f_{ω2+n-1}(...f_{ω2+n-1}(n)...)))}_{n}$$
5.3. 오메가 단계 2(지수화 단계 이상)
- $$f_{ω^2}(n)=f_{ωω}(n)=f_{ωn}(n)=f_{ω(n-1)+ω}(n)$$
- $$f_{ω^3}(n)=f_{ω^2×ω}(n)=f_{ω^2×n}(n)=f_{ω^2×(n-1)+ω^2}(n)$$
- $$f_{ω^ω}(n)=f_{ω^n}(n)=f_{ω^{n-1}×ω}(n)=f_{ω^{n-1}×n}(n)=f_{ω^{n-1}×(n-1)+ω^{n-1}}(n)$$
- $$f_{ω^{ω+1}}(n)=f_{ω^ω×ω}(n)=f_{ω^ω×n}(n)=f_{ω^ω×(n-1)+ω^ω}(n)$$
- $$f_{ω^{ω2}}(n)=f_{ω^{ω+ω}}(n)=f_{ω^{ω+n}}(n)=f_{ω^{ω+(n-1)}×ω}(n)=f_{ω^{ω+(n-1)}×n}(n)=f_{ω^{ω+(n-1)}×(n-1)+ω^{ω+(n-1)}}(n)$$
- $$f_{ω^{ω^2}}(n)=f_{ω^{ωω}}(n)=f_{ω^{ωn}}(n)=f_{ω^{ω(n-1)+ω}}(n)$$
- $$f_{ω^{ω^ω}}(n)=f_{ω^{ω^n}}(n)=f_{ω^{ω^{n-1}×ω}}(n)$$
5.4. 엡실론 단계
$$\epsilon_0$$은 $$\{1,ω,ω^ω,ω^{ω^ω},\cdots\}$$의 극서수이고, $$\epsilon_{a+1}$$은 $$\{\epsilon_a+1,ω^{\epsilon_a+1},ω^{ω^{\epsilon_a+1}},\cdots\}$$의 극서수이다.
- $$f_{\epsilon_0}(n)=f_{ω↑↑(n-1)}(n)$$
- $$f_{\epsilon_{a+1}}(n)=f_{ω^{ω^{\cdot^{\cdot^{\cdot^{\epsilon_a+1}}}}}}(n)$$ ($$ω$$가 $$n-1$$개)[7]
5.5. 제타-에타 단계
- $$f_{\zeta_0}(n)=f_{\epsilon_{\epsilon_{._{._{._{\epsilon_0}}}}}}(n)$$ ($$\epsilon$$가 $$n-1$$개)
- $$f_{\zeta_{a+1}}(n)=f_{\epsilon_{\epsilon_{._{._{._{\zeta_a+1}}}}}}(n)$$ ($$\epsilon$$가 $$n-1$$개)
- $$f_{\eta_0}(n)=f_{\zeta_{\zeta_{._{._{._{\zeta_0}}}}}}(n)=f_{\zeta_{\eta_0}}(n)$$ ($$\zeta$$가 $$n-1$$개)
- $$f_{\eta_{a+1}}(n)=f_{\zeta_{\zeta_{._{._{._{\eta_a+1}}}}}}(n)$$ ($$\zeta$$가 $$n-1$$개)
5.6. 베블런 함수 단계
그리스 문자는 무한하지 않기 때문에, 다음 단계로 나아가기 위해 앞의 극서수들을 일반화한 베블런 함수 $$\varphi(n)$$을 사용한다.
1. $$\varphi_0(a)=\omega^a $$
2. 서수 $$\alpha$$에 대해, $$\varphi_\alpha(0)[n]=\varphi^n_{\alpha-1}(0)$$
3. $$\varphi_\alpha(m)[n]=\varphi^n_{\alpha-1}(\varphi_\alpha(m-1)+1)$$
4. $$\alpha$$가 극서수라면, $$\varphi_\alpha(0)[n]=\varphi_n(0)$$
5. $$\varphi_\alpha(m)[n]=\varphi_n(\varphi_\alpha(m-1)+1)$$
5.6.1. 일변수 파이 단계
- $$f_{\varphi_0(a)}(n)=f_{\omega^a}(n)$$
- $$f_{\varphi_1(a)}(n)=f_{\epsilon_a}(n)$$
- $$f_{\varphi_2(a)}(n)=f_{\zeta_a}(n)$$
- $$f_{\varphi_3(a)}(n)=f_{\eta_a}(n)$$
- $$f_{\varphi_4(0)}(n)=f_{\eta_{\eta_{._{._{._{\eta_0}}}}}}(n)$$ ($$\eta$$가 $$n-1$$개)
- $$f_{\varphi_{\alpha+1}(0)}(n)=f_{\varphi_{\alpha}(\varphi_{\alpha}(...\varphi_{\alpha}(0)...))}(n)$$ ($$\varphi_\alpha$$가 $$n-1$$개)
- $$f_{\varphi_{\alpha+1}(\beta+1)}(n)=f_{\varphi_{\alpha}(\varphi_{\alpha}(...\varphi_{\alpha+1}(\beta)...))}(n)$$ ($$\varphi_\alpha$$가 $$n-1$$개)
- $$f_{\varphi_{\alpha}(\beta)}(n)=f_{\varphi(\alpha,\beta)}(n)$$
5.6.2. 감마 단계
- $$f_{\Gamma_0}(n)=f_{\varphi(1,0,0)}=f_{\varphi_{\varphi_{\varphi_{...\varphi_{0}(0)...}(0)}(0)}(0)}(n)$$ ($$\varphi$$가 $$n-1$$개) $$=f_{\varphi(\varphi(\varphi(...\varphi(0,0)...,0),0),0)}$$) ($$\varphi$$가 $$n-1$$개)
5.6.3. 다변수 파이 단계
- $$f_{\varphi(a,b,c...d,e+1)}(n)=f_{\varphi(a,b,c...d-1,\varphi(a,b,c...d-1,\varphi(a,b,c...d-1,\varphi(a,b,c...d,e)...))}(n)$$ ($$\varphi$$가 $$n-1$$개)
- $$f_{\varphi(a,b,c...d+1,0,0,0...0)}(n)=f_{\varphi(a,b,c...d,\varphi(a,b,c...d,\varphi(a,b,c...d,...\varphi(a,b,c...d,0,0,0...0)...)0,0...0)0,0...0)}(n)$$ ($$\varphi$$가 $$n-1$$개)
- $$f_{\varphi(0,0,0....0,a,b,0,c)}(n)=f_{\varphi(a,b,0,c)}(n)$$
- $$\varphi(1,0,0,0)$$을 아커만 서수라고 하고, $$\varphi(\underbrace{1,0,0,...,0,0)}_\omega$$를 작은 베블런 서수라고 한다.
5.7. 서수 붕괴 함수 단계
이 문서에서는 서수 붕괴 함수가 어떻게 커지는지만 중점적으로 다룬다. 자세한 원리는 서수(수학)/큰 가산서수 문서의 5번째 문단 참고.
5.7.1. 바흐만의 프사이 함수 단계 1
- $$f_{\psi(0)}(n)=f_{\epsilon_0}(n)$$
- $$f_{\psi(1)}(n)=f_{\epsilon_1}(n)$$
- $$f_{\psi(\omega)}(n)=f_{\epsilon_\omega}(n)$$
- $$f_{\psi(\Omega)}(n)=f_{\zeta_0}(n)$$
- $$f_{\psi(\Omega+1)}(n)=f_{\epsilon_{\zeta_0+1}}(n)$$
- $$f_{\psi(\Omega+a)}(n)=f_{\epsilon_{\zeta_0+a}}(n)$$
- $$f_{\psi(\Omega2)}(n)=f_{\psi(\Omega+\Omega)}(n)=f_{\zeta_1}(n)$$
- $$f_{\psi(\Omega3)}(n)=f_{\zeta_2}(n)$$
- $$f_{\psi(\Omega^2)}(n)=f_{\psi(\Omega×\Omega)}(n)=f_{\eta_0}(n)=f_{\varphi_3(0)}(n)$$
- $$f_{\psi({\Omega^2}2)}(n)=f_{\psi(\Omega^2 +\Omega^2)}=f_{\eta_1}(n)$$
- $$f_{\psi(\Omega^3)}=f_{\varphi_4(0)}(n)$$
- $$f_{\psi(\Omega^\omega)}(n)=f_{\varphi_\omega(0)}(n)=f_{\varphi(\omega,0)}(n)$$
- $$f_{\psi(\Omega^\Omega)}(n)=f_{\varphi(1,0,0)}(n)=f_{\Gamma_0}(n)$$
- $$f_{\psi(\Omega^{\Omega^2})}(n)=f_{\varphi(1,0,0,0)}(n)$$
- $$f_{\psi(\Omega^{\Omega^\omega})}(n)=f_{\varphi(1,\underbrace{0,0,...,0,0)}_\omega}(n)$$
- $$f_{\psi(\Omega^{\Omega^\Omega})}(n)$$
5.7.2. 바흐만의 프사이 함수 단계 2
- $$f_{\psi_1(0)}(n)=f_{\psi(\epsilon_{\Omega+1})}(n)=f_{\psi(\Omega^{\Omega^{\Omega^{^{.^{.^.}}}}})}(n)$$
- $$f_{\psi_1(1)}(n)=f_{\psi(\epsilon_{\Omega+2})}(n)$$
- $$f_{\psi_1(\Omega)}(n)=f_{\psi(\zeta_{\Omega+1})}(n)$$
- $$f_{\psi_1(\Omega^2)}(n)=f_{\psi(\eta_{\Omega+1})}(n)$$
- $$f_{\psi_1(\Omega^{\Omega})}(n)=f_{\psi(\Gamma_{\Omega+1})}(n)$$
- $$f_{\psi_2(0)}(n)=f_{\psi_1({\epsilon_{\Omega+1}})}(n)=f_{\psi_1(\Omega^{\Omega^{\Omega^{^{.^{.^.}}}}})}(n)$$
- $$f_{\psi_{\psi(0)}(0)}(n)=f_{\psi_{\epsilon_0}(0)}(n)=f_{\psi_{\omega^{\omega^{\omega^{.^{.^.}}}}}(0)}(n)$$
- $$f_{\psi_{\psi_1(0)}(0)}(n)=f_{\psi_{\psi(\epsilon_{\Omega+1})}(0)}(n)=f_{\psi_{\psi(\Omega^{\Omega^{.^{.^.}}})}(0)}(n)$$
- $$f_{\psi_{\psi_{\psi(0)}(0)}(0)}(n)=f_{\psi_{\psi_{\epsilon_0}(0)}(0)}(n)$$
6. 왜 3이 기준인가?
$$\Gamma_0$$에 대해, $$f_{\Gamma_0}(2)$$를 구해보자. 이 서수는 $$\{1, \varphi_1(0), \varphi_{ \varphi_1(0)}(0), \varphi_{ \varphi_{ \varphi_1(0)}(0)}(0), \cdots\}$$의 극서수이므로 이것은 $$f_{\varphi_1(0)}(2)=f_{\epsilon_0}(2)$$과 같다. $$\epsilon_0$$은 $$\{1, \omega, \omega^\omega, \omega^{\omega^\omega} \cdots\}$$의 극서수라서, 이것은 $$f_{\omega}(2)$$와 같고, $$f_{\omega}(2)=f_{2}(2)=8$$이 된다. 이렇듯 많은 극서수를 정의하는 수열이 1부터 시작하므로, 2 이하의 수는 계산이 너무 쉽게 끝나게 된다. 만약 $$\Gamma_0+1$$과 같이 극서수가 아니라 따름서수라면 $$f_{\Gamma_0+1}(2)=f_{\Gamma_0}(f_{\Gamma_0}(2))=f_{\Gamma_0}(8)$$처럼 재귀를 통해 값이 3 이상이 되어 그나마 낫다.
나아가서 1을 넣으면 서수가 무엇이든 결과값이 2로 고정된다. fundamental sequence가 1로 시작하는 극서수[8]인 $$\alpha$$에 대해 $$f_\alpha(1)$$를 계산하면 $$f_1(1)=f_0(1)=2$$가 된다. $$\alpha$$가 따름서수라도 한번만 재귀하게 되어 $$f_{\alpha}(1)=f_{\alpha-1}(1)$$이므로 재귀를 통해 값을 늘릴 수도 없다.
7. 관련 항목
[1] $$n$$을 $$n$$번 더하는게 아니라 '자기 자신을 더하는 것'을 $$n$$번 반복하는 것임에 유의해야 한다.[2] 예를 들어 $$f_3(3)$$은 $$(3×2^3)×2^{(3×2^3)})×2^{((3×2^3)×2^{(3×2^3)})})$$과 같고 이는 $$24×2^{24}×2^{24×2^{24}}$$ 이므로 약 $$6.89×10^{121210694}$$이다.[3] $$2 \times \omega$$라고 쓰면 안된다. 서수 연산에서는 교환법칙이 성립하지 않아서, $$ 2 \times \omega$$와 $$ \omega$$가 같다.[4] 더 정확히는 $$f^{63}_{\omega}(4)$$로 근사할 수 있다.[5] 정작 유명한 TREE(3)은 정확한 크기가 측정되지 않았다.[6] 여기서 $$\uparrow^{m-1}$$은 윗방향 화살표가 $$m-1$$개 있다는 뜻이다.[7] $$\epsilon_a$$다음에 나오는 $$+1$$의 위치에 유의한다.[8] 그렇지 않은 극서수도 있다. 예를 들어 $$\omega2$$는 $$\omega+1$$로 시작한다. 그러나 이렇게 따름서수가 되더라도 $$\omega+1$$에서 $$+1$$은 사라지고 값은 늘리지 못한채 더 작은 극서수(이 경우에는 $$\omega$$)가 되어 끝내는 1이 된다.