그레이엄 수
1. 개요
Graham's number
수의 하나. 램지 이론이라는 조합론의 문제 중 하나에서 구해지는 수다.
간단히 말하자면 다음 조건을 만족하는 수.
의 2''n''개의 꼭짓점을 모두 직선으로 연결한다. 그리고 이 선들을 2가지 색을 사용해 칠한다. 이 때 ''n''이 충분히 크다면 칠하는 방법에 상관없이 동일 2차원 평면상에 있는 네 점을 연결한 6개의 선이 모두 같은 색인 것이 반드시 존재한다.여기서 나온 '충분히 큰' ''n'' 값이 바로 '''그레이엄 수'''이다.
그런데, 이 수가 상상조차 쉽게 할 수 없을 만큼 큰 수 라는 점이다. 아래 계산법을 보면 알겠지만, $$3 \uparrow\uparrow\uparrow 3$$만해도 쉽게 상상이 안되는 큰 수인데, 이건 겨우 처음 시작 부분에 위치하는 작은 수(?)이다.
다만, 실제로 인위적으로 창조한 수 중에서는 이보다 더 큰 수도 많다. 피쉬 수, BIGG, Meameamealokkapoowa oompa 같은 수는 그레이엄 수 보다 아득하게 더 크며, 이보다도 더 큰 수들도 얼마든지 많다.[2] 하지만 큰 수의 대표격으로 그레이엄 수가 언급되는 것은 '''"수학적 증명에서 등장하는 가장 큰 수"'''라는 실제적으로 '수학적 의미'를 가지고 있는 수이기 때문이다.
2. 일러두기
그레이엄 수의 계산을 알기 위해서는 거듭제곱 이상의 계산을 하기 위해 쓰이는 하이퍼 연산 표기법중의 하나인 커누스 윗화살표 표기법을 알아야 한다.
앞으로 테트레이션의 계산으로 $$\underbrace {a^{a^{\cdot^{\cdot^{\cdot^a}}}}}_b$$ 의 형태가 많이 나올텐데 이 문서에서는 'a로 b개의 지수 탑을 쌓는다'라고 표현하겠다.
- 표기 간략화
$$\left. \begin{matrix} \underbrace a \\ \underbrace b \\ \underbrace {\vdots} \\ z \end{matrix} \right \} 26$$
마찬가지로 위의 표기에서도 26은 총 몇 층인지를 나타낸다.
3. 처음 알려진 그레이엄 수(大 그레이엄 수)
1977년, 이 수가 그 문제의 답이라는 것을 수학자 로널드 그레이엄이 증명했고 기존에 스큐스 수가 가지고 있던 "수학적인 증명에서 나타나는 가장 큰 수" 타이틀을 뺏어왔다. 게다가 지금 스큐스 수는 계속 줄어들고 있다.
비록 그레이엄이 이 수가 문제의 답임을 구하긴 했지만 그 답이 천문학적이라는 수식어가 왜소할 정도로 큰 수인 관계로 수학자들은 이보다 더 작은 답이 없는지 계속 찾고 있다.
3.1. 계산
앞으로의 계산들에 넣은 괄호는 계산 순서가 어떻게 되는지 시각적으로 쉽게 이해할 수 있도록 넣은 것이지 괄호가 없어도 계산은 똑같이 된다.
그레이엄 수는 3이 주인공인 수이다. 먼저 2개의 3을 놓고 화살표를 1개씩 늘려보자.
$$3 \uparrow 3 = 3^3 = 27$$
$$\begin{aligned} 3 \uparrow\uparrow 3 & = 3 \uparrow 3 \uparrow 3 \\ & = 3 \uparrow 27 \\ & = 7625597484987 \end{aligned}$$
벌써 이 단계에서 $$ 3 \uparrow\uparrow 3 = 3^{3^3} = 3^{27} = 7625597484987$$. 즉 7조를 넘는다.
[math(\begin{aligned} 3 \uparrow\uparrow\uparrow 3 & = 3 \uparrow\uparrow 3 \uparrow\uparrow 3 \\
& = 3 \uparrow\uparrow (3 \uparrow 3 \uparrow 3) \\
& = 3 \uparrow\uparrow (3 \uparrow 27) \\
& = 3 \uparrow\uparrow 7625597484987 \\
& = \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3}_{7625597484987} \end{aligned})]
위는 3을 거듭제곱으로 7,625,597,484,987개의 지수 탑을 쌓아 올린 것이다. 그러니까 $$\underbrace {3^{3^{ ^{\cdot^{\cdot^{\cdot^3}}}}}}_{7625597484987}$$ 이란 얘기이다. 이미 이 단계에서부터 상상을 초월하는 큰 수가 나와버렸다.[3] 2cm 크기로 3을 쓴다면 지구부터 태양까지 도달해야 완성할 수 있다.
[math(\begin{aligned} 3 \uparrow\uparrow\uparrow\uparrow 3 & = 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \\
& = 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow 3 \uparrow\uparrow 3) \\
& = 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow 3 \uparrow 3)) \\
& = 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow 27)) \\
& = 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow 7625597484987) \\
& = 3 \uparrow\uparrow\uparrow (\underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3}_{7625597484987}) \\
& = \underbrace{3 \uparrow\uparrow 3 \uparrow\uparrow \cdots \uparrow\uparrow 3}_{\underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3}_{7625597484987}} \end{aligned} \\
\qquad~\:\: \left. \begin{aligned} &&=\underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3} \\
&& \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3} \\
&& \underbrace{\qquad ~} \\
&& \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3} \\
&& \underbrace{3 \uparrow 3 \uparrow 3}_{\displaystyle 3} \;\;\;~ \end{aligned} \right \} \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3}_{7625597484987})]
이는 3으로 3개의 지수 탑을 쌓고, 그렇게 나온 그 수를 개수로 해서 3으로 지수 탑을 쌓고, 다시 그 수를 개수로 해서 3으로 지수 탑을 쌓고, 다시 그 수를 개수로 해서 3으로 지수 탑을 쌓고... 이를 총 $$3 \uparrow\uparrow\uparrow 3-1$$번을 해야 하는 수다. $$3 \uparrow\uparrow\uparrow 3$$이 얼마나 큰 수인지는 위에 나와있으니 알 것이다.
[math(\left. \begin{matrix}
\underbrace {3^{3^{\cdot^{\cdot^{\cdot^3}}}}} \\
\underbrace {3^{3^{\cdot^{\cdot^{\cdot^3}}}}} \\
\underbrace {\;\, \vdots \;\,} \\
\underbrace {3^{3^{\cdot^{\cdot^{\cdot^3}}}}} \\
\underbrace {3^{3^3}} \\
3 \end{matrix} \right \} \underbrace {3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{3^{3^3}})]
지수 형태로 나타내면 위와 같이 된다.
$$g_1 = 3 \uparrow\uparrow\uparrow\uparrow 3$$
이제 이 $$3 \uparrow\uparrow\uparrow\uparrow 3$$를 $$g_n$$수열의 1번째 항이라고 정의한다. 이 수도 굉장할 정도로 큰 수지만 아직 그레이엄 수까지는 코빼기도 안 갔다.
$$g_2 = 3 \uparrow^{g_1} 3$$
2번째 항을 구하기 위해서는 역시 화살표의 개수를 늘려야 한다. 화살표가 몇개냐고? 바로 $$g_1$$개이다. $$g_2$$는 $$3 \uparrow\uparrow \cdots \uparrow 3$$에서 ↑의 개수가 $$g_1$$개, 즉 $$3 \uparrow\uparrow\uparrow\uparrow 3$$개라는 것이다.
$$g_3 = 3 \uparrow^{g_2} 3$$
$$g_4 = 3 \uparrow^{g_3} 3$$
$$g_5 = 3 \uparrow^{g_4} 3$$
$$\;\vdots$$
$$g_{64} = 3 \uparrow^{g_{63}} 3 = \text{Graham's\;number}$$
그 다음 항을 구할 때도 마찬가지이다. $$g_3$$은 화살표가 $$g_2$$개, $$g_4$$는 화살표가 $$g_3$$개, $$g_5$$는 화살표가 $$g_4$$개 ... 이 과정을 계속하여 구한 64번째 항 $$g_{64}$$가 바로 '''그레이엄 수'''이다.
한마디로 정리하면, 그레이엄 수는 아래 점화식으로 정의된 수열 $$\{g_{n}\}$$의 제64항인 $$g_{64}$$라고 할 수 있다.
그레이엄 수 계산을 설명한 영상(영어)
엄청 큰 수의 표기법(한국어)
일본어 백과사전에 따른 정식 표기는 아래와 같다.
[ 펼치기 ・ 접기 ]
\end{matrix} \right \} 64)]}}}
위에서 봤듯이 화살표가 한개 늘어갈 때마다 상상할 수 없는 속도로 수가 커지는데, 그레이엄 수는 화살표의 개수마저도 상상이 안가는 수만큼 필요한 것이다. 만약에 그레이엄 수가 모두 계산이 돼서 그 수를 나타낼 때, 각 자리의 숫자 하나가 플랑크 부피(4.22419×10−105 m3)만큼의 공간을 차지한다고 하더라도 관측 가능한 우주에 그레이엄 수의 숫자를 다 담아낼 수 없다. 만약 다중우주가 존재한다고 치고, 다중우주가 구골플렉스↑구골플렉스↑구골플렉스↑구골플렉스...를 구골플렉스번[4] 반복한 만큼 있다고 해도 이 모든 우주는 그레이엄 수의 티끌만큼도 담아내지 못한다. 참고로 '''수소 원자의 부피가 6.54×10−32 m3 정도 된다.''' 그리고, 관측 가능한 우주의 부피는 대략 3.4×1080 m3 정도로 추정된다. 흔히 숫자가 클 때 표현하는 '천문학적이다'라는 표현도 이 수의 거대함을 표현하기에는 택도 없을 만큼 상상을 초월하는 수인 것이다.
다행히 콘웨이 화살표 표기법을 이용하면 $$3 \rightarrow 3 \rightarrow 64 \rightarrow 2$$보다 크고 $$3 \rightarrow 3 \rightarrow 65 \rightarrow 2$$보다 작은 수라고 표기할 수 있으며, $$f(x) = 3 \rightarrow 3 \rightarrow x$$라고 두면 $$(\underbrace {f \circ f \circ \cdots \circ f}_{64})(4)=f^{64}(4)$$와 같이 나타낼 수 있다고 한다.
참고로 마지막 500자리 숫자는 다음과 같다. 출처참고[5]
4. 새로 알려진 그레이엄 수(小 그레이엄 수)
많은 수학자들이 이 수의 더 작은 상한을 찾기 위해서 노력하였는데, 어느 수학자에 의해서 이 문제의 답이 $$2 \uparrow\uparrow\uparrow 6$$보다 작다는 논문이 발표되었다. arxiv의 논문 보기 단 arxiv의 특성상 이 논문에 오류가 없다는 것이 확인된 것은 아니다. 더 많은 수학자에 의해서 검증 받게 된 후에나 인정될 것이다.
$$2 \uparrow\uparrow\uparrow 6$$도 매우 큰 수긴 하나 기존의 그 끝을 알 수 없었던 원래의 수보다 굉장히 작은 수다.[6]
참고로 저 논문의 내용을 간단히 줄이면 그레이엄 수 $$Graham(2) \leq TTT(4,2,6) + 1$$인것을 증명하였고, 거기에 추가로 $$TTT(4,2,6) < HJ(4,2,6)$$으로 바운드되며, $$HJ(4,2,6) < 2 \uparrow\uparrow 2 \uparrow\uparrow (3 + 2 \uparrow\uparrow 8) < 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 9 < 2 \uparrow\uparrow\uparrow 6$$이라는 것을 계산한 것이다.
4.1. 계산
$$2 \uparrow\uparrow\uparrow 6$$을 한번 계산해보자.
먼저 화살표 표기법의 성질을 이용해서
$$2 \uparrow\uparrow\uparrow 6$$
$$= 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 2$$
$$= 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow (2 \uparrow 2)$$
$$= 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 4$$
$$= 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow (2 \uparrow 2 \uparrow 2 \uparrow 2)$$
$$= 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow (2 \uparrow 2 \uparrow 4)$$
$$= 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow (2 \uparrow 16)$$
$$= 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 65536$$ 으로 나타낼 수 있다.
여기서 제일 먼저 계산해야 하는 $$2 \uparrow\uparrow 65536$$은 $$\underbrace{2 \uparrow 2 \uparrow \cdots \uparrow 2}_{65536}$$로 정의되고, 이 수가 얼마인지 가늠하기 위해 $$2 \uparrow\uparrow 4$$부터의 계산을 살펴보자면
$$2 \uparrow\uparrow 4 = 2^{2^{2^{2}}} = 65536$$
$$2 \uparrow\uparrow 5 = 2^{2^{2^{2^{2}}}} = 2^{65536} \approx 2 \times 10^{19728}$$
$$2 \uparrow\uparrow 6 = 2^{2^{2^{2^{2^{2}}}}} \approx 10^{10^{19727}}$$
$$2 \uparrow\uparrow 7 = 2^{2^{2^{2^{2^{2^{2}}}}}} \approx 10^{10^{10^{19727}}}$$
$$2 \uparrow\uparrow 8 = 2^{2^{2^{2^{2^{2^{2^{2}}}}}}} \approx 10^{10^{10^{10^{19727}}}}$$
$$2 \uparrow\uparrow 9 = 2^{2^{2^{2^{2^{2^{2^{2^{2}}}}}}}} \approx 10^{10^{10^{10^{10^{19727}}}}}$$
$$2 \uparrow\uparrow 10 = 2^{2^{2^{2^{2^{2^{2^{2^{2^{2}}}}}}}}} \approx 10^{10^{10^{10^{10^{10^{19727}}}}}}$$
$$\quad\,\vdots$$
$$2 \uparrow\uparrow 65536 = \underbrace {2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536} \approx \; \underbrace {\!\!10^{10^{\cdot^{\cdot^{\cdot^{10}}}}}\!\!\!}_{65532}{}^{^{^{^{^{^{\,19727}}}}}}$$
이렇게 2로 65536개의 지수 탑을 쌓은 수이다.
$$2 \uparrow\uparrow 7$$만 해도 구골플렉시안을 가뿐히 넘는 수가 나오게 되는데, 이 $$2 \uparrow\uparrow 65536$$ 앞에 $$2 \uparrow\uparrow$$를 붙여 계산하는 것을 2번 더 해야 한다.
$$2 \uparrow\uparrow 2 \uparrow\uparrow 65536 = \underbrace {2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\displaystyle \underbrace {2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}$$
$$2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 65536 = \underbrace {2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\displaystyle \underbrace {2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\displaystyle \underbrace {2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}}$$
정리하면 $$2 \uparrow\uparrow\uparrow 6$$은 2로 65536개의 지수 탑을 쌓아서 만든 수를 개수로 해서 2로 지수 탑을 쌓고 다시 그 수를 개수로 해서 2로 지수 탑을 쌓아서 만든 수이다. 이 수도 결코 작은 수가 아닌데, 원래의 그레이엄 수에 비하면 상상조차 못 할 정도의 수는 아니다.
5. 관련 문서
[1] 한국어 위키백과에 초입방체에 대한 설명이 있으니 참고하자. 간단히 말하면 2차원은 정사각형, 3차원은 정육면체 등이다.[2] 당장 그레이엄 수에 1만 더해도 더 큰 수가 되기 때문이다.[3] 앞에서 얘기했지만 지수에 지수가 있는 것이 반복된 형태는 위에 있는 지수부터 밑으로 계산해야 한다.
맨 위에 있는 지수 $$3^3=27$$
그 아래 $$3^{3^3}=3^{27}=7625597484987$$
그 아래 $$3^{3^{3^3}}=3^{7625597484987} \approx1.258×10^{3638334640024}$$
그 아래 $$3^{3^{3^{3^3}}} \approx 3^{1.258×10^{3638334640024}} \approx 10^{10^{10^{12.56}}}$$...
이렇게 이런 계산을 총 7,625,597,484,986번을 해야 $$3 \uparrow\uparrow\uparrow 3$$가 나오니 말 다했다.[4] 줄여서 표현하자면 구골플렉스↑↑구골플렉스로 표현할 수 있다. 하이퍼 구골플렉스, 메가퓨거구골플렉스 라고도 부르며 이는 현재의 기술로도 계산이 불가능한 3↑↑↑3 으로도 비교할 수 없는 훨씬 큰 수다.[5] $$3 \uparrow\uparrow\uparrow 3$$도 이미 계산이 불가능한 상황에 그레이엄 수를 다 계산했을 리는 없다. 저 숫자들은 일부만 계산했을 때 나타나는 법칙을 토대로 구해낸 것.[6] 대충 $$3 \uparrow\uparrow\uparrow 3$$보다는 약간(?) 크지만 $$3 \uparrow\uparrow\uparrow\uparrow 3$$보다는 어마어마하게 작다.
맨 위에 있는 지수 $$3^3=27$$
그 아래 $$3^{3^3}=3^{27}=7625597484987$$
그 아래 $$3^{3^{3^3}}=3^{7625597484987} \approx1.258×10^{3638334640024}$$
그 아래 $$3^{3^{3^{3^3}}} \approx 3^{1.258×10^{3638334640024}} \approx 10^{10^{10^{12.56}}}$$...
이렇게 이런 계산을 총 7,625,597,484,986번을 해야 $$3 \uparrow\uparrow\uparrow 3$$가 나오니 말 다했다.[4] 줄여서 표현하자면 구골플렉스↑↑구골플렉스로 표현할 수 있다. 하이퍼 구골플렉스, 메가퓨거구골플렉스 라고도 부르며 이는 현재의 기술로도 계산이 불가능한 3↑↑↑3 으로도 비교할 수 없는 훨씬 큰 수다.[5] $$3 \uparrow\uparrow\uparrow 3$$도 이미 계산이 불가능한 상황에 그레이엄 수를 다 계산했을 리는 없다. 저 숫자들은 일부만 계산했을 때 나타나는 법칙을 토대로 구해낸 것.[6] 대충 $$3 \uparrow\uparrow\uparrow 3$$보다는 약간(?) 크지만 $$3 \uparrow\uparrow\uparrow\uparrow 3$$보다는 어마어마하게 작다.