큰 수에 대하여 (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=\underset{65,536\text{-times}}{\underbrace{2^{2^{{\cdot }^{{\cdot }^2}}}}}$

• $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=\underset{65,536\text{-times}}{\underbrace{2^{2^{{\cdot }^{{\cdot }^2}}}}}$
  $2\uparrow \uparrow \uparrow \uparrow 4=2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow 2))=2\uparrow \uparrow \uparrow \left(\underset{65,536\text{-times}}{\underbrace{2^{2^{{\cdot }^{{\cdot }^2}}}}}\right)=???$

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

$$a{\uparrow }^{k}n=\underset{k\text{-times}}{\underbrace{a\underset{(n-1)\text{-times}}{\underbrace{\uparrow \cdots \uparrow }}a\underset{(n-1)\text{-times}}{\underbrace{\uparrow \cdots \uparrow }}\cdots \underset{(n-1)\text{-times}}{\underbrace{\uparrow \cdots \uparrow }}a}}$$

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

정수 $a$와 음이 아닌 정수$n\ge 0$, $k\ge 0$에 대하여,

$$a{\uparrow }^{k}n:=\{\begin{array}{ll}na& \text{if }k=0\\ 1& \text{if }k\ge 1\text{ and }n=0\\ a{\uparrow }^{k-1}(a{\uparrow }^k(n-1))& \text{otherwise}\end{array}$$

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