Slow-growing hierarchy

1. 개요[편집]

---

큰 수들의 크기를 비교할 때 쓰이는 계층구조. 이름처럼 fgh와는 차원이 다른 수준으로 매우 느리게 증가한다.[1] 따라서 작은 서수로는 큰 수를 비교할때 쓰이지 않고, 서수 그 자체의 크기를 알아볼 때 쓰인다.

2. 정의 및 설명[편집]

---

1. [math( g_0(n) = 0 )]
2. 서수 [math( \alpha )]에 대해 [math( g_{\alpha +1}(n) = g_{\alpha} (n)+1 )]
3. [math( \alpha )]가 극서수라면 [math( g_{\alpha}(n) = g_{\alpha [n]}(n) )]

이해를 돕기 위해서 정의를 풀어서 다시 쓰면 다음과 같다.

1. 서수 0에 해당하는 함수는 0으로 고정된다.
2. 서수가 다른 서수 [math(\alpha)]의 다음 서수인 경우, [math(\alpha)]에 대응하는 함수에 '다음 수'라는 연산을 한다.
3. 서수가 더 작은 서수들의 극한서수인 경우, 기본 수열에서 [math(n)]번째 서수를 대입한다.

각 단계는 하나의 함수를 가리킨다. 이 함수의 특징은 서수의 크기의 기준을 [math(\omega)]에서 [math(n)]으로 변환한 것이다. 앞서 말했듯 sgh는 비교적 작은 서수에 대해서는 매우 느리게 증가하므로 큰 수를 근사하는 데에는 적합하지 않고, 근사값으로 서수의 크기를 알아내서 fgh의 단계로 환산하는 활용을 하는 용도로 쓰인다.

3. 계산 예시[편집]

---

[math(=)]은 참값, [math(≒)][2]은 근사값을 의미한다.

• [math(g_{0}(n) = 0)]
• [math(g_{1}(n) = 1)]
• [math(g_{m}(n) = m)]
• [math(g_{\omega}(n) = n)]
• [math(g_{\omega+m}(n) = n+m)]
• [math(g_{\omega2}(n) = 2n)]
• [math(g_{\omega m}(n) = nm)]
• [math(g_{\omega^2}(n) = n^2)]
• [math(g_{\omega^\omega}(n) = n^n)]
• [math(g_{\omega^{\omega^\omega}}(n) = n^{n^n})]
• [math(g_{\epsilon_0}(n) = n↑↑(n-1))](↑는 커누스 윗화살표 표기법)
• [math(g_{\epsilon_1}(n) ≒ n↑↑((n-1)2))]
• [math(g_{\epsilon_{m}}(n) ≒ n↑↑((n-1)(m+1)))]
• [math(g_{\epsilon_{\omega}}(n) ≒ n↑↑n^2)]
• [math(g_{\epsilon_{\omega^m}}(n) ≒ n↑↑n^{m+1})]
• [math(g_{\epsilon_{\epsilon_{0}}}(n) ≒ n↑↑n↑↑(n-1))]
• [math(g_{\zeta_{0}}(n) ≒ n↑↑↑n)]
• [math(g_{\zeta_{1}}(n) ≒ n↑↑↑n2)]
• [math(g_{\zeta_{m}}(n) ≒ n↑↑↑n(m+1))]
• [math(g_{\zeta_{\omega}}(n) ≒ n↑↑↑n^2)]
• [math(g_{\zeta_{\zeta_{0}}}(n) ≒ n↑↑↑n↑↑↑n)]
• [math(g_{\eta_0}(n) ≒ n↑^4n)]
• [math(g_{\varphi(4,0)}(n) ≒ n↑^5n)]
• [math(g_{\varphi(m,0)}(n) ≒ n↑^{m+1}n)]
• [math(g_{\varphi(\omega,0)}(n) ≒ n↑^{n+1}n ≒ f_{\omega}(n))]([math(f)]는 fgh)
• [math(g_{\varphi(\varphi(\omega,0),0)}(n) ≒ f_{\omega}(f_{\omega}(n)))]
• [math(g_{\Gamma_0}(n) = g_{\varphi(1,0,0)}(n) ≒ f_{\omega+1}(n))]
• [math(g_{\varphi(1,1,0)}(n) ≒ f_{\omega+2}(n))]
• [math(g_{\varphi(2,0,0)}(n) ≒ f_{\omega2}(n))]
• [math(g_{\varphi(m,0,0)}(n) ≒ f_{\omega m}(n))]
• [math(g_{\varphi(1,0,0,0)}(n) ≒ f_{\omega^2}(n))]
• [math(g_{\varphi(1,0,0,0,0)}(n) ≒ f_{\omega^3}(n))]
• [math(g_{\psi(\Omega^{\Omega^\omega})}(n) = g_{SVO}(n) ≒ f_{\omega^{\omega}}(n))]
• [math(g_{\psi(\Omega^{\Omega^{\omega+m}})}(n) ≒ f_{\omega^{\omega+m}}(n))]
• [math(g_{\psi(\Omega^{\Omega^{\omega2}})}(n) ≒ f_{\omega^{\omega2}}(n))]
• [math(g_{\psi(\Omega^{\Omega^{\omega m}})}(n) ≒ f_{\omega^{\omega m}}(n))]
• [math(g_{\psi(\Omega^{\Omega^{\omega^2}})}(n) ≒ f_{\omega^{\omega^2}}(n))]
• [math(g_{\psi(\Omega^{\Omega^{\psi(\Omega^{\Omega})}})}(n) ≒ f_{\omega^{\omega^{\omega}}}(n))]
• [math(g_{\psi(\Omega^{\Omega^{\Omega}})}(n) = g_{LVO}(n) ≒ f_{\epsilon_0}(n))]