크누스 윗화살표 표기법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

크누스 윗화살표 표기법(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개)

같이 보기[편집]