크누스 윗화살표 표기법

크누스 윗화살표 표기법(Knuth's up-arrow notation)은 아주 큰 정수를 표기하는 방법으로 도널드 크누스가 1976년에 개발했다. 이 표기법은 반복된 거듭제곱을 나타내기 위해 사용하며, 이런 방법은 거듭제곱이 곱셈의 반복이며, 곱셈이 덧셈의 반복인 것과 똑같다.

표기법

자연수 x, y에 대해 크누스 윗화살표 표기법 연산자 $\uparrow$는 다음과 같다:

$x\uparrow y = x^y$

또, $\uparrow \uparrow$는 다음과 같이 귀납적으로 정의한다.

$x\uparrow \uparrow 2 = x\uparrow x = x^x$

$x\uparrow \uparrow 3 = x\uparrow (x\uparrow x) = x^{x^x}$

...

$x\uparrow \uparrow y = x\uparrow (x\uparrow \uparrow (y-1)) = x\uparrow x\uparrow x\uparrow .....\uparrow x$ (y개) $= x^{x^{x^{.^{.^.}}}}$ (y개)

마찬가지로 $\uparrow \uparrow \uparrow$는 다음과 같이 정의한다.

$x\uparrow \uparrow \uparrow 2 = x\uparrow \uparrow x$

$x\uparrow \uparrow \uparrow 3 = x\uparrow \uparrow x\uparrow \uparrow x$

...

$x\uparrow \uparrow \uparrow y = x\uparrow \uparrow (x\uparrow \uparrow \uparrow (y-1)) = x\uparrow \uparrow x\uparrow \uparrow x\uparrow \uparrow ...\uparrow \uparrow x$ (y개)

일반적으로 $\uparrow ^n$은 다음과 같이 정의한다.

$x\uparrow ^ny = x\uparrow ...\uparrow y$ (n개) $= x\uparrow ...\uparrow x\uparrow ...\uparrow x ... x\uparrow ...\uparrow x$ (x가 y개, 각 부분의 화살표가 n-1개)

같이 보기

• 그레이엄 수