커누스 윗화살표 표기법

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

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

커누스 윗화살표 표기법은 덧셈, 곱셈, 거듭제곱 표기로 이어지는 반복 계산 표기법을 일반화한 의미가 있다. 덧셈이란 1을 반복하여 증가시키는 연산이고, 곱셈이란 덧셈을 반복하는 연산이고, 거듭제곱은 곱셈을 반복하는 연산이다. 이러한 반복 연산을 무한히 확장할 수 있는 표기법으로 윗화살표(\uparrow)를 사용할 수 있다. 윗화살표 1개는 곱셈을 반복하는 거듭제곱 연산이고, 2개는 거듭제곱을 반복하는 연산, 즉 테트레이션(tetration)이다. 윗화살표 3개는 테트레이션을 반복하는 펜테이션(pentation)이고, 윗화살표 4개는 펜테이션을 반복하는 헥세이션(hexation)이다. 이처럼 윗화살표의 개수는 무한히 증가할 수 있는데, 이것을 일반화하여 \uparrow^m과 같이 표기할 수 있다. 여기서 m은 윗화살표의 개수를 나타낸다.

표기법[편집]

자연수 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개)

계산[편집]

윗화살표가 1개인 경우 2\uparrow n은 다음과 같이 계산한다.

2\uparrow 1 = 2^1 = 2

2\uparrow 2 = 2^2 = 4

2\uparrow 3 = 2^3 = 8

2\uparrow 4 = 2^4 = 16

2\uparrow 5 = 2^5 = 32

2\uparrow 6 = 2^6 = 64

...

2\uparrow n = 2^n = 2 \times 2 \times ... \times 2 : (2를 n회 반복하여 곱한다)


윗화살표가 2개인 경우 2\uparrow \uparrow n은 다음과 같이 계산한다.

2\uparrow \uparrow 1 = 2

2\uparrow \uparrow 2 = 2^2 = 4

2\uparrow \uparrow 3 = 2^{2^2} = 16

2\uparrow \uparrow 4 = 2^{2^{2^2}} = 65,536

2\uparrow \uparrow 5 = 2^{2^{2^{2^2}}} = 2^{65,536} \approx 2.0 \times 10^{19,728}

2\uparrow \uparrow 6 = 2^{2^{2^{2^{2^2}}}} = 2^{2^{65,536}} \approx 10^{6.0 \times 10^{19,727}}

...

2\uparrow \uparrow n = 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}} (n회)


윗화살표가 3개인 경우 2\uparrow \uparrow \uparrow n은 다음과 같이 계산한다.

2\uparrow \uparrow \uparrow 1 = 2

2\uparrow \uparrow \uparrow 2 = 2\uparrow \uparrow 2 = 2^2 = 4

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

2\uparrow \uparrow \uparrow 4 = 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2)) = 2\uparrow \uparrow (2\uparrow \uparrow \uparrow 3) = 2\uparrow \uparrow 65,536 = 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}} (65,536회)

2\uparrow \uparrow \uparrow 5 = 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2))) = 2\uparrow \uparrow (2\uparrow \uparrow \uparrow 4) = 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}} (2\uparrow \uparrow \uparrow 4회)

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 \uparrow 5) = 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}} (2\uparrow \uparrow \uparrow 5회)

...

2\uparrow \uparrow \uparrow n = 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow ... \uparrow \uparrow 2)))) = 2\uparrow \uparrow (2\uparrow \uparrow \uparrow (n-1)) = 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}} (2\uparrow \uparrow \uparrow (n-1)회)


윗화살표가 4개인 경우 2\uparrow \uparrow \uparrow \uparrow n은 다음과 같이 계산한다.

2\uparrow \uparrow \uparrow \uparrow 1 = 2

2\uparrow \uparrow \uparrow \uparrow 2 = 2\uparrow \uparrow \uparrow 2 = 2^2 = 4

2\uparrow \uparrow \uparrow \uparrow 3 = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow 2) = 2\uparrow \uparrow \uparrow 4 = 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}} (65,536회)

2\uparrow \uparrow \uparrow \uparrow 4 = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow 2)) = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow \uparrow 3) = 2\uparrow \uparrow \uparrow 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}} (65,536회)

2\uparrow \uparrow \uparrow \uparrow 5 = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow 2))) = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow \uparrow 4) = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}}) (65,536회)

2\uparrow \uparrow \uparrow \uparrow 6 = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow 2)))) = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow \uparrow 5) = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}})) (65,536회)

...

2\uparrow \uparrow \uparrow \uparrow n = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow ... \uparrow \uparrow \uparrow 2)))) = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow \uparrow (n-1)) = 2\uparrow \uparrow \uparrow (2\uparrow \uparrow \uparrow ... \uparrow \uparrow \uparrow 2^{2^{2^{2^{.^{.^{.^{.^2}}}}}}}) (65,536회)


마찬가지로 3에 대해 계산하면 다음과 같다.

3\uparrow 1 = 3^1 = 3

3\uparrow 2 = 3^2 = 9

3\uparrow 3 = 3^3 = 27

3\uparrow 4 = 3^4 = 81

3\uparrow \uparrow 1 = 3

3\uparrow \uparrow 2 = 3^3 = 27

3\uparrow \uparrow 3 = 3^{3^3} = 3^{27} = 7,625,597,484,987

3\uparrow \uparrow 4 = 3^{3^{3^3}} = 3^{7,625,597,484,987}

3\uparrow \uparrow \uparrow 1 = 3

3\uparrow \uparrow \uparrow 2 = 7,625,597,484,987

3\uparrow \uparrow \uparrow 3 = 3^{3^{3^{3^{.^{.^{.^{.^3}}}}}}} (7,625,597,484,987회)

3\uparrow \uparrow \uparrow \uparrow 1 = 3

3\uparrow \uparrow \uparrow \uparrow 2 = 3^{3^{3^{3^{.^{.^{.^{.^3}}}}}}} (7,625,597,484,987회)


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

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

그레이엄 수 표기[편집]

커누스 윗화살표는 그레이엄 수 G64(4)를 표기할 때 사용되고 있다. 그레이엄 수는 이름이 붙은 자연수 중에서 수학적 의미를 갖고 있는 가장 큰 수이다.

G^{64}(4) = 3 \uparrow ... \uparrow 3 (여기서 윗화살표의 개수는 G63(4)개이다.)


같이 보기[편집]