최근 수정 시각 : 2024-10-22 09:15:59

Slow-growing hierarchy

sgh에서 넘어옴
1. 개요2. 정의 및 설명3. 계산 예시

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번 정의에서 '기본 수열'을 정하기에 따라 sgh의 값은 달라질 수 있다. 예를 들어 [math(\omega)]는 [math(\{1,2,3,...\})]의 극서수이기도 하고 [math(\{2,4,6,8,...\})]의 극서수이기도 하다. 기본 수열을 무엇으로 하냐에 따라 [math(g_\omega(n))]의 성장률이 [math(n)]일 수도 있고 [math(2n)]일 수도 있는 것이다. 심지어는 [math(\{f_1(1),f_\omega(2),f_{\omega^\omega}(3),f_{\omega^{\omega^\omega}}(4),...\})]와 같이 잡으면 성장률이 [math(f_{\epsilon_0}(n))]과 동급인 사태가 벌어질 수도 있다. 따라서 '기본 수열'을 명시하고 그것이 무엇인지 확인하는 것이 중요하다.

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))]
[1] 물론 어디까지나 비교적 느리다는 소리지 지수는 물론, 커누스 윗화살표 표기법을 능가하는 것은 확실하다. 심지어 sgh의 한계치는 TREE(3)보다도 크다. 콘웨이 연쇄 화살표 표기법보다 훨씬 빠르고 [math(\psi(\psi_I(0)))]부터는 fgh와 별 차이가 없다. 물론 수의 크기 대비 별 차이가 없다는 것이지 비슷해지기 위해 TREE(작은 쪽) 식으로 늘려도 소용없다. [2] ≈ 역시나 모양만 다르고 용도는 같은 것이다.

분류