1. 개요
큰 수들의 크기를 비교할 때 쓰이는 계층구조.[1] FGH는 커지면 커질수록 뭔가가 더 붙는 다른 큰 수 함수들과는 다르게[2] 간결하고 매우 강력하여 큰 수들을 비교할때 요긴하게 쓰인다.2. 정의 및 설명
Fast-growing hierarchy[3]는 서수 [math(\mu)]와 기본 수열(fundamental sequence)[4] [math(S:\mu\cap\text{Lim}\rightarrow(\mathbb{N}\rightarrow\mu))][5]로 구성된다.- [math( f_0(n) = n+1 )]
- 서수 [math( \alpha )]에 대해, [math( f_{\alpha +1}(n) = f_{\alpha}^n (n) )]
- [math( \alpha )]가 극한 서수라면, [math( f_{\alpha}(n) = f_{\alpha [n]}(n) )]
- 서수 0에 해당하는 함수는 '다음 수'라는 연산이다.
- 서수가 다른 서수 [math(\alpha)]의 다음 서수인 경우, [math(\alpha)]에 대응하는 함수를 [math(n)]번 합성한다.
- 서수가 더 작은 서수들의 극한 서수인 경우, 기본 수열에서 [math(n)]번째 서수를 대입한다.
3. FGH의 기본 수열
상술했듯 FGH에서 초한서수를 이용하기 위해서는 기본 수열을 명시하지 않았을 때 [math(\alpha[n])]이 무엇인지 알 수가 없기 때문에 반드시 그 서수들의 기본 수열을 정의해야 한다.[6] 따라서 표준적인 FGH에서는 기본 수열을 아래와 같이 정한다.3.1. 웨이너 계층(Wainer hierarchy)
이 문서에서 쓰일 작은 가산 서수의 기본 수열이다.- [math(\omega[n]=n)]
- [math(\omega^{\alpha + 1}[n] = \omega^\alpha n)]
- [math(\omega^{\alpha}[n] = \omega^{\alpha[n]})] ([math(\alpha)]가 극한 서수일 경우.)
- [math((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k}[n])] (단, [math(\alpha_ 1 \geq \alpha_2 \geq \cdots \geq \alpha_{k - 1} \geq \alpha_k)])
- [math(\epsilon_0[0]=0)]
- [math(\epsilon_0[n+1]=\omega^{\epsilon_0[n]})]
이 기본 수열을 이용해서 칸토어 일반형(Cantor normal form)으로 이루어진 서수의 FGH를 계산 할 수 있다. 예를 들어, [math(f_{\omega^{\omega+1}+\omega^\omega}(3))]은 다음과 같이 계산된다.
[math(f_{\omega^{\omega+1}+\omega^\omega}(3))]
[math(=f_{(\omega^{\omega+1}+\omega^\omega)[3]}(3))]
[math(=f_{\omega^{\omega+1}+\omega^\omega[3]}(3))] ( 4번 규칙 적용)
[math(=f_{\omega^{\omega+1}+\omega^3[3]}(3))] ( 3번 규칙 적용)
[math(=f_{\omega^{\omega+1}+\omega^23}(3))] ( 2번 규칙 적용)
[math(=f_{\omega^{\omega+1}+\omega^22+\omega^2[3]}(3))] (전개)
[math(=f_{(\omega^{\omega+1}+\omega^22+\omega3)[3]}(3))] ( 2번 규칙 적용)
[math(=f_{(\omega^{\omega+1}+\omega^22+\omega2+\omega)[3]}(3))] (전개)
[math(=f_{\omega^{\omega+1}+\omega^22+\omega2+\omega[3]}(3))] ( 4번 규칙 적용)
[math(=f_{\omega^{\omega+1}+\omega^22+\omega2+3}(3))] ( 1번 규칙 적용)
3.2. 베블런 함수(Veblen function)
베블런 함수의 기본 수열이다.[math(z)]는 0으로 이루어진 문자열이다.
- [math((\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k))[n]=\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k)[n])]
- [math(\varphi(\gamma)[n]=\left\{\begin{array}{lcr} n \quad \text{if} \quad \gamma=1\\ \varphi(\gamma-1)\cdot n \quad \text{if} \quad \gamma \quad \text{is a successor ordinal}\\ \varphi(\gamma[n]) \quad \text{if} \quad \gamma \quad \text{is a limit ordinal}\\ \end{array}\right.)]
- [math(\varphi(s,\beta,z,0)[0]=0)], [math(\varphi(s,\beta,z,0)[n+1]=\varphi(s,\beta-1,\varphi(s,\beta,z,0)[n],z))][7]
- [math(\varphi(s,\beta,z,\gamma)[0]=\varphi(s,\beta,z,\gamma-1)+1)], [math(\varphi(s,\beta,z,\gamma)[n+1]=\varphi(s,\beta-1,\varphi(s,\beta,z,\gamma)[n],z))][8]
- [math(\varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta,z,\gamma[n]))][9]
- [math(\varphi(s,\beta,z,0)[n]=\varphi(s,\beta[n],z,0))][10]
- [math(\varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta[n],\varphi(s,\beta,z,\gamma-1)+1,z))][11]
3.3. 서수 붕괴 함수(Ordinal collapsing function)
큰 가산 서수 항목에는 TFBO(Takeuti-Feferman-Buchholz ordinal)까지만 서술되어 있는데 그 이후의 표기법도 상당히 많지만 간단하게 어떤 표기법이 쓰여졌는지만 서술한다.
먼저 TFBO 다음엔 부츠홀츠의 확장 붕괴 함수를 사용하여 오메가 밑첨자를 끝없이 내린다. 이후의 표기법에 대해서 googology 사이트 내에서도 가장 오해가 많은데 Rathjen's Φ function를 사용하는게 맞는 표현법이다. 다만 많은 유저들이 그저 접근 불가능 기수인 I를 사용하고 있다.
그 이후에는 I를 대각화하기 위해 말로 기수를 기반으로 하는 함수가 사용되고 그 이후엔 말로 함수를 대각화하기 위해 약 콤팩트 기수를 기반으로 하는 Rathjen psi 함수( 둘의 표기법이 조금 다르다. ) 그 다음엔 stegert 함수가 사용되는 표기법이 상당히 복잡하다. 여기까지가 제대로 정의된 가장 큰 함수라고 할 수 있다.
사실 FGH가 자주 쓰이는 googology에서 볼 수 있는 거의 모든 수들은 Denis Maksudov라는 유저가 만들었다. Denis Maksudov가 만든 숫자들을 보면 말로 기수 단계의 수 이후에 바로 타르 함수로 넘어가는데 타르 함수는 Taranovsky's C를 사용하여 만들어졌다. 확실한 증거는 없지만 타르 함수는 2차 산술의 증명재귀 서수보다 성장률이 빠를것으로 기대된다. 기대가 맞다면 타르 함수는 말로 기수 단계마저도 먼지로 만들어버리고도 한참 남을 정도로 거대한 수이며 그 이후에 약 콤팩트 기수, stegert의 함수들까지 모두 압도해버린다고 할 수 있다.
3.4. 계산 불가능한 FGH 함수
가장 작은 비재귀적인 서수인 처치-클레이니 서수(Church-Kleene ordinal) [math(\omega^\text{CK}_1)]를 이용한 fgh 함수인 [math(f_{\omega_1^\text{CK}}(n))]은 계산 불가능하며, 이 서수의 기본 수열은 클린의 [math(\mathcal O)]로 정의되어진다. 이 함수의 성장률은 바쁜 비버 함수에 근사할 것으로 예상되나, 현재까지는 성장률이 [math(f_{\omega}(n))]보다 강력하다는 것만 증명되었을 뿐 정확한 성장률은 증명된 바 없다. 또한 [math(\omega^\text{CK}_2,\ \omega^\text{CK}_3,\ \omega^\text{CK}_\omega,\ \omega^\text{CK}_{\epsilon_0})]같은 확장이나, [math(\omega^\text{CK}_{\omega^\text{CK}_1})]같은4. FGH의 단계
5. 계산 예시
정의에 의해 서수 0에 해당하는 함수는 '다음 수'라는 연산이다. [math( f_0(n) = n+1,\ f_0(100)=101 )]서수 1에 해당하는 함수는 '다음 수'를 [math(n)]번 반복한 것이므로 [math( f_1(n) = n+n = 2n,\ f_1(100)=200 )]
서수 2에 해당하는 함수는 2배하기를 [math(n)]번 반복하는 것이므로[12] [math(2 \times 2 \times ... \times 2 \times n = n \times 2^n)]이다. [math(f_2(n) = n \times 2^n,\ f_2(100)=100 \times 2^{100} \sim 1.26765 × 10^{32})]
서수 3에 해당하는 함수는 [math( n \times 2^n, (n \times 2^n) \times 2^{(n \times 2^n)}, ... )] 이런식으로 [math(n)]번 합성하는 것이다.[13]줄임표를 사용하지 않고 정확하게 나타내기는 힘들고 근삿값은 [math(2^nn((2^{2^nn}\uparrow\uparrow(n-1)))] 정도이다.[math( \uparrow \uparrow )]의 의미는 커누스 윗화살표 표기법 참고.
서수 4에 해당하는 함수는 위의 함수를 [math(n)]번 합성한 것이므로 근삿값으로 [math( 2 \uparrow \uparrow 2 \uparrow \uparrow.. \uparrow \uparrow n )]이고 이것은 [math( 2 \uparrow \uparrow \uparrow n)]보다 크다.
서수 5에 해당하는 함수는 위의 함수를 [math(n)]번 합성한 것이므로 근삿값으로 [math(2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow ... \uparrow \uparrow \uparrow n)]이고 이것은 [math(2 \uparrow \uparrow \uparrow \uparrow n)]보다 크다. 즉 유한 서수 [math(\alpha+1)]에 대한 함수는 대략 커누스 윗화살표 표기법으로 화살표가 [math(\alpha)]개 있는 것과 비슷하다. ( 화살표 앞뒤에 붙는 수의 크기는 2 이상이기만 하면 크게 중요하지 않다.)
일반적으로 [math(2<m<\omega)]인 서수 [math(m)]에 대해 다음이 성립한다.
[math(f_{m+1}(n)>f_{m}(n)\uparrow^{m} n>2\uparrow^{m} n)]
그렇다면 따름 서수만 가지고 모든 단계를 근사할 수 있을까? 아니다. 아직 정의 ( 3)은 쓰지도 않았다. 여기서 가장 작은 극 서수인 [math(\omega)]가 등장한다.
서수 [math(\omega)]에 해당하는 함수는 정의( 3)에 의해 [math(\omega)]에 n을 대입해서 n단계 함수가 된다. [math(\omega)]의 fundamental sequence의 [math(n)]번째 항은 [math(n)]이기 때문이다. 즉 [math(f_{\omega}(100)=f_{100}(100))]이다.
서수 [math(\omega+1)] 에 해당하는 함수 [math(f_{\omega+1}(n))]은 절대 [math(f_{n+1}(n))]가 아니다. [math(\omega+1)]은 극 서수가 아니기 때문에 정의 ( 2)에 의하여 [math(f_{\omega+1}(n) = f^n_{\omega}(n))]이므로 [math(f_{100}(100))]을 계산해서 나오는 엄청 큰 수를 [math(A_1)]라고 하면 서수 [math(A_1)]에 해당하는 함수인 [math(f_{A_1}(A_1))]를 계산해서 나온 결과를 [math(A_2)]라 하는 식으로 반복해서 [math(A_{100})]에 도달해야 [math(f_{\omega+1}(100))]이 나온다. 또한 이 [math(f_{\omega+1}(100))]은 그레이엄 수보다도 커진다.
[math(f_{\omega2}(n))]는 [math(\omega2)]가 서수의 수열 [math(\omega+1, \omega+2, \cdots)]로 정의되기 때문에, 정의 ( 3)에 의해 [math(f_{\omega+n}(n))]와 같다.[14] 이를 반복하면 [math(f_{\omega (m+1)}(n))]는 [math(f_{\omega m+n})]가 된다.
[math(f_{\omega^2}(n))]는 같은 원리로 정의 ( 3)을 사용하여 [math(f_{\omega n}(n))]가 되고, [math(f_{\omega^\omega}(n))]는 [math(f_{\omega^n}(n))]이 된다.
이제 몇몇 큰 수들을 이 표기법으로 어떻게 나타낼 수 있는지 알아보자.
구골의 경우, 약간의 계산을 거치면 [math(f_{2}(323)=323\times2^{323}\lt10^{100}\lt324\times2^{324}=f_{2}(324))]임을 알 수 있다. 하지만 서수 3에 대한 [>함수]]로는 [math(f_{3}(2)=2048\lt10^{100}\lt f_{3}(3))]이 되어, 비교하는 의미가 없어진다.[15]
스큐스 수의 경우, 대략 [math(f_3(4)\lt e^{e^{e^{79}}}\lt f_3(5))]이다.
그레이엄 수의 경우, 윗 화살표가 [math(g_{63})]개이므로 유한 서수로 나타내기에는 너무 크다. 대신, [math(g_{1}=3\uparrow\uparrow\uparrow\uparrow3\lt f_{64}(64))]에서 시작하여 [math(g_{2}\lt f_{f_{64}(64)}(f_{64}(64)))]를 보이고, 이 과정을 64번 반복하면 [math(g_{64}\lt f_{\omega+1}(64))]인 것을 알 수 있다.[16]
하이퍼 그레이엄은, 그레이엄 수가 [math(f_{\omega+1}(64))]라고 근사했으므로 그레이엄 수를 그레이엄 수번 재귀한 하이퍼 그레이엄 은 [math(f_{\omega+1}^{f_{\omega+1}(64)}(64))]이고, 이건 [math(f_{\omega+1}^{f_{\omega+1}(64)}(f_{\omega+1}(64))=f_{\omega+2}(f_{\omega+1}(64)))]보다 작으므로 하이퍼 그레이엄[math(<f_{\omega+2}(f_{\omega+1}(64)))]이다.
이처럼 큰 수나 빠르게 증가하는 함수들은 그 크기나 성장률에 "대응"하는 서수를 가지는 경우가 많기 때문에, 큰 수나 빠르게 증가하는 함수들의 크기와 성장률을 편리하게 비교할 수 있다.
6. 큰 수의 서열
- 서수 2에 대응: [math(f_2(3)=24)]에서 [math(f_3(3)\approx 6.89×10^{121210694})]까지. 여기는 일상적인 큰 수의 범위라고 할 수 있다.
- 서수 3에 대응: [math(f_3(3))]에서 [math(f_4(3))]까지. 테트레이션으로 쉽게 나타낼 수 있는 수들이 여기 대응된다. 현재로서는 수학 이외의 학문( 통계역학 등)에서 유의미한 큰 수의 마지노선이라고 할 수 있다.
- [math(\omega)]에 대응: 아커만 함수, 모우저, 커누스 윗화살표 표기법
- [math(\omega+1)]: BEAF에서 {a,b,1,2}, 그레이엄 수
- [math(\omega+2)]: BEAF에서 {a,b,2,2}, 하이퍼 그레이엄[17]
- [math(\omega2)]: BEAF에서 {a,b,n,2}, 그레이엄 재귀 함수 성장률 한계치
- [math(\omega^2)]: 콘웨이 연쇄 화살표 표기법, BEAF에서 {a,b,n,n}[18]
- [math(\omega^2+1)]: 피쉬 수 1
- [math(\omega^3)]: 피쉬 수 2
- [math(\omega^{\omega})]: 약한 굿스타인 수열의 최대값, 피쉬 수 3
- [math(\omega^{\omega^{\omega}})]: BEAF에서 {a,b\(0,1\)2}[19]
- [math(\epsilon_0)]: 굿스타인 함수, 피쉬 수 5
- [math(\zeta_0)]: 피쉬 수 6 함수의 성장률
- [math(\psi(\Omega^{\Omega^\omega}))], [math(\theta(\Omega^\omega))], [math(\vartheta(\Omega^\omega))] ( 작은 베블런 서수): 약한 tree 수열의 성장률
- [math(\psi(\Omega^{\Omega^\omega \omega}))], [math(\theta(\Omega^\omega \omega))], [math(\vartheta(\Omega^\omega \omega))]: TREE(n) 함수의 근사적인 성장률
- [math(\psi_0(\Omega_\omega))], [math(\theta(\Omega_\omega))]: SCG(n) 함수의 근사적인 성장률
- [math(\psi(\psi_I(0)))]: sgh 성장률의 한계[20]
- [math(\psi(\psi_{I_\omega}(0)))] ~ [math(\psi({I_\omega}))]: 바시쿠 행렬 체계의 최소 성장률, BIGG의 근사치[21]
7. 왜 3이 기준인가?
[math(\Gamma_0)]에 대해, [math(f_{\Gamma_0}(2))]를 구해보자. 이 서수는 [math(\{1, \varphi_1(0), \varphi_{ \varphi_1(0)}(0), \varphi_{ \varphi_{ \varphi_1(0)}(0)}(0), \cdots\})]의 극 서수이므로 이것은 [math(f_{\varphi_1(0)}(2)=f_{\epsilon_0}(2))]과 같다. [math(\epsilon_0)]은 [math(\{1, \omega, \omega^\omega, \omega^{\omega^\omega} \cdots\})]의 극 서수라서, 이것은 [math(f_{\omega}(2))]와 같고, [math(f_{\omega}(2)=f_{2}(2)=8)]이 된다. 이렇듯 많은 극 서수를 정의하는 수열이 1부터 시작하므로, 2 이하의 수는 계산이 너무 쉽게 끝나게 된다. 만약 [math(\Gamma_0+1)]과 같이 극 서수가 아니라 따름 서수라면 [math(f_{\Gamma_0+1}(2)=f_{\Gamma_0}(f_{\Gamma_0}(2))=f_{\Gamma_0}(8))]처럼 재귀를 통해 값이 안쪽의 값이 3 이상이 된 채 다시 계산하게 되어 그나마 낫다.[22]나아가서 1을 넣으면 어느 가산 서수이던 결과값이 2로 고정된다.[23] 0의 경우 1이 되는 것은 말할 필요도 없다. fundamental sequence가 1로 시작하는 극 서수[24]인 [math(\alpha)]에 대해 [math(f_\alpha(1))]를 계산하면 [math(f_1(1)=f_0(1)=2)]가 된다. [math(\alpha)]가 따름 서수라도 한번만 재귀하게 되어 [math(f_{\alpha}(1)=f_{\alpha-1}(1))]이므로 재귀를 통해 값을 늘릴 수도 없다.
8. 관련 문서
[1]
이름부터 Fast Growing hierarchy(고속 성장하는 계층구조)다.
[2]
대신
서수의 정의가 조금씩 더 복잡해지긴 한다.
[3]
한국어로 번역하자면 "급성장 계층" 정도가 된다.
[4]
극한
서수를 이루는 더 작은 서수들의 표준적인 수열
[5]
[math(S(\alpha)(n))]은 편의상 [math(\alpha[n])]으로 나타내고, [math(\text{Lim})]는
극한
서수의 모임이다.
[6]
예를 들어, [math(\{1,2939,\omega,\omega+1,\omega+2,....\})]의
극한
서수나 [math(\{\omega+1,\omega+2,\omega+3,....\})]의
극한
서수나 똑같은 [math(\omega2)]이다.
표준적인
수열을 정의해 놓지 않는다면 [math(\omega2[2])]는 [math(2939)]나 [math(\omega+2)]가 모두 가능하게 된다.
[7]
[math(\beta)]가 따름
서수일 경우.
[8]
[math(\gamma,\beta)]가 따름
서수일 경우.
[9]
[math(\gamma)]가
극한
서수일 경우.
[10]
[math(\beta)]가
극한
서수일 경우.
[11]
[math(\gamma)]가 따름
서수이고 [math(\beta)]가
극한
서수일 경우.
[12]
[math(n)]을 [math(n)]번 더하는게 아니라 '자기 자신을 더하는 것'을 [math(n)]번 반복하는 것임에 유의해야 한다.
[13]
예를 들어 [math(f_3(3))]은 [math((3×2^3)×2^{(3×2^3)})×2^{((3×2^3)×2^{(3×2^3)})}))]과 같고 이는 [math(24×2^{24}×2^{24×2^{24}})] 이므로 약 [math(6.89×10^{121210694})]이다.
[14]
[math(2 \times \omega)]라고 쓰면 안된다.
서수
연산에서는
교환법칙이 성립하지 않아서, [math(\omega=2\omega\not = \omega2)]이다.
[15]
저
수는 자릿수가
1
억 자리를 넘는다.
서수
4 이상부터는 그냥
말이 필요없다.
[16]
더 정확히는 [math(f^{64}_{\omega}(4))]보다 크고 [math(f^{64}_{\omega}(5))]보다는
작은 수로 근사할 수 있다.
[17]
이는
그레이엄 수를
그레이엄 수 번 재귀한
숫자다.
BEAF로는 {3,G(64),2,2} 에서 {3,G(64)+1,2,2}에 근사한다.
[18]
n =
3일 경우인 {3,3,3,3}만 해도
그레이엄 수를
그레이엄 수 만큼 재귀한 하이퍼 그레이엄 조차도
먼지로 만들어버리고도 한참 남고도 썩어
우주를 돌고도 또 남을만큼을 만큼 매우 크다. 참고로 {5,5,5,5} 이상이면
덧셈,
곱셈,
지수,
화살표, 그레이엄
함수, 그레이엄 재귀 식으로 단계를 올리고 다시 단계의
수를 재귀하는 것을 바로 전단계에 나온
수만큼 올리는 식으로는 택도 없을 만큼 무섭게 커져버린다.
[19]
여기서부터
그레이엄 수보다 더 많은
숫자가 배열 내에 들어간다.
[20]
정확하겐 이를 넘어가면 fgh와 값이 별 차이가 없다.
[21]
대략 [math(f_{\psi(\psi_{I_\omega}(0))}(200))] 정도 된다.
[22]
이
수는
그레이엄 수,
BEAF의 차원 배열, 계산 가능한
피쉬 수들 따위로는 비교할
수 없다.
[23]
비유하자면
경우의 수가 충분히 많은
게임에서 연속으로 같은 경우가 나오는 것을 생각해보자. 아무리
경우의 수가 많아도 어차피 처음의 것은 아무거나 나와도 되기 때문에 연속되는 횟수가 최소
2회는 되어야 한다. 물론
TREE(3)같이 넣은
수가 특정 값을 넘어가는 순간 상상도 할
수 없을 정도로 커지는 게 아닌 이상 fgh의
성장률을 따라잡기는 무리다.
[24]
그렇지 않은 극
서수도 있다. 예를 들어 [math(\omega2)]는 [math(\omega+1)]로 시작한다. 그러나 이렇게 따름
서수가 되더라도 [math(\omega+1)]에서 [math(+1)]은 사라지고 값은 늘리지 못한채 더 작은 극
서수(이 경우에는 [math(\omega)])가 되어 끝내는
1이 된다.