Graham's number

수의 하나. 램지 이론이라는 조합론의 문제 중 하나에서 구해지는 수다.

간단히 말하자면 다음 조건을 만족하는 수.

여기서 나온 '충분히 큰' n 값이 바로 그레이엄 수이다. 차원이 그렇게 큰 게 더 무섭다.

그런데, 이 수가 상상조차 쉽게 할 수 없을 만큼 큰 수 라는 점이다. 아래 계산법을 보면 알겠지만, $3 \uparrow\uparrow\uparrow 3$만해도 쉽게 상상이 안되는 큰 수인데, 이건 겨우 처음 시작 부분에 위치하는 작은 수(?)이다.

다만, 실제로 인위적으로 창조한 수 중에서는 이보다 더 큰 수도 많다. 피쉬 수, BIGG, Meameamealokkapoowa oompa 같은 수는 그레이엄 수 보다 아득하게 더 크며, 이보다도 더 큰 수들도 얼마든지 많다.[2] 하지만 큰 수의 대표격으로 그레이엄 수가 언급되는 것은 "수학적 증명에서 등장하는 가장 큰 수"라는 실제적으로 '수학적 의미'를 가지고 있는 수이기 때문이다.

그레이엄 수의 계산을 알기 위해서는 거듭제곱 이상의 계산을 하기 위해 쓰이는 하이퍼 연산 표기법중의 하나인 커누스 윗화살표 표기법을 알아야 한다.

앞으로 테트레이션의 계산으로 $\underbrace {a^{a^{\cdot^{\cdot^{\cdot^a}}}}}_b$ 의 형태가 많이 나올텐데 이 문서에서는 'a로 b개의 지수 탑을 쌓는다'라고 표현하겠다.

앞으로 $\underbrace {a \uparrow a \uparrow \cdots \uparrow a}_{a가\;b개}$를 $\underbrace {a \uparrow a \uparrow \cdots \uparrow a}_{b}$로 간략하게 나타내겠다. 그러므로 $\underbrace {a \uparrow a \uparrow \cdots \uparrow a}_{b}$에서 $b$는 $\uparrow$가 아닌 $a$가 모두 몇 개인지를 나타낸다.

$\left. \begin{matrix} \underbrace a \\ \underbrace b \\ \underbrace {\vdots} \\ z \end{matrix} \right \} 26$

마찬가지로 위의 표기에서도 26은 총 몇 층인지를 나타낸다.

1977년, 이 수가 그 문제의 답이라는 것을 수학자 로널드 그레이엄이 증명했고 기존에 스큐스 수가 가지고 있던 "수학적인 증명에서 나타나는 가장 큰 수" 타이틀을 뺏어왔다. 게다가 지금 스큐스 수는 계속 줄어들고 있다.

비록 그레이엄이 이 수가 문제의 답임을 구하긴 했지만 그 답이 천문학적이라는 수식어가 왜소할 정도로 큰 수인 관계로 수학자들은 이보다 더 작은 답이 없는지 계속 찾고 있다.

앞으로의 계산들에 넣은 괄호는 계산 순서가 어떻게 되는지 시각적으로 쉽게 이해할 수 있도록 넣은 것이지 괄호가 없어도 계산은 똑같이 된다.

그레이엄 수는 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조를 넘는다.

$\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을 쓴다면 지구부터 태양까지 도달해야 완성할 수 있다.

$\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~~~ \vdots \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$이 얼마나 큰 수인지는 위에 나와있으니 알 것이다.

$\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}$라고 할 수 있다.

그레이엄 수 계산을 설명한 영상(영어)
엄청 큰 수의 표기법(한국어)

일본어 백과사전에 따른 정식 표기는 아래와 같다.

[ 펼치기 ・ 접기 ]

$3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \uparrow \uparrow \uparrow \uparrow 3$

이를 조금 더 간단히 나타내면 다음과 같다.

$\left. \begin{matrix} 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ \underbrace {\quad~ \vdots \quad~} \\ 3 \underbrace {\uparrow \cdots \uparrow} 3 \\ 3 \uparrow \uparrow \uparrow \uparrow 3 \end{matrix} \right \} 64$

위에서 봤듯이 화살표가 한개 늘어갈 때마다 상상할 수 없는 속도로 수가 커지는데, 그레이엄 수는 화살표의 개수마저도 상상이 안가는 수만큼 필요한 것이다. 만약에 그레이엄 수가 모두 계산이 돼서 그 수를 나타낼 때, 각 자리의 숫자 하나가 플랑크 부피(4.22419×10⁻¹⁰⁵ m³)만큼의 공간을 차지한다고 하더라도 관측 가능한 우주에 그레이엄 수의 숫자를 다 담아낼 수 없다. 만약 다중우주가 존재한다고 치고, 다중우주가 구골플렉스↑구골플렉스↑구골플렉스↑구골플렉스...를 구골플렉스번[4] 반복한 만큼 있다고 해도 이 모든 우주는 그레이엄 수의 티끌만큼도 담아내지 못한다. 참고로 수소 원자의 부피가 6.54×10⁻³² m³ 정도 된다. 그리고, 관측 가능한 우주의 부피는 대략 3.4×10⁸⁰ m³ 정도로 추정된다. 흔히 숫자가 클 때 표현하는 '천문학적이다'라는 표현도 이 수의 거대함을 표현하기에는 택도 없을 만큼 상상을 초월하는 수인 것이다.

다행히 콘웨이 화살표 표기법을 이용하면 $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]

많은 수학자들이 이 수의 더 작은 상한을 찾기 위해서 노력하였는데, 어느 수학자에 의해서 이 문제의 답이 $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$이라는 것을 계산한 것이다.

$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로 지수 탑을 쌓아서 만든 수이다. 세상에... 이 수도 결코 작은 수가 아닌데, 원래의 그레이엄 수에 비하면 상상조차 못 할 정도의 수는 아니다.