큰 수에 대하여 (3) - 크누스 윗화살표 표기법(Knuth's Up-Arrow Notation)

크누스 윗화살표 표기법(Knuth's up-arrow notation)은 매우 큰 정수를 표기하는 방법중의 하나로 크누스(Donald Knuth) 에 의해 1976년에 개발되었다. 곱셈은 덧셈의 반복연산, 거듭제곱은 곱셈의 반복연산이라는 사실에 착안하며, 거듭제곱의 반복연산 (테트레이션(tetration)), 테트레이션의 반복연산등을 쉽게 표기할 수 있는 방법 중 하나로써 개발되었다. 크누스 윗화살표 표기법의 간단한 설명하면 다음과 같다.

먼저 \(a\)의 \(n\) 거듭제곱을 \(a \uparrow n\)으로 나타낸다. 다시말해 \(a \uparrow n :=a^n\)으로 정의한다. 또한 \(a \uparrow \uparrow n\)은 \(a \uparrow n\)을 \(n\)회 반복시행한 것, 즉 테트레이션(tetration)을 나타낸다. 따라서 \(a \uparrow \uparrow n := {}^{n}a\)이다. 이와 같은 방식으로 \(a \uparrow \uparrow \uparrow n\) (펜테이션(pentation)), \(a \uparrow \uparrow \uparrow \uparrow n\) (헥세이션(hexation)) 등도 정의할 수 있다. 크누스 윗화살표 표기법을 이용한 계산값들이 얼마나 폭발적으로 증가하는지, 간단한 예를 통해 살펴보자.

• \(2 \uparrow 2 = 2 \times 2 = 4\)
  \(2 \uparrow 3 = 2 \times 2 \times 2 = 8 \)
  \(2 \uparrow 4 = 2 \times 2 \times 2 \times 2 = 16\)

• \(2 \uparrow \uparrow 2 = 2^2 = 4\)
  \(2 \uparrow \uparrow 3 = 2^{2^2} = 2^4 = 16 \)
  \(2 \uparrow \uparrow 4 = 2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65,536\)

여기까지는 실생활에서도 가끔은 볼 수 있는 연산이기 때문에 그 값을 계산하는 것이 그렇게 어렵지만은 않다. 하지만 아래의 식들을 보면 알 수 있듯이 얼핏 간단해 보이는 \(2 \uparrow \uparrow \uparrow 4\)도 그 크기를 가늠하는 것 조차 불가능해 보인다.

• \(2 \uparrow \uparrow \uparrow 2 = 2 \uparrow \uparrow 2 = 4\)
  \(2 \uparrow \uparrow \uparrow 3 = 2 \uparrow \uparrow (2 \uparrow \uparrow 2) = 2 \uparrow \uparrow 4 = 65,536\) 
  \(2 \uparrow \uparrow \uparrow 4 = 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow 2))) =  2 \uparrow \uparrow 65,536 = \underbrace{ 2^{2^{\cdot^{\cdot^{2}}}}}_{65,536\text{-times}} \)

• \(2 \uparrow \uparrow \uparrow \uparrow 2 = 2 \uparrow \uparrow \uparrow 2 = 4 \) 
  \(2 \uparrow \uparrow \uparrow \uparrow 3 = 2 \uparrow \uparrow \uparrow (2 \uparrow \uparrow \uparrow 2) = 2 \uparrow \uparrow \uparrow 4 = \underbrace{ 2^{2^{ \cdot^{ \cdot^{2}}}}}_{65,536\text{-times}} \)
  \(2 \uparrow \uparrow \uparrow \uparrow 4 = 2 \uparrow \uparrow \uparrow (2 \uparrow \uparrow \uparrow (2 \uparrow \uparrow \uparrow 2)) = 2 \uparrow \uparrow \uparrow \left( \underbrace{ 2^{2^{\cdot^{\cdot^{2}}}}}_{65,536\text{-times}} \right) = ??? \)

마지막 계산은 거듭제곱만을 이용해 표현하기가 거의 불가능에 가까워 계산을 생략하였다. 이제 여기까지 살펴 본 크누스 윗화살표 표기법을 일반화하여 \( a {\uparrow}^{k}n\)은 다음을 나타낸다고 하자.

\[a \uparrow^{k}n = \underbrace{a \underbrace{\uparrow \cdots \uparrow}_{(n-1)\text{-times}} a \underbrace{\uparrow \cdots \uparrow}_{(n-1)\text{-times}} \cdots \underbrace{\uparrow \cdots \uparrow}_{(n-1)\text{-times}} a}_{k\text{-times}} \]

위의 표현법을 바탕으로 크노스 윗화살표 표기법을 재귀적으로 정의하면 다음과 같다:

정수 \(a\)와 음이 아닌 정수\(n \geq 0\), \(k \geq 0\)에 대하여,

\[ a {\uparrow}^{k}n := \begin{cases} na & \text{if } k=0 \\ 1 & \text{if } k \geq 1 \text{ and } n=0 \\ a {\uparrow}^{k-1}(a {\uparrow}^{k}(n-1)) & \text{otherwise} \end{cases} \]

위의 정의는 곱셈 (\(a {\uparrow}^{0}n = na\))과 거듭제곱 (\(a {\uparrow}^{1}n = a \uparrow n = a^n\))을 모두 포함한다. 위의 재귀적 정의를 이용하면, 실제로 크누스 윗화살표 표기법을 이용한 계산을 컴퓨터로 간단하게 코딩할 수 있다. 나아가 \( 2 \uparrow \uparrow \uparrow 2 \)등의 계산을 직접 손으로 재귀적 정의에 의해 단계적으로 구해보는 것도 재미있을 것이다.