커누스 윗화살표 표기법

존 호튼 콘웨이의 화살표 표기법에 대한 내용은 콘웨이 연쇄 화살표 표기법 문서 참고하십시오.

1. 개요[편집]

---

Knuth's up-arrow notation
수학자 겸 프로그래머인 도널드 커누스가 고안한 큰 수의 표기법.[1][2] 간단하게 화살표 표기법(arrow notation)이라고도 불린다. 하이퍼 연산을 표기하는 데 쓰이는 여러 표기법들 중 하나이다.

2. 하이퍼 연산[편집]

---

덧셈을 반복하면 곱셈, 곱셈을 반복하면 제곱이다. 이에 제곱의 반복인 연산도 있을 수 있음을 생각해볼 수 있다.
이렇게 개념을 확장하여 덧셈이 1차 연산, 곱셈이 2차 연산, 제곱이 3차 연산일 때 그 다음의 4차 이상의 연산들도 똑같이 정의될 수 있으며 이 n차 연산을 하이퍼 연산(hyperoperation)이라고 부른다. 4차 이상의 하이퍼 연산의 일반적인 명칭은 테트레이션(tetration), 펜테이션(pentation), 헥세이션(hexation) 등 각 숫자를 뜻하는 접두사를 가져와 -ation으로 불린다.

3. 상세[편집]

---

실수 [math(a)]와 음이 아닌 정수 [math(b)], 2 이상의 정수 [math(n)]에 대하여

[math(a \uparrow b = a^b)]
[math(a \mathrel {\underbrace {\uparrow\uparrow\cdots\uparrow\uparrow}_{n}} b = a \uparrow^n b)]
[math(a \uparrow^n b = \underbrace {a \uparrow^{n-1} a \uparrow^{n-1} \cdots \uparrow^{n-1} a \uparrow^{n-1} a}_{a가\;b개})]

윗화살표 표기법은 2개의 수 사이에 윗화살표를 넣는 연산 표기법인데, 화살표 1개짜리 연산은 거듭제곱과 같고 2개 이상의 화살표는 그보다 1개 적은 화살표 연산을 1번째 수로 2번째 수만큼 반복한다는 의미이다. n차 연산이 (n-1)차 연산의 반복이라는 것과 일맥상통한다.
여기서 화살표 1개 연산인 거듭제곱은 3차 연산이므로 [math(\uparrow^n)]는 정확하게 (n+2)차 연산과 같음을 알 수 있다.

[math(a \uparrow^{x} b \uparrow^{y} c \uparrow^{z} d = a \uparrow^{x} (b \uparrow^{y} (c \uparrow^{z} d)))]
거듭제곱의 반복의 계산을 맨 위의 지수부터 아래로 하는 것[3]과 동일하게 여러개의 화살표 연산이 있을 때 괄호가 따로 없으면 맨 오른쪽의 화살표부터 왼쪽으로 계산함을 헷갈리지 말자.

단, a, b가 모두 2일 경우 화살표 연산의 특징에 따라 화살표 개수에 상관없이 항상 4로 고정된다.

4. 화살표 표기를 거듭제곱의 꼴로 쓰기[편집]

---

꽤나 번거롭지만 화살표 표기를 거듭제곱의 꼴로 나타낼 수 있다.
[math(
\def\degii{\underbrace{a^{a^{\cdot^{\cdot^{\cdot^a}}}}}}
\def\degiii{\left. \begin{matrix} \degii \\ \degii \\ \underbrace{\;\;~ \vdots \;\;~} \\ \degii \\ a \end{matrix} \right\}}
\def\degix{\underbrace{\left. \degiii \degiii \cdots \right\} \degiii a}}

a \uparrow b = a^b \\ ~ \\
a \uparrow\uparrow b = \degii_{\displaystyle b} \\ ~ \\
\rule{0pt}{39pt}^{\displaystyle a \uparrow\uparrow\uparrow b =} \degiii b \\ ~ \\
\rule{0pt}{39pt}^{\displaystyle a \uparrow\uparrow\uparrow\uparrow b =} \degix_{\displaystyle b}
)]

화살표 하나가 늘수록 수식이 굉장히 복잡해진다. 이렇게 윗화살표 표기법은 4차 이상의 하이퍼 연산을 3차 연산인 제곱의 꼴만으로 표기하기에는 한계가 있고 하이퍼 연산을 간단하게 표기하기 위해 이러한 하이퍼 연산 표기법이 필요함을 알 수 있는 예이다.

ⁿn 꼴의 지수 탑을 쌓는 것보다도 화살표의 개수를 늘리는 게 훨씬 더 빠르다. 참고.

하지만 이 무시무시한 연산도 fgh 에서는 오메가 단계가 한계다. 그레이엄 수 같이 화살표 탑을 쌓더라도, [math(f_{ω+1}(n))] 단계가 한계다. 콘웨이 연쇄 화살표 표기법에서는 길이가 3인 연쇄 화살표로 축약된다.

5. 같이 보기[편집]

---

• 큰 수
• 테트레이션
• 그레이엄 수
• 콘웨이 연쇄 화살표 표기법