커누스 윗화살표 표기법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

커누스 윗화살표 표기법은 지수 표기법의 확장으로, 매우 큰 수를 나타내기 위해 고안된 수학적 표기법이다. 단일 윗화살표는 거듭제곱, 이중 윗화살표는 테트레이션을 나타내며, 화살표의 개수를 늘려가며 더욱 빠르게 증가하는 수를 표현한다. 이 표기법은 하이퍼 연산, 콘웨이 사슬 화살표 표기법, 배열 표기법 등과 밀접하게 관련되어 있으며, 그레이엄 수와 같이 상상을 초월하는 큰 수를 표현하는 데 활용된다.

2. 역사

덧셈, 곱셈, 거듭제곱과 같은 기본적인 산술 연산은 반복적인 적용을 통해 더 높은 단계의 연산으로 확장될 수 있는 자연스러운 수열을 형성한다. 도널드 커누스는 이러한 연산의 서열을 거듭제곱 이상으로 확장하고 매우 큰 수를 간결하게 표현하기 위해 윗화살표(↑)를 이용한 표기법을 개발했다. 이 표기법은 기본적인 연산들의 반복적인 성질을 일반화한 것이다.

커누스 표기법에서 윗화살표 한 개( $a \uparrow b$ )는 거듭제곱 $a^b$ 를 나타낸다. 이는 $a$ 를 $b$ 번 곱하는 것을 의미한다. 커누스는 연산의 서열을 더 확장하여, 거듭제곱의 반복인 테트레이션을 나타내는 "이중 윗화살표"( $a \uparrow\uparrow b$ ) 연산을 정의했다. 이는 $a$ 를 $b$ 번 거듭제곱한 탑 형태( $\underbrace{a^{a^}}}} _{b\mbox{ 개의 }a}$ )로 계산된다.

이러한 아이디어는 계속 확장될 수 있다. "삼중 윗화살표"( $a \uparrow\uparrow\uparrow b$ )는 테트레이션의 반복인 펜테이션을 의미하고, "사중 윗화살표"( $a \uparrow\uparrow\uparrow\uparrow b$ )는 펜테이션의 반복인 헥세이션을 나타낸다. 일반적으로, $n$ 개의 윗화살표 연산( $a \uparrow^n b$ )은 $n-1$ 개의 윗화살표 연산을 $b$ 번 반복 적용하는 방식으로 정의된다. 이 연산들은 거듭제곱과 마찬가지로 오른쪽 결합(right-associative) 성질을 가지며, 계산은 오른쪽에서 왼쪽으로 진행된다. 이 표기법은 하이퍼 연산의 수열을 나타내는 한 방법이기도 하다.

2. 1. 커누스의 도입 (1976)

덧셈, 곱셈, 거듭제곱과 같은 기본적인 산술 연산은 자연스럽게 하이퍼 연산이라는 연산의 서열로 확장될 수 있다.

자연수 ''b''에 의한 곱셈은 덧셈을 ''b''번 반복하는 것으로 정의된다:

:

a\times b = H_2(a,b) = \underbrace{a+a+\dots+a}_{b\mbox{ 개의 }a}

예를 들어,

3\times 4 = 4+4+4 = 12

이다.

자연수 지수 ''b''에 의한 거듭제곱은 곱셈을 ''b''번 반복하는 것으로 정의된다. 도널드 커누스는 이를 윗화살표 한 개(`↑`)를 사용하여 다음과 같이 표기했다. 이는 일부 초창기 컴퓨터에서 거듭제곱 연산자로 위쪽 화살표를 사용했던 것에서 착안한 것이다.

:

a\uparrow b = H_3(a,b) = a^b = \underbrace{a\times a\times\dots\times a}_{b\mbox{ 개의 }a}

예를 들어,

4\uparrow 3 = 4^3 = 4\times 4\times 4 = 64

이다. 구골플렉스

10^{10^{100}}

는 이 표기법을 사용하면

10\uparrow 10\uparrow 100

으로 쓸 수 있다.

커누스는 이러한 연산의 서열을 거듭제곱 이상으로 확장하기 위해, 거듭제곱의 반복인 테트레이션을 나타내는 "이중 윗화살표"(`↑↑`) 연산을 정의했다:

:

a\uparrow\uparrow b = H_4(a,b) = {\ ^{b}a} = \underbrace{a^{a^}}}} = \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))}_{b\mbox{ 개의 }a}

예를 들면 다음과 같다.

:

4\uparrow\uparrow 3 = {\ ^{3}4} = 4^{4^4} = 4\uparrow (4\uparrow 4) = 4^{256} \approx 1.34078079\times 10^{154}

여기서 계산은 오른쪽에서 왼쪽으로 진행되는데, 이는 커누스 윗화살표 연산(거듭제곱 포함)이 오른쪽 결합(right-associative)으로 정의되었기 때문이다.

이 정의에 따라 몇 가지 예를 들면 다음과 같다.

:

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^{3^{27}} = 3^{7625597484987} \approx 1.2580143\times 10^{3638334640024}

커누스는 이 표기법을 더욱 확장하여, 테트레이션의 반복인 펜테이션을 나타내는 "삼중 윗화살표"(`↑↑↑`) 연산을 정의했다:

:

a\uparrow\uparrow\uparrow b = H_5(a,b) = \underbrace{a\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}_{b\mbox{ 개의 }a}

이어서 펜테이션의 반복인 헥세이션은 "사중 윗화살표"(`↑↑↑↑`) 연산으로 정의했다:

:

a\uparrow\uparrow\uparrow\uparrow b = H_6(a,b) = \underbrace{a\uparrow\uparrow\uparrow (a\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow a))}_{b\mbox{ 개의 }a}

이러한 확장은 계속될 수 있다. 일반적인 규칙은

n

개의 윗화살표 연산(

a \uparrow^n b

)은

n-1

개의 윗화살표 연산을 ''b''번 반복하는 오른쪽 결합 연산으로 확장된다는 것이다. 기호로는 다음과 같이 나타낸다.

:

a \underbrace{\uparrow\uparrow\dots\uparrow}_{n} b = \underbrace{a \underbrace{\uparrow\uparrow\dots\uparrow}_{n-1} (a \underbrace{\uparrow\uparrow\dots\uparrow}_{n-1} (\dots \underbrace{\uparrow\uparrow\dots\uparrow}_{n-1} a))}_{b\mbox{ 개의 }a}

표기

a \uparrow^n b

는 하이퍼 연산

H_{n+2}(a,b)

와 같다.

예시:

:

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

:

3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow (3\uparrow\uparrow 3) = 3\uparrow\uparrow (7,625,597,484,987) = \underbrace{3^{3^{.^{.^{.^3}}}}} _{7,625,597,484,987 \mbox{ 개의 } 3}

2. 2. 하이퍼 연산과의 관계

덧셈, 곱셈, 그리고 거듭제곱과 같은 기본적인 산술 연산은 하이퍼 연산이라는 연산의 수열로 자연스럽게 확장될 수 있다. 커누스 윗화살표 표기법은 이러한 하이퍼 연산을 간결하게 나타내는 방법이다.

자연수

b

에 대해 곱셈은 덧셈을 반복하는 것으로 정의된다. 이는 하이퍼 연산에서

H_2(a,b)

에 해당한다.

:

\begin{matrix}a\times b = H_2(a,b) = & \underbrace{a+a+\dots+a} \\& b\mbox{ 개의 }a\end{matrix}

예를 들어,

3\times 4 = 4+4+4 = 12

이다.

자연수 지수

b

에 대한 거듭제곱은 곱셈을 반복하는 것으로 정의되며, 커누스는 이를 위쪽 화살표(↑) 한 개로 표기했다. 이는 하이퍼 연산에서

H_3(a,b)

에 해당한다. 일부 초기 컴퓨터에서는 위쪽 화살표를 거듭제곱 연산자로 사용하기도 했다.

:

\begin{matrix}a\uparrow b = H_3(a,b) = a^b = & \underbrace{a\times a\times\dots\times a}\\& b\mbox{ 개의 }a\end{matrix}

예를 들어,

4\uparrow 3 = 4^3 = 4\times 4\times 4 = 64

이다. 구골플렉스

10^{10^{100}}

는

10\uparrow(10\uparrow100)

으로 쓸 수 있다.

커누스는 연산의 수열을 거듭제곱 너머로 확장하기 위해, 거듭제곱의 반복인 테트레이션을 의미하는 "이중 윗화살표"(↑↑) 연산을 정의했다. 이는 하이퍼 연산에서

H_4(a,b)

에 해당한다.

:

\begin{matrix}a\uparrow\uparrow b = H_4(a,b) = {\ ^{b}a}  & = & \underbrace{a^{a^}}}} & = & \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))} \\& & b\mbox{ 개의 }a & & b\mbox{ 개의 }a\end{matrix}

이 연산은 오른쪽에서 왼쪽으로 계산한다. 즉,

a\uparrow\uparrow b = a\uparrow(a\uparrow\uparrow(b-1))

이다.

예를 들면,

:

\begin{matrix}4\uparrow\uparrow 3 & = {\ ^{3}4}  & = & 4^{4^4} & = & 4\uparrow (4\uparrow 4) & = & 4^{256} & \approx & 1.34078079\times 10^{154} \\& & 3\mbox{ 개의 }4 & & 3\mbox{ 개의 }4\end{matrix}

이 정의에 따라 계산하면 다음과 같다.

:

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^{3^{27}} = 3^{7625597484987} \approx 1.2580143\times 10^{3638334640024}

:

3\uparrow\uparrow 5 = 3^{3^{3^{3^3}}} = 3^{3^{3^{27}}} = 3^{3^{7625597484987}}

커누스는 이 표기법을 더 확장하여, 테트레이션의 반복인 펜테이션을 의미하는 "삼중 윗화살표"(↑↑↑) 연산을 정의했다. 이는 하이퍼 연산에서

H_5(a,b)

에 해당한다.

:

\begin{matrix}a\uparrow\uparrow\uparrow b = H_5(a,b) = & \underbrace{a\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))} \\& b\mbox{ 개의 }a\end{matrix}

잇따라 "사중 윗화살표"(↑↑↑↑) 연산은 펜테이션의 반복인 헥세이션을 의미한다. 이는 하이퍼 연산에서

H_6(a,b)

에 해당한다.

:

\begin{matrix}a\uparrow\uparrow\uparrow\uparrow b = H_6(a,b) = & \underbrace{a\uparrow\uparrow\uparrow (a\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow a))} \\& b\mbox{ 개의 }a\end{matrix}

이러한 방식으로 계속 확장할 수 있다. 일반적인 규칙은

n

개의 윗화살표 연산(

\uparrow^n

)은 오른쪽 결합 법칙을 따르는 (

n-1

)개의 윗화살표 연산(

\uparrow^{n-1}

)을

b

번 반복 적용하는 것으로 정의된다는 것이다. 이는 하이퍼 연산

H_{n+2}(a, b)

또는

a[n+2]b

와 같다.

:

\begin{matrix}a \uparrow^n b = H_{n+2}(a,b) = a\ \underbrace{\uparrow\uparrow\!\!\dots\!\!\uparrow}_{n}\ b = & \underbrace{a\ \underbrace{\uparrow\uparrow\!\!\dots\!\!\uparrow}_{n-1} \ (a\ \underbrace{\uparrow\uparrow\!\!\dots\!\!\uparrow}_{n-1} \ (\dots \ (a \underbrace{\uparrow\uparrow\!\!\dots\!\!\uparrow}_{n-1} a)\dots))}_{b\text{ 개의 }a}\end{matrix}

예시:

:

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

:

\begin{matrix}3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow(3\uparrow\uparrow 3) = 3\uparrow\uparrow(7,625,597,484,987) = & \underbrace{3 \uparrow (3 \uparrow (\dots \uparrow 3))} \\& 7,625,597,484,987\mbox{ 개의 }3\end{matrix}

2. 3. 다른 표기법과의 비교

커누스 윗화살표 표기법은 기본적인 수학 연산부터 매우 큰 수까지 표현할 수 있으며, 다른 큰 수 표기법들과 밀접한 관련이 있다.

단일 커누스 윗화살표(

\uparrow

)는 거듭제곱을 나타내고, 이중 커누스 윗화살표(

\uparrow\uparrow

)는 테트레이션을 나타낸다.

:

a\uparrow b = a^b

:

a\uparrow\uparrow b = {}^b a

또한, 여러 개의 화살표를 사용하는

\uparrow^n

표기법은 아커만 함수의 일반해를 나타내는 데 사용될 수 있다.

:

\operatorname {Ack} \left(n, b \right) = \left\{ 2 \uparrow^{n-2} \left(b+3 \right) \right\} - 3 \quad \mbox{if }n\ge 3

하이퍼 연산자는

\uparrow^n

표기법과 거의 동일하지만, 덧셈, 곱셈, 후속자 함수까지 포함하는 더 넓은 개념이다.

n \ge 3

일 때 두 표기법은 다음과 같은 관계를 가진다.

:

\operatorname {hyper} \left(a, n, b \right) = a \uparrow^{n-2} b \quad \mbox{if }n\ge 3

컨웨이의 사슬 화살표 표기법은 세 개의 숫자로 이루어진 경우 커누스 윗화살표 표기법과 동일한 값을 나타낸다.

:

a \to b \to n = a \uparrow^n b

하지만 컨웨이 표기법은 사슬을 더 길게 확장하여 커누스 윗화살표 표기법으로는 간결하게 나타내기 어렵거나 사실상 표현이 불가능한 매우 큰 수, 예를 들어 그레이엄 수와 같은 수를 표현할 수 있다.

배열 표기법 역시 세 개의 변수를 사용하는 경우에는 커누스 윗화살표 표기법과 동일하다.

:

\{a,b,n\} = a \uparrow^n b

배열 표기법은 변수의 개수를 늘림으로써 컨웨이 연쇄 화살표 표기법보다 훨씬 더 빠르게 수가 증가하는 강력한 표기법이다. 예를 들어, 4개의 변수를 사용하는 배열 표기법은 컨웨이 연쇄 화슬표 표기법과 비슷한 수준의 수를 나타내고, 5개 변수를 사용하면 컨웨이 확장 표기법 수준에 도달하며, 6개 이상의 변수를 사용하면 그 수준을 훨씬 뛰어넘는 수를 표현할 수 있다.

이 외에도 다각형 표기법이나 하이퍼 E 표기법 (확장 표기법 제외) 등 다른 큰 수 표기법들도 커누스 윗화살표 표기법과 비슷한 수준의 큰 수를 만들어내거나 유사한 증가 속도를 보이는 경우가 있다.

3. 정의 및 표기법

커누스 윗화살표 표기법은 덧셈, 곱셈, 거듭제곱과 같은 기본적인 산술 연산을 확장하는 하이퍼 연산 수열을 표기하기 위해 도널드 커누스가 고안한 방법이다. 이 표기법은 특히 테트레이션 이상의 매우 큰 수를 간결하게 나타내는 데 유용하다.

기본적인 아이디어는 연산의 반복을 윗화살표의 개수로 나타내는 것이다.

윗화살표 한 개( $a \uparrow b$ )는 $a$ 를 $b$ 번 곱하는 거듭제곱 $a^b$ 를 의미한다. 이는 하이퍼 연산에서 $H_3(a,b)$ 에 해당한다.
윗화살표 두 개( $a \uparrow\uparrow b$ )는 거듭제곱( $\uparrow$ )을 $b$ 번 반복하는 테트레이션 ${^b a}$ 를 의미한다. 이는 $H_4(a,b)$ 에 해당한다.
윗화살표 세 개( $a \uparrow\uparrow\uparrow b$ )는 테트레이션( $\uparrow\uparrow$ )을 $b$ 번 반복하는 펜테이션을 의미한다. 이는 $H_5(a,b)$ 에 해당한다.
일반적으로 윗화살표 $n$ 개( $a \uparrow^n b$ )는 ( $n-1$ )중 윗화살표 연산( $\uparrow^{n-1}$ )을 $b$ 번 반복하는 것을 의미하며, 이는 하이퍼 연산 $H_{n+2}(a,b)$ 와 동일하다.

커누스는 윗첨자를 사용한 거듭제곱 표기(

a^b

)가 테트레이션 이상으로 일반화하기 어렵다고 판단하여, 이러한 인라인(inline) 표기법

a \uparrow b

를 도입했다.

공식적으로 커누스 윗화살표 표기법은 정수

a, b, n

(

a \ge 0, n \ge 1, b \ge 0

)에 대해 다음과 같이 재귀적으로 정의된다.^[4]

:

a\uparrow^n b=\begin{cases}a^b, & \text{if }n=1; \\1, & \text{if }n>1\text{ and }b=0; \\a\uparrow^{n-1}(a\uparrow^{n}(b-1)), & \text{otherwise }\end{cases}

이 정의는 거듭제곱을 기본 연산으로 사용한다. 또는 곱셈을 기본 연산(

n=0

)으로 포함하여 정의할 수도 있다.

:

a\uparrow^n b=\begin{cases}a\times b, & \text{if }n=0; \\1, & \text{if }n>0\text{ and }b=0; \\a\uparrow^{n-1}(a\uparrow^{n}(b-1)), & \text{otherwise }\end{cases}

단,

a \ge 0, n \ge 0, b \ge 0

이다. 하지만 커누스 자신은

n=0

인 경우(

\uparrow^0

, 즉 곱셈)는 윗화살표 표기법으로 정의하지 않았다.

모든 윗화살표 연산은 거듭제곱과 마찬가지로 오른쪽 결합 법칙(right-associative)을 따른다. 즉, 연산은 오른쪽에서 왼쪽으로 계산되어야 한다. 예를 들어,

a \uparrow b \uparrow c

는

a \uparrow (b \uparrow c)

를 의미하며,

(a \uparrow b) \uparrow c

가 아니다.

3. 1. 기본 연산

덧셈, 곱셈, 거듭제곱과 같은 기본적인 산술 연산은 하이퍼 연산이라는 더 큰 연산 체계로 자연스럽게 확장될 수 있다.

자연수

b

에 대한 곱셈은 덧셈을

b

번 반복하는 것으로 정의된다.

:

\begin{matrix}a\times b & = & \underbrace{a+a+\dots+a} \\& & b\mbox{ 개의 }a\end{matrix}

예를 들어,

4 \times 3

은 4를 3번 더하는 것과 같다.

:

\begin{matrix}   4\times 3 & = & \underbrace{4+4+4} & = & 12\\& & 3\mbox{ 개의 }4\end{matrix}

자연수 지수

b

에 대한 거듭제곱은 곱셈을

b

번 반복하는 것으로 정의된다. 커누스는 이를 윗화살표 한 개(

\uparrow

)를 사용하여 표기했다.

:

\begin{matrix}a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\& b\mbox{ 개의 }a\end{matrix}

즉,

a \uparrow b

는

a

를

b

번 곱한 값, 즉

a

의

b

제곱(

a^b

)을 의미한다. 예를 들어,

4 \uparrow 3

은 4를 3번 곱하는 것과 같다.

:

\begin{matrix}4\uparrow 3= 4^3 = & \underbrace{4\times 4\times 4} & = & 64\\& 3\mbox{ 개의 }4\end{matrix}

이 표기법은 테트레이션과 같이 거듭제곱을 반복하는 더 큰 수를 나타내는 하이퍼 연산으로 자연스럽게 이어진다.

3. 2. 확장 연산

덧셈, 곱셈, 거듭제곱과 같은 기본적인 산술 연산은 하이퍼 연산이라는 더 큰 수열로 자연스럽게 확장될 수 있다. 거듭제곱

a^b

는

a

를

b

번 반복하여 곱하는 것으로 정의되며, 도널드 커누스는 이를 윗화살표 하나(

\uparrow

)를 사용하여

a \uparrow b

로 표기했다.

:

a\uparrow b = a^b = \underbrace{a\times a\times\dots\times a}_{b\text{ copies of }a}

커누스는 이 연산 수열을 거듭제곱 너머로 확장하기 위해, 거듭제곱의 반복인 테트레이션을 나타내는 "이중 윗화살표" 연산(

\uparrow\uparrow

)을 정의했다.

:

a\uparrow\uparrow b = {\ ^{b}a} = \underbrace{a^{a^}}}} _ {b\text{ copies of }a } = \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))}_{b\text{ copies of }a}

여기서 계산은 오른쪽에서 왼쪽으로 수행된다. 이는 커누스 윗화살표 연산이 거듭제곱과 마찬가지로 오른쪽 결합 법칙(right-associative)을 따르기 때문이다. 예를 들어

a \uparrow b \uparrow c

는

a \uparrow (b \uparrow c)

를 의미하며,

(a \uparrow b) \uparrow c

가 아니다.

이 정의에 따른 예시는 다음과 같다.

$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^{3^{27}} = 3^{7625597484987} \approx 1.258 \times 10^{3638334640024}$
$4\uparrow\uparrow 3 = 4^{4^4} = 4^{256} \approx 1.34078079\times 10^{154}$

커누스는 이 표기법을 더욱 확장하여, 테트레이션의 반복인 펜테이션을 나타내는 "삼중 윗화살표" 연산(

\uparrow\uparrow\uparrow

)을 정의했다.

:

a\uparrow\uparrow\uparrow b = \underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}_{b\text{ copies of }a}

잇따라, 펜테이션의 반복인 헥세이션은 "사중 윗화살표" 연산(

\uparrow\uparrow\uparrow\uparrow

)으로 정의된다.

:

a\uparrow\uparrow\uparrow\uparrow b = \underbrace{a_{}\uparrow\uparrow\uparrow (a\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow a))}_{b\text{ copies of }a}

이러한 확장은 계속될 수 있다. 일반적인 규칙은

n

개의 윗화살표 연산(

a \uparrow^n b

)은 (

n-1

)개의 윗화살표 연산(

a \uparrow^{n-1}

)을

b

번 반복하는 것으로 정의된다는 것이다. 이는 오른쪽 결합 법칙을 따른다.

:

\begin{matrix}a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}_{n}\ b=\underbrace{a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow}_{n-1}\ (a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1}\ (\dots\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1}\ a))}_{b\text{ copies of }a}\end{matrix}

예를 들면 다음과 같다.

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

\begin{matrix}3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow(3\uparrow\uparrow 3) = 3\uparrow\uparrow(7,625,597,484,987) = &\underbrace{3^{3^{.^{.^{.^3}}}}} \\& \mbox{7,625,597,484,987 copies of 3}\end{matrix}

표기

a \uparrow^n b

는

a

와

b

사이에

n

개의 윗화살표가 있는 것을 나타낸다. 이는 하이퍼 연산

H_{n+2}(a,b)

또는

a[n+2]b

와 동일하다. 예를 들어,

a \uparrow b

는

a \uparrow^1 b = H_3(a,b) = a[3]b = a^b

이고,

a \uparrow\uparrow b

는

a \uparrow^2 b = H_4(a,b) = a[4]b

이다.

3. 3. 계산 규칙

모든 윗화살표 연산(일반적인 거듭제곱

a \uparrow b

포함)은 오른쪽 결합 연산(right associative)이다. 즉, 여러 윗화살표 연산이 연달아 나올 경우, 수식의 오른쪽 부분부터 계산해야 한다.^[4]

이를 수식으로 표현하면 다음과 같다. 여기서

\uparrow^n

은 윗화살표가

n

개 있는 연산을 의미한다.

:

a \uparrow^n b \uparrow^n c = a \uparrow^n (b \uparrow^n c)

예를 들어,

3 \uparrow 2 \uparrow 3

을 계산해 보자. 오른쪽 결합 법칙에 따라 오른쪽의

2 \uparrow 3

을 먼저 계산해야 한다.

:

3 \uparrow 2 \uparrow 3 = 3 \uparrow (2 \uparrow 3)

:

2 \uparrow 3

은

2^3

과 같으므로 8이다. 따라서,

:

3 \uparrow (2 \uparrow 3) = 3 \uparrow 8 = 3^8 = 6561

이 된다.

만약 왼쪽부터 계산한다면

(3 \uparrow 2) \uparrow 3

이 되는데, 이는

(3^2) \uparrow 3 = 9 \uparrow 3 = 9^3 = 729

로 계산된다. 이 값은 올바른 계산 결과인 6561과 다르다.

테트레이션 (

\uparrow\uparrow

)의 경우도 마찬가지이다.

3\uparrow\uparrow 3

을 계산하면 다음과 같다.

:

3\uparrow\uparrow 3 = 3 \uparrow (3 \uparrow 3)

:

3 \uparrow 3

은

3^3 = 27

이므로,

:

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

이다.

만약 왼쪽부터 계산한다면

(3 \uparrow 3) \uparrow 3

이 되는데, 이는

(3^3) \uparrow 3 = 27 \uparrow 3 = 27^3 = 19683

으로 계산되어 올바른 값과 크게 달라진다.

이러한 오른쪽 결합 규칙은

a \uparrow^n b

의 재귀적 정의와도 일치한다.

b \ge 1, n \ge 1

일 때,

:

a \uparrow^n b = a \uparrow^{n-1} (a \uparrow^n (b-1))

이 정의는

a \uparrow^n b

를 계산하기 위해 먼저 오른쪽의

a \uparrow^n (b-1)

을 계산해야 함을 보여준다. 이를 반복하면 결국 가장 오른쪽의 연산부터 차례대로 계산하게 된다.

:

a \uparrow^n b = a \uparrow^{n-1} (a \uparrow^{n-1} (\dots (a \uparrow^{n-1} a)\dots))

(여기서

a

는

b

번 나타난다)

3. 4. 대체 표기법

''a''^''b''와 같은 거듭제곱 표기는 보통 지수 ''b''를 밑수 ''a''의 윗첨자로 작성한다. 그러나 프로그래밍 언어나 일반 텍스트 이메일과 같은 많은 환경에서는 윗첨자 활자를 지원하지 않는다. 이러한 환경에서는 커누스 윗화살표 표기법의 선형 표기법인 ''a'' ↑ ''b''를 적용하는 대신, 캐럿(^) 기호를 사용하여 `a^b`와 같이 표기하기도 한다. 윗화살표 기호(↑) 자체도 특정 문자 집합이나 글꼴에 따라서는 포함되어 있지 않거나 제대로 표시되지 않는 경우가 있기 때문이다.

윗화살표가 여러 개 사용되는 경우에도 마찬가지로 캐럿을 반복해서 사용하는 방식으로 대체 표기할 수 있다.

''a'' ↑ ''b''는 `a^b`로 표기한다.
''a'' ↑↑ ''b''는 `a^^b`로 표기한다.
''a'' ↑↑↑ ''b''는 `a^^^b`로 표기한다.
일반적으로 ''a'' ↑^''n'' ''b''는 `a` 다음에 `^` 기호를 ''n''번 반복하고 `b`를 쓰는 방식으로 표기할 수 있다.

이러한 캐럿을 이용한 표기법은 도널드 커누스 자신도 대체적이거나 간편한 표기법으로 인정한 바 있다.

4. 윗화살표 표기법을 거듭제곱으로 표현

커누스 윗화살표 표기법을 익숙한 거듭제곱의 위첨자 표기법을 사용하여 나타내면, 매우 높은 거듭제곱의 탑 형태가 된다.

$a \uparrow \uparrow b$ 는 $a$ 를 $b$ 번 거듭제곱한 탑으로 표현할 수 있다.

: $a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}$

예를 들어, $a \uparrow \uparrow 4$ 는 다음과 같다.

: $a \uparrow \uparrow 4 = a \uparrow (a \uparrow (a \uparrow a)) = a^{a^{a^a}}$

만약 $b$ 가 변수이거나 너무 큰 수라면, 거듭제곱의 탑은 점 표기(...)와 탑의 높이( $b$ )를 명시하여 나타낸다.

윗화살표 세 개를 사용한 $a \uparrow \uparrow \uparrow b$ 는 이러한 거듭제곱의 탑을 여러 층으로 쌓아 올린 형태로 표현할 수 있다. 각 층의 높이는 바로 아래층의 결과값으로 결정된다.

: $a \uparrow \uparrow \uparrow b = \left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b$

예를 들어, $a \uparrow \uparrow \uparrow 4$ 는 다음과 같이 표현된다.

: $a \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow (a \uparrow \uparrow (a \uparrow \uparrow a)) = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a} }}$

여기서도 $b$ 가 변수이거나 너무 크다면, 점 표기와 함께 전체 스택의 높이( $b$ )를 표시한다.

더 나아가, 윗화살표 네 개를 사용한 $a \uparrow \uparrow \uparrow \uparrow b$ 는 거듭제곱 탑의 스택을 $b$ 번 반복하여 쌓은 형태로 표현할 수 있다.

: $a \uparrow \uparrow \uparrow \uparrow b = \underbrace{ \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \cdots \right\} a }_{b}$

예를 들어, $a \uparrow \uparrow \uparrow \uparrow 4$ 는 다음과 같다.

: $a \uparrow \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow a)) = \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} a$

이러한 방식으로 윗화살표의 개수( $n$ )가 늘어날수록, 거듭제곱의 반복적인 중첩 구조를 사용하여 $a \uparrow^n b$ 를 표현할 수 있다. 이는 매우 큰 수를 시각적으로 이해하는 데 도움을 주지만, 표기가 상당히 복잡해질 수 있다.

4. 1. 테트레이션을 사용한 표현

테트레이션을 위한 루디 러커 표기법

^{b}a

는 윗화살표 표기법으로 나타낸 매우 큰 수를 기하학적 표현(테트레이션 타워)을 사용하여 다소 간결하게 나타낼 수 있게 한다.^[7]

커누스는 이중 화살표를 테트레이션(거듭제곱의 반복) 연산자로 정의했다.

:

a\uparrow\uparrow b = {}^{b}a = \underbrace{a^{a^}}}}_ {b\text{ 개의 }a }

이 표기법을 사용하면 다음과 같이 표현할 수 있다.

$a \uparrow \uparrow b = { }^{b}a$
$a \uparrow \uparrow \uparrow b = \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{b}$
$a \uparrow \uparrow \uparrow \uparrow b = \left. \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{\vdots}_{a} }} \right\} b$

예를 들어, 네 번째 아커만 수

4 \uparrow^4 4

는 다음과 같이 나타낼 수 있다.

:

4 \uparrow^4 4 = \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{4} }} = \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ ^{^{^{4}4}4}4 }}

구체적인 계산 예시는 다음과 같다.

$2\uparrow\uparrow2 = {}^2 2 = 2^2=4$
$2\uparrow\uparrow3 = {}^3 2 = 2^{2^2}=2^{4}=16$
$2\uparrow\uparrow4 = {}^4 2 = 2^{2^{2^2}}=2^{2^{4}}=2^{16}=65,536$
$2\uparrow\uparrow5 = {}^5 2 = 2^{2^{2^{2^2}}}=2^{2^{16}}=2^ \approx 2.003\times 10^{19,728}$
$3\uparrow\uparrow2 = {}^2 3 = 3^3=27$
$3\uparrow\uparrow3 = {}^3 3 = 3^{3^3}=3^{27}=7,625,597,484,987$
$3\uparrow\uparrow4 = {}^4 3 = 3^{3^{3^3}}=3^{3^{27}}=3^{7,625,597,484,987} \approx 1.258\times 10^{3,638,334,640,024}$
$10\uparrow\uparrow3 = {}^{3}10 = 10^{10^{10}} = 10^{10,000,000,000}$ (1 다음에 0이 100억 개)
$10\uparrow\uparrow4 = {}^{4}10 = 10^{10^{10^{10}}} = 10^{10^{10,000,000,000}}$

5. 예제 및 값의 표

커누스 윗화살표 표기법은 매우 큰 수를 간결하게 나타내기 위해 사용된다. 몇 가지 예를 통해 이 표기법이 어떻게 작동하는지 살펴보자.

$a \uparrow \uparrow b$ 는 테트레이션을 나타내며, 거듭제곱을 반복하는 것을 의미한다. 이를 익숙한 윗첨자 표기법으로 쓰면 거듭제곱이 탑처럼 쌓이는 형태가 된다.

: 예: $a \uparrow \uparrow 4 = a \uparrow (a \uparrow (a \uparrow a)) = a^{a^{a^a}}$

만약 ''b''가 아주 큰 수라면, 거듭제곱 탑을 모두 쓰기 어려우므로 점(...)을 사용하고 탑의 높이(거듭제곱 횟수)를 표시한다.

: $a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}$ (''a''가 ''b''번 거듭제곱됨)

$a \uparrow \uparrow \uparrow b$ 는 펜테이션을 나타내며, 테트레이션( $\uparrow\uparrow$ )을 반복하는 연산이다. 이는 거듭제곱 탑들의 스택(stack)으로 표현될 수 있으며, 각 탑의 높이가 이전 탑의 결과값으로 결정된다.

: $a \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow (a \uparrow \uparrow (a \uparrow \uparrow a)) =\underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a} }}$

마찬가지로 ''b''가 아주 크면, 스택 역시 점과 스택의 높이를 나타내는 표시로 써야 할 수 있다.

: $a \uparrow \uparrow \uparrow b =\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b$ (거듭제곱 탑이 ''b''층으로 쌓임)

더 나아가, $a \uparrow \uparrow \uparrow \uparrow b$ 는 헥세이션을 나타내며, 펜테이션( $\uparrow\uparrow\uparrow$ )을 반복하는 연산이다. 이는 거듭제곱 탑 스택들의 열(row)로 생각할 수 있다.

: $a \uparrow \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow a)) =\left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}\underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}\underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}a$

일반적으로 $a \uparrow^n b$ 는 $(n-1)$ 중 화살표 연산을 ''b''번 반복하는 것을 의미한다^[7].

: $a \underbrace{\uparrow\uparrow\cdots \cdots \cdots \uparrow}_{n \text{ 개의 화살표} } b= \underbrace{a\underbrace{\uparrow\uparrow \cdots \cdots \cdots \cdots \uparrow}_{(n-1) \text{ 개의 화살표} }a\underbrace{\uparrow\uparrow \cdots \cdots \cdots \cdots \uparrow}_{(n-1) \text{ 개의 화살표} }\cdots a \underbrace{\uparrow\uparrow \cdots \cdots \cdots \cdots \uparrow}_{(n-1) \text{ 개의 화살표} } a}_ {b\text{ 개의 }a }$

모든 윗화살표 연산은 오른쪽부터 계산하는 오른쪽 결합 법칙(right associative)을 따른다. 즉, $a \uparrow b \uparrow c$ 는 $a \uparrow (b \uparrow c)$ 를 의미하며, $(a \uparrow b) \uparrow c$ 와는 다르다.

: 예: $3\uparrow\uparrow 3=3^{3^3}$ 는 $3^{(3^3)}=3^{27}=7,625,597,484,987$ 이다. 이는 $\left(3^3\right)^3=27^3=19,683$ 과는 매우 다른 값이다.

아래 하위 섹션에서는 밑이 2, 3, 4, 10인 경우에 대한 구체적인 계산 값의 표와 예제를 보여준다.

5. 1. 2↑^''m'' ''n'' 계산

2\uparrow^m n

을 계산하는 것은 무한한 표로 나타낼 수 있다.

2^n

을 가장 윗 행에 채우고, 왼쪽 열은 2로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽 칸의 값을 확인하고, 그 값을 ''k''라고 할 때, 바로 윗 행의 ''k''번째 열에 있는 값을 가져와 현재 칸에 채운다.

$2\uparrow^m n$ = hyper(2, ''m'' + 2, ''n'') = 2 → ''n'' → ''m''의 값
m\n	1	2	3	4	5	6	공식
1	2	4	8	16	32	64	$2^n$ (거듭제곱)
2	2	4	16	65536	$2^{65536}\approx 2.0 \times 10^{19728}$	$2^{2^{65536}}\approx 10^{6.0 \times 10^{19727}}$	$2\uparrow\uparrow n$ (테트레이션)
3	2	4	65536
4	2	4		$2\uparrow\uparrow\uparrow\uparrow n$ (헥세이션)

이 표는 아커만 함수의 표와 유사하며, $m$ 과 $n$ 의 시작값이 다르고 모든 값에 3을 더한 형태와 관련이 있다.

특히 $m=2$ 일 때, 즉 테트레이션 $2\uparrow\uparrow n$ 의 값은 다음과 같이 계산된다.^[7]

$2\uparrow\uparrow1 = 2$
$2\uparrow\uparrow2 = 2 \uparrow (2\uparrow\uparrow1) = 2 \uparrow 2 = 2^2 = 4$
$2\uparrow\uparrow3 = 2 \uparrow (2\uparrow\uparrow2) = 2 \uparrow 4 = 2^4 = 16$
$2\uparrow\uparrow4 = 2 \uparrow (2\uparrow\uparrow3) = 2 \uparrow 16 = 2^{16} = 65536$
$2\uparrow\uparrow5 = 2 \uparrow (2\uparrow\uparrow4) = 2 \uparrow 65536 = 2^{65536} \approx 2.003\times 10^{19728}$
$2\uparrow\uparrow6 = 2 \uparrow (2\uparrow\uparrow5) = 2 \uparrow 2^{65536} = 2^{2^{65536}} \approx 10^{6.0 \times 10^{19727}}$ (표의 $m=2, n=6$ 값)

5. 2. 3↑^''m'' ''n'' 계산

3^n

을 가장 윗 행에 채우고, 왼쪽 열에 3으로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 얻어서 이전 행의 그 값의 위치에 있는 값을 얻는다.

$3\uparrow^m n$ = hyper(3, ''m'' + 2, ''n'') = 3 → n → m의 값
m\n	1	2	3	4	5	공식
1	3	9	27	81	243	$3^n$
2	3	27	7,625,597,484,987	$3^{7{,}625{,}597{,}484{,}987}\approx 1.3 \times 10^{3{,}638{,}334{,}640{,}024}$	$3^{3^{7{,}625{,}597{,}484{,}987}}$	$3\uparrow\uparrow n$
3	3	7,625,597,484,987
4	3	$\begin{matrix}$	$3\uparrow\uparrow\uparrow\uparrow n$

여기서 이중 화살표는 테트레이션 (거듭제곱의 반복)을 나타내는 연산자이다^[7].

: $a\uparrow\uparrow b= \underbrace{a \uparrow a \uparrow \cdots \uparrow a}_ {b\text{ copies of }a }= \underbrace{a^{a^}}}}_ {b\text{ copies of }a }$

이것을 사용하여 $3\uparrow\uparrow n$ (표의 m=2 행)의 몇 가지 값을 계산하면 다음과 같다.

: $3\uparrow\uparrow2 = 3^3=27$

: $3\uparrow\uparrow3 = 3^{3^3}=3^{27}=7625597484987$

: $3\uparrow\uparrow4 = 3^{3^{3^3}}=3^{3^{27}}=3^{7625597484987} \approx 1.258\times 10^{3638334640024}$

5. 3. 4↑^''m'' ''n'' 계산

4^b

의 값들을 맨 윗줄에 놓고, 맨 왼쪽 열을 4로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 가져와서, 이전 행의 해당 값 위치에 있는 값을 찾으면 된다.

$4\uparrow^n b$ = $H_{n+2}(4,b)$ = $4[n+2]b$ = 4 → b → n의 값
n\b	1	2	3	4	5	공식
1	4	16	64	256	1024	$4^b$
2	4	256	$4^{256}\approx 1.34 \times 10^{154}$	$4^{4^{256}}\approx 10^{8.0 \times 10^{153}}$	$4^{4^{4^{256}}}$	$4\uparrow\uparrow b$ (테트레이션)
3	4	$4^{4^{256}}\approx 10^{8.0 \times 10^{153}}$
4	4		$4\uparrow\uparrow\uparrow\uparrow b$

예를 들어, 이중 화살표는 테트레이션(거듭제곱의 반복)을 나타낸다.^[7]

$4\uparrow\uparrow 1 = 4^1 = 4$
$4\uparrow\uparrow 2 = 4^4 = 256$
$4\uparrow\uparrow 3 = 4^{4^4} = 4^{256} \approx 1.34 \times 10^{154}$
$4\uparrow\uparrow 4 = 4^{4^{4^4}} = 4^{4^{256}} \approx 10^{8.0 \times 10^{153}}$

세제곱 화살표(

\uparrow\uparrow\uparrow

) 이상부터는 값이 매우 빠르게 커져서 일반적인 표기법으로 나타내기 어렵다.

5. 4. 10↑^''m'' ''n'' 계산

10^n

을 가장 윗 행에 채우고, 왼쪽 열에 10으로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 얻어서 이전 행의 그 값의 위치에 있는 값을 얻는다.

$10\uparrow^m n$ = 하이퍼 연산(10, ''m'' + 2, ''n'') = 10 → ''n'' → ''m''의 값
m\n	1	2	3	4	5	공식
1	10	100	1,000	10,000	100,000	$10^n$
2	10	10,000,000,000	$10^{10,000,000,000}$	$10^{10^{10,000,000,000}}$	$10^{10^{10^{10,000,000,000}}}$	$10\uparrow\uparrow n$ (테트레이션)
3	10	$\underbrace{10^{10^{.^{.^{.^{10}}}}}}_ {10\mbox{ copies of }10}$	$\underbrace{10^{10^{.^{.^{.^{10}}}}}}_ {\underbrace{10^{10^{.^{.^{.^{10}}}}}}_ {10\mbox{ copies of }10}}$	$\underbrace{10^{10^{.^{.^{.^{10}}}}}}_ {\underbrace{10^{10^{.^{.^{.^{10}}}}}}_ {\underbrace{10^{10^{.^{.^{.^{10}}}}}}_ {10\mbox{ copies of }10}}}$		$10\uparrow\uparrow\uparrow n$
4	10	$\underbrace{^{^{^{^{^{10}.}.}.}10}10}_{10\mbox{ copies of }10}$	$\underbrace{^{^{^{^{^{10}.}.}.}10}10}_{\underbrace{^{^{^{^{^{10}.}.}.}10}10}_{10\mbox{ copies of }10}}$			$10\uparrow\uparrow\uparrow\uparrow n$

예를 들어, 이중 화살표( $\uparrow\uparrow$ )는 테트레이션 (거듭제곱의 반복)을 나타낸다^[7]:

: $a\uparrow\uparrow b = \underbrace{a^{a^}}}}_ {b\text{ copies of }a }$

이를 이용하여 $10\uparrow\uparrow n$ (표의 ''m''=2 행)의 값을 계산하면 다음과 같다.

: $10\uparrow\uparrow 2 = 10^{10} = 10,000,000,000$ (100억)

: $10\uparrow\uparrow 3 = 10^{10^{10}} = 10^{10,000,000,000}$ (10의 100억 제곱)

: $10\uparrow\uparrow 4 = 10^{10^{10^{10}}} = 10^{10^{10,000,000,000}}$

표에서 2 ≤ ''n'' ≤ 9일 때 $10\uparrow^m n$ 의 수치적인 순서는 ''m''이 가장 우선적인 사전식 순서이다. 따라서 이 8개의 열에서 수치적인 순서는 단순히 행의 순서대로 정렬된다. 3 ≤ ''n'' ≤ 99인 97개의 열에도 마찬가지로 적용되며, ''m'' = 1에서 시작하면 3 ≤ ''n'' ≤ 9,999,999,999까지 가능하다.

6. 일반화 및 활용

어떤 수는 너무 커서 커누스 윗화살표 표기법으로 표현하기 어려울 수 있다. 이런 경우, 여러 개의 화살표를 한 번에 나타내는 ''n''중 화살표 연산( $\uparrow^n$ )이나 이와 동일한 하이퍼 연산이 유용하게 사용될 수 있다. 이는 화살표의 개수가 변수인 경우를 나타낼 때도 편리하다.

수가 너무 커서 ''n''중 화살표 표기법으로도 부족할 때는 콘웨이가 고안한 콘웨이 연쇄 화살표 표기법을 사용할 수 있다. 세 개의 요소로 이루어진 연쇄 화살표는 다른 표기법들과 동일한 값을 나타내지만, 연쇄의 길이가 4 이상이 되면 훨씬 더 강력한 표현력을 갖는다. 커누스 윗화살표, 하이퍼 연산, 콘웨이 연쇄 화살표 사이에는 다음과 같은 관계가 성립한다.

: $\begin{matrix}a\uparrow^n b & = & a [n+2] b & = & a\to b\to n \\\mbox{(커 누 스 )} & & \mbox{(하 이 퍼 연 산 )} & & \mbox{(콘 웨 이 )}\end{matrix}$

루벤 루이스 굿스타인은 하이퍼 연산 수열( $+, \times, \uparrow, \uparrow\uparrow, \dots$ )을 이용하여 음이 아닌 정수를 표현하는 독자적인 기수법 체계인 hereditary 표현(hereditary representation)을 만들었다.^[13] 이 표현 방식은 굿스타인 수열과 같은 수학적 개념을 정의하는 데 활용된다.

더욱 빠르게 증가하는 함수들을 체계적으로 분류하고 이해하기 위해 서수 분석의 일종인 빠르게 증가하는 계층과 같은 개념이 사용된다. 이 계층은 매우 빠르게 증가하는 함수들을 단계적으로 생성하며, 아커만 함수나 그레이엄 수와 같은 거대한 수와 관련된 함수들을 포함한다. 이러한 함수들은 대부분 계산 가능한 함수이지만, 바쁜 비버 함수와 같이 계산 불가능할 정도로 빠르게 증가하여 어떤 윗화살표 표기법이나 서수 기반 분석으로도 완전히 표현하거나 이해하기 어려운 함수들도 존재한다.

일반적으로 커누스 윗화살표 표기법은 비교적 작은 수를 나타내는 데 사용되고, 그보다 더 큰 수를 나타낼 때는 하이퍼 연산이나 콘웨이 연쇄 화살표 표기법이 더 적합하다고 여겨진다.

6. 1. 하이퍼 연산

덧셈, 곱셈, 거듭제곱과 같은 기본적인 산술 연산은 자연스럽게 하이퍼 연산이라는 연산의 서열(sequence)로 확장될 수 있다. 하이퍼 연산은 보통

H_n(a, b)

또는

a[n]b

형태로 표기한다.

H₁ (덧셈): $H_1(a,b) = a+b = a + \underbrace{1+1+\dots+1}_{b\text{ 개의 }1}$ (1을 b번 더함)
H₂ (곱셈): $H_2(a,b) = a\times b = \underbrace{a+a+\dots+a}_{b\text{ 개의 }a}$ (a를 b번 더함)
H₃ (거듭제곱): $H_3(a,b) = a^b = \underbrace{a\times a\times\dots\times a}_{b\text{ 개의 }a}$ (a를 b번 곱함)

커누스 윗화살표 표기법은 이 하이퍼 연산 서열을 거듭제곱 너머로 확장한 것이다.

하나의 윗화살표 (거듭제곱): $a\uparrow b = a^b = H_3(a,b)$
두 개의 윗화살표 (테트레이션): $a\uparrow\uparrow b = H_4(a,b) = \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))}_{b\text{ 개의 }a} = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^a}}}}}_{b\text{ 개의 }a}$ (거듭제곱의 반복)
세 개의 윗화살표 (펜테이션): $a\uparrow\uparrow\uparrow b = H_5(a,b) = \underbrace{a\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}_{b\text{ 개의 }a}$ (테트레이션의 반복)
네 개의 윗화살표 (헥세이션): $a\uparrow\uparrow\uparrow\uparrow b = H_6(a,b) = \underbrace{a\uparrow\uparrow\uparrow (a\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow a))}_{b\text{ 개의 }a}$ (펜테이션의 반복)

일반적으로,

n

개의 윗화살표 연산(

a \uparrow^n b

)은

(n-1)

개의 윗화살표 연산을

b

번 반복하는 것으로 정의되며, 이는 하이퍼 연산

H_{n+2}(a,b)

또는

a[n+2]b

와 같다. 즉, 다음과 같은 관계가 성립한다.

:

a \uparrow^n b = H_{n+2}(a,b) = a[n+2]b

예를 들어,

39\uparrow\uparrow14

는 하이퍼 연산으로

39[4]14

로 쓸 수 있다. 이는 테트레이션을 의미하며,

39[2]14 = 39 \times 14 = 546

과는 전혀 다른 값이다. 비슷하게,

77 \uparrow^{77} 77

은

77[77+2]77 = 77[79]77

을 의미한다.

커누스 윗화살표 표기법, 하이퍼 연산, 그리고 콘웨이 연쇄 화살표 표기법 사이에는 다음과 같은 관계가 있다.

:

\begin{matrix}a\uparrow^n b & = & a [n+2] b & = & a\to b\to n \\\mbox{(커 누 스 )} & & \mbox{(하 이 퍼 연 산 )} & & \mbox{(콘 웨 이 )}\end{matrix}

보통 커누스 윗화살표는 비교적 작은 수에, 연쇄 화살표나 하이퍼 연산은 더 큰 수를 표기할 때 사용된다.

6. 2. 콘웨이 연쇄 화살표 표기법

커누스 윗화살표 표기법으로도 표현하기 어려운 매우 큰 수가 존재한다. 이러한 수를 나타내기 위해 존 콘웨이가 고안한 콘웨이 연쇄 화살표 표기법을 사용할 수 있다.

콘웨이 연쇄 화살표 표기법에서 세 개의 숫자로 이루어진 연쇄 화살표는 커누스 윗화살표 표기법과 동일한 값을 나타낸다. 구체적인 관계는 다음과 같다.

:

a \uparrow^n b = a \to b \to n

여기서

a \uparrow^n b

는 커누스 윗화살표 표기법이고,

a \to b \to n

는 콘웨이 연쇄 화살표 표기법이다.

하지만 콘웨이 연쇄 화살표 표기법은 항의 개수가 4개 이상으로 확장될 수 있으며, 이 경우 커누스 윗화살표 표기법보다 훨씬 더 강력한 표현력을 가진다. 이를 통해 커누스 윗화살표 표기법으로는 간결하게 나타내기 어렵거나 현실적으로 표현하기 힘든 매우 큰 수, 예를 들어 그레이엄 수와 같은 수를 표현할 수 있다.

일반적으로 커누스 윗화살표는 비교적 작은 수에, 연쇄 화살표나 하이퍼 연산은 더 큰 수에 사용해야 한다고 주장되기도 한다.

6. 3. 그레이엄 수

커누스 윗화살표 표기법은 수학적 증명 과정에서 등장한 매우 큰 수인 그레이엄 수

G^{64}(4)

를 표기하는 데 사용된다. 그레이엄 수는 이름이 붙은 자연수 중에서 수학적 의미를 갖고 있는 가장 큰 수로 알려져 있다.

이를 커누스 윗화살표 표기법으로 나타내면 다음과 같다.

G^{64}(4) = 3 \uparrow^{G^{63}(4)} 3 = 3 \underbrace{\uparrow \uparrow \dots \uparrow}_{G^{63}(4)\text{개}} 3

여기서 윗화살표(

\uparrow

)의 개수는

G^{63}(4)

개이며, 이 값 자체도 상상하기 어려울 정도로 매우 큰 수이다.

G^{n}(4)

는 재귀적으로 정의되는데,

G^1(4) = 3 \uparrow\uparrow\uparrow\uparrow 3 = 3 \uparrow^4 3

이고,

G^n(4) = 3 \uparrow^{G^{n-1}(4)} 3

(단,

n \ge 2

)이다.

그레이엄 수와 같이 커누스 윗화살표 표기법만으로는 간결하게 나타내기 어렵거나 현실적으로 표현하기 어려운 큰 수를 표현하기 위해 콘웨이 연쇄 화살표 표기법과 같은 더 강력한 표기법이 사용되기도 한다.

6. 4. 굿스타인 수열

루벤 루이스 굿스타인은 커누스 화살표와는 다른 표기법 체계를 사용하여 하이퍼 연산 수열(

+, \times, \uparrow, \uparrow\uparrow, \dots

)을 나타냈다.^[13] 그는 이 하이퍼 연산 수열을 이용해 음이 아닌 정수에 대한 기수법의 일종인 hereditary 표현(hereditary representation)을 만들었다. 이 표현 방식은 굿스타인 수열의 정의에 사용된다.

굿스타인의 표기법에서 대괄호 `[1]`, `[2]`, `[3]`, `[4]`, ...는 각각 하이퍼 연산

+, \times, \uparrow, \uparrow\uparrow, \dots

를 나타낸다. 어떤 정수 ''n''을 밑 ''b''로 하는 ''k''단계 완전 hereditary 표현은 다음과 같은 규칙으로 만들어진다. 이 표현은 처음 ''k''개의 하이퍼 연산과 숫자 0, 1, ..., ''b''-1, 그리고 밑 ''b'' 자신만을 사용한다.

0 ≤ ''n'' ≤ ''b''-1 인 경우: ''n''은 단순히 해당하는 숫자로 표현된다.
''n'' > ''b''-1 인 경우: ''n''의 표현은 재귀적으로 찾아진다. 먼저 ''n''을 다음과 같은 형태로 나타낸다.

:

n = b [k] x_k [k-1] x_{k-1} [k-2] \dots [2] x_2 [1] x_1

여기서 ''x''_''k'', ..., ''x''₁는 다음 조건을 (차례대로) 만족하는 가장 큰 정수이다.

:

b [k] x_k \le n

:

b [k] x_k [k-1] x_{k-1} \le n

:

\dots

:

b [k] x_k [k-1] x_{k-1} [k-2] \dots [2] x_2 [1] x_1 \le n

만약 어떤 ''x''_''i''가 ''b''-1보다 크다면, 그 ''x''_''i''도 같은 방식으로 다시 표현한다. 이 과정을 숫자 0, 1, ..., ''b''-1과 밑 ''b''만 남을 때까지 반복한다.

계산할 때는 고차 연산(더 높은 단계의 하이퍼 연산)에 높은 우선순위를 부여하여 불필요한 괄호를 피할 수 있다. 따라서 각 단계별 표현은 다음과 같은 형태를 가진다.

1단계 표현: $b [1] X$ 형태. (''X''도 이 형태)
2단계 표현: $b [2] X [1] Y$ 형태. (''X'', ''Y''도 이 형태)
3단계 표현: $b [3] X [2] Y [1] Z$ 형태. (''X'', ''Y'', ''Z''도 이 형태)
4단계 표현: $b [4] X [3] Y [2] Z [1] W$ 형태. (''X'', ''Y'', ''Z'', ''W''도 이 형태)
이런 식으로 계속된다.

밑이 ''b''인 hereditary 표현에서는 밑 ''b'' 자체가 {0, 1, ..., ''b''-1}의 "자릿수"처럼 표현에 등장하는 점이 특징이다. 이는 밑을 ''b''로 하는 일반적인 기수법과 비교된다. 예를 들어, 일반적인 이진법에서 6은

(110)_2 = 2^2 + 2^1

로 표현된다. 반면, 밑이 2인 3단계 hereditary 표현으로 6을 나타내면 다음과 같다.

6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0)

Hereditary 표현은

[1] 0

(덧셈 항등원),

[2] 1

(곱셈 항등원),

[3] 1

(거듭제곱 항등원) 등과 같이 연산 결과에 영향을 주지 않는 항들을 제거하여 간략하게 만들 수 있다. 예를 들어, 위에서 보인 밑이 2인 6의 3단계 표현은

2 [3] 2 [1] 2

로 간단히 할 수 있다.

'''예시: 266의 hereditary 표현'''

정수 266을 밑 2로 표현하는 유일한 1, 2, 3, 4, 5단계 hereditary 표현은 다음과 같다.

1단계: $266 = 2 [1] 2 [1] 2 [1] \dots [1] 2$ (2가 133개)
2단계: $266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)$
3단계: $266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2$
4단계: $266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2$
5단계: $266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2$

6. 5. 빠르게 증가하는 함수

어떤 숫자들은 너무 커서 커누스 윗화살표 표기법의 여러 화살표를 사용하는 것이 번거로워진다. 이럴 때는 ''n''-화살표 연산자

\uparrow^n

가 유용하며, 이는 초연산과 동일한 개념이다.

예를 들어,

6\uparrow\uparrow4

는

\underbrace{6^{6^{.^{.^{.^{6}}}}}}_{4}

를 의미하며, 이는

6^{6^{6^{6}}}

과 같다. 이 값은

6^{6^{46,656}}

으로 계산되어 매우 큰 수가 된다.

숫자가 너무 커서 ''n''-화살표 표기법으로도 표현하기 어려울 때는 콘웨이 연쇄 화살표 표기법을 사용할 수 있다. 이 표기법에서 세 개의 요소로 이루어진 연쇄는 다른 표기법과 동일한 수준의 수를 나타내지만, 네 개 이상의 요소로 이루어진 연쇄는 훨씬 더 강력한 표현력을 가진다.

커누스 윗화살표, 초연산, 콘웨이 연쇄 화살표 표기법 사이의 관계는 다음과 같이 나타낼 수 있다.

:

\begin{matrix}a\uparrow^n b & = & a [n+2] b & = & a\to b\to n \\\mbox{(커누스)} & & \mbox{(초연산)} & & \mbox{(콘웨이)}\end{matrix}

더욱 빠르게 증가하는 함수들을 체계적으로 분류하기 위해 서수 분석의 일종인 빠르게 증가하는 계층을 사용한다. 빠르게 증가하는 계층은 어떤 기본 함수

f(x)

에 대해 연속적인 함수 반복과 대각선화 기법을 적용하여 더 빠르게 증가하는 함수들을 단계적으로 생성하는 방법이다.

표준 빠르게 증가하는 계층은 가장 기본적인 함수

f_0(x) = x+1

에서 시작한다. 이 계층에서 각 단계별 함수의 증가 속도는 다음과 같다.

$f_2(x)$ : 지수적 증가를 보인다.
$f_3(x)$ : 테트레이션과 유사한 증가 속도를 가지며, 처음 네 개의 초연산자(덧셈, 곱셈, 거듭제곱, 테트레이션)를 포함하는 함수로 그 증가율의 상한이 정해진다.
$f_\omega(x)$ : 아커만 함수와 유사한 증가 속도를 보인다. $\omega$ 는 첫 번째 초한 서수이다.
$f_{\omega + 1}(x)$ : 일반적인 화살표 표기법의 범위를 넘어서는 매우 빠른 증가 속도를 가지며, 그레이엄 수와 같은 거대한 수를 근사하는 데 사용될 수 있다.
$f_{\omega^2}(x)$ : 임의로 길게 늘어선 콘웨이 연쇄 화살표 표기법과 유사한 수준의 증가 속도를 가진다.

위에 언급된 함수들은 모두 계산 가능한 함수이다. 굿스타인 수열이나 TREE 수열과 같이 훨씬 더 빠르게 증가하는 계산 가능한 함수들도 존재하며, 이러한 함수들은 매우 큰 서수를 사용하여 분석되고 특정 조합론이나 증명 이론 분야에서 나타난다.

한편, 바쁜 비버 함수와 같이 계산 불가능할 정도로 빠르게 증가하는 함수도 존재한다. 이러한 함수의 증가 속도는 본질적으로 너무 빨라서 커누스 윗화살표 표기법이나 서수 기반의 분석 방법으로는 완전히 파악하거나 표현할 수 없다.

참조

_[1] 논문 Mathematics and Computer Science: Coping with Finiteness
_[2] 논문 Transfinite Ordinals in Recursive Number Theory 1947-12
_[3] 문서
_[4] 문서
_[5] 문서
_[6] 서적 巨大数論第2版 http://gyafun.jp/ln/ インプレス R&D
_[7] 논문 Mathematics and Computer Science: Coping with Finiteness https://www.sciencem[...] 1976-12-17
_[8] 문서
_[9] 웹사이트 大きすぎて全世界のインクを使っても書けない「巨大数」の世界 https://quizknock.co[...] QuizKnock inc. 2017-02-02
_[10] 웹사이트 ギネスブックに載った世界一大きな数がヤバすぎる！ https://enjoymath.po[...] 学生団体POMB 2021-03-28
_[11] 웹사이트 Power Tower https://mathworld.wo[...] 2021-03-28
_[12] 간행물 B. Randell and L.J. Russell, ''ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer''. Academic Press, 1964 http://www.softwarep[...]
_[13] 저널 Transfinite ordinals in recursive number theory

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com

커누스 윗화살표 표기법

1. 개요

2. 역사

2. 1. 커누스의 도입 (1976)

2. 2. 하이퍼 연산과의 관계

2. 3. 다른 표기법과의 비교

3. 정의 및 표기법

3. 1. 기본 연산

3. 2. 확장 연산

3. 3. 계산 규칙

3. 4. 대체 표기법

4. 윗화살표 표기법을 거듭제곱으로 표현

4. 1. 테트레이션을 사용한 표현

5. 예제 및 값의 표

5. 1. 2↑''m'' ''n'' 계산

5. 2. 3↑''m'' ''n'' 계산

5. 3. 4↑''m'' ''n'' 계산

5. 4. 10↑''m'' ''n'' 계산

6. 일반화 및 활용

6. 1. 하이퍼 연산

6. 2. 콘웨이 연쇄 화살표 표기법

6. 3. 그레이엄 수

6. 4. 굿스타인 수열

6. 5. 빠르게 증가하는 함수

참조

5. 1. 2↑^''m'' ''n'' 계산

5. 2. 3↑^''m'' ''n'' 계산

5. 3. 4↑^''m'' ''n'' 계산

5. 4. 10↑^''m'' ''n'' 계산