1 개요
큰 수들의 크기를 비교할 때 쓰이는 계층구조.
2 정의 및 설명
- [math] f_0(n) = n+1 [/math]
- ordinal [math] \alpha [/math]에 대해 [math] f_{\alpha +1}(n) = f_{\alpha}^n (n) [/math]
- [math] \alpha [/math]가 limit ordinal이라면 [math] f_{\alpha}(n) = f_{\alpha [n]}(n) [/math]
이해를 돕기 위해서 ordinal을 '단계'라는 말로 대체하고 정의를 풀어서 다시 쓰면 다음과 같다.
- 0단계 함수는 '다음 수'라는 연산이다.
- 다음단계 함수는 이번단계 함수를 [math]n[/math]번 합성한 것이다.
- 단계를 표시한 식에 문자밖에 없을 경우, 그 식의 끝 문자에 [math]n[/math]을 대입한다.
각 단계는 하나의 함수를 가리킨다. 정의 (2)에 의해서 같은 단계의 함수에 더 큰 수를 집어넣는 것보다 단계를 높이는 것이 결과값을 훨씬 크게 만든다. 4단계 이상이 되면 함수에 3만 집어넣어도 우주 원자 수 정도는 가뿐히 넘는다. 높은 단계의 크기를 체감하고 싶을 때에는 보통 [math]n[/math]에 3을 대입하는 경우가 많다.
3 계산 예시
정의에 의해 0단계 함수는 '다음 수'라는 연산이다. [math] f_0(n) = n+1,\ f_0(100)=101 [/math]
1단계 함수는 '다음 수'를 [math]n[/math]번 반복한 것이므로 [math] n+n=2n [/math]이다. [math] f_1(n) = 2n,\ f_1(100)=200 [/math]
2단계 함수는 2배하기를 [math]n[/math]번 반복하는 것이므로[1] [math]2 \times 2 \times ... \times 2 \times n = n \times 2^n[/math]이다. [math]f_2(n) = n \times 2^n,\ f_2(100)=100 \times 2^{100} \sim 1.267[/math]구
3단계 함수는 [math] n \times 2^n, (n \times 2^n) \times 2^{(n \times 2^n)}, ... [/math] 이런식으로 [math]n[/math]번 합성하는 것이다. 줄임표를 사용하지 않고 정확하게 나타내기는 힘들고 근삿값은 [math] 2^{2^{2^{...^{2^n}}}} [/math]으로 [math] 2 \uparrow \uparrow n [/math]보다 크다. [math] \uparrow \uparrow [/math]의 의미는 테트레이션 참고.
4단계 함수는 3단계 함수를 [math] n [/math]번 합성한 것이므로 근삿값으로 [math] 2 \uparrow \uparrow 2 \uparrow \uparrow.. \uparrow \uparrow n [/math]이고 이것은 [math] 2 \uparrow \uparrow \uparrow n[/math]보다 크다.
5단계 함수는 4단계 함수를 [math]n[/math]번 합성한 것이므로 근삿값으로 [math]2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow ... \uparrow \uparrow \uparrow n[/math]이고 이것은 [math]2 \uparrow \uparrow \uparrow \uparrow n[/math]보다 크다. 즉 윗 화살표가 [math]a[/math]개 있는 것은 [math]a+1[/math]단계라고 할 수 있다. (화살표 앞뒤에 붙는 수의 크기는 2 이상이기만 하면 크게 중요하지 않다.)
그러면 윗화살표 표기법만 가지고 모든 단계를 근사할 수 있을까? 아니다. 아직 정의 (3)은 쓰지도 않았다. 여기서 가장 작은 무한 ordinal인 [math]\omega[/math]가 등장한다.
[math]\omega[/math]단계 함수는 정의(3)에 의해 드디어 이거 쓰네 [math]\omega[/math]에 n을 대입해서 n단계 함수가 된다. 즉 [math]f_{\omega}(100)=f_{100}(100)[/math]이다.
[math]\omega+1[/math]단계 함수는 [math]n+1[/math]단계 함수가 아니다. 정의 (2)에 의하여 [math]\omega+1[/math]단계는 [math]\omega[/math]단계를 [math]n[/math]번 중첩하는 것인데, [math]f_{100}(100)[/math]을 계산해서 나오는 엄청 큰 수를 [math]A[/math]라고 하면 [math]A[/math]단계 함수인 [math]f_A(A)[/math]를 계산해야 하고 그 결과를 또 단계에 넣고 하는 것을 100번 반복해야 [math]f_{\omega+1}(100)[/math]이 나온다.
[math]\omega + \omega[/math]단계 함수는 [math]\omega \times 2[/math]단계로 나타내고[2] 정의 (3)을 사용하면 [math]\omega+n[/math]단계 함수가 된다.
[math]\omega \times \omega[/math]단계 함수는 [math] \omega^2[/math]단계로 나타내고 정의 (3)을 사용하면 [math] \omega \times n[/math]단계 함수가 된다.
[math]\omega^{\omega}[/math]단계 함수도 있고, [math]\omega^{\omega^{\omega}}[/math]단계도 있고, [math]\omega^{\omega^{\omega^{\omega}}}[/math]단계도 있고, ... 이런 식으로 계속 올라가서 [math]\omega[/math]를 지수로 [math]\omega[/math]번 쌓은 것을 [math]\epsilon_0[/math]라고 한다. 그 이후로도 [math]\zeta_0, \Gamma_0[/math] 등의 많은 단계들을 만들어냈으나 여기서는 생략.
4 큰 수의 서열
[math]\alpha[/math]단계에 해당하는 수의 범위를 [math]f_{\alpha}(3)[/math] 이상 [math]f_{\alpha}(100)[/math] 이하로 잡았으며, 3단계까지는 이 기준이 바뀌면 수들의 위치도 변한다. (순서가 바뀌지는 않는다.)
- 0단계: 4부터 101까지
- 1단계: 6부터 200까지
- 2단계: 24부터 약 1.267구까지. 만, 억, 조, 경, 해, 자, 양, 구
- 2단계와 3단계 사이: 간, 정, 재, 극, ..., 무량대수, 구골, 긍갈라, 아가라, 최승, ..., 보마
- 3단계: 녜마, 아바검, 미가바, ..., 불가설불가설전, 구골플렉스, 구골플렉시안, 스큐스 수
- [math]\omega[/math]단계와 [math]\omega+1[/math]단계 사이: 모우저
- [math]\omega+1[/math]단계: 그레이엄 수
- [math]\epsilon_0[/math]단계: Goodstein function
- 작성자가 이해하지 못한 단계: TREE function, SCG function, Loader's number
- 측정 불가 단계: Rayo's number, busy beaver function, Xi function 등