커누스 윗화살표 표기법

#!if 넘어옴1 != null
''''''{{{#!if 넘어옴2 != null
, ''''''}}}{{{#!if 넘어옴3 != null
, ''''''}}}{{{#!if 넘어옴4 != null
, ''''''}}}{{{#!if 넘어옴5 != null
, ''''''}}}{{{#!if 넘어옴6 != null
, ''''''}}}{{{#!if 넘어옴7 != null
, ''''''}}}{{{#!if 넘어옴8 != null
, ''''''}}}{{{#!if 넘어옴9 != null
, ''''''}}}{{{#!if 넘어옴10 != null
, ''''''}}}은(는) 여기로 연결됩니다.

#!if 설명 == null && 리스트 == null
{{{#!if 설명1 == null
다른 뜻에 대한 내용은 아래 문서를}}}{{{#!if 설명1 != null
{{{#!html 존 호튼 콘웨이의 화살표 표기법}}}에 대한 내용은 [[콘웨이 연쇄 화살표 표기법]] 문서{{{#!if (문단1 == null) == (앵커1 == null)
를}}}{{{#!if 문단1 != null & 앵커1 == null
의 [[콘웨이 연쇄 화살표 표기법#s-|]]번 문단을}}}{{{#!if 문단1 == null & 앵커1 != null
의 [[콘웨이 연쇄 화살표 표기법#|]] 부분을}}}}}}{{{#!if 설명2 != null
, {{{#!html 화살표(←\}}}에 대한 내용은 [[화살표]] 문서{{{#!if (문단2 == null) == (앵커2 == null)
를}}}{{{#!if 문단2 != null & 앵커2 == null
의 [[화살표#s-|]]번 문단을}}}{{{#!if 문단2 == null & 앵커2 != null
의 [[화살표#|]] 부분을}}}}}}{{{#!if 설명3 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단3 == null) == (앵커3 == null)
를}}}{{{#!if 문단3 != null & 앵커3 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단3 == null & 앵커3 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명4 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단4 == null) == (앵커4 == null)
를}}}{{{#!if 문단4 != null & 앵커4 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단4 == null & 앵커4 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명5 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단5 == null) == (앵커5 == null)
를}}}{{{#!if 문단5 != null & 앵커5 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단5 == null & 앵커5 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명6 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단6 == null) == (앵커6 == null)
를}}}{{{#!if 문단6 != null & 앵커6 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단6 == null & 앵커6 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명7 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단7 == null) == (앵커7 == null)
를}}}{{{#!if 문단7 != null & 앵커7 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단7 == null & 앵커7 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명8 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단8 == null) == (앵커8 == null)
를}}}{{{#!if 문단8 != null & 앵커8 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단8 == null & 앵커8 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명9 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단9 == null) == (앵커9 == null)
를}}}{{{#!if 문단9 != null & 앵커9 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단9 == null & 앵커9 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명10 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단10 == null) == (앵커10 == null)
를}}}{{{#!if 문단10 != null & 앵커10 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단10 == null & 앵커10 != null
의 [[#|]] 부분을}}}}}}

#!if 설명 == null
{{{#!if 리스트 != null
다른 뜻에 대한 내용은 아래 문서를}}} 참고하십시오.

#!if 리스트 != null
{{{#!if 문서명1 != null
 * {{{#!if 설명1 != null
존 호튼 콘웨이의 화살표 표기법: }}}[[콘웨이 연쇄 화살표 표기법]] {{{#!if 문단1 != null & 앵커1 == null
문서의 [[콘웨이 연쇄 화살표 표기법#s-|]]번 문단}}}{{{#!if 문단1 == null & 앵커1 != null
문서의 [[콘웨이 연쇄 화살표 표기법#|]] 부분}}}}}}{{{#!if 문서명2 != null
 * {{{#!if 설명2 != null
화살표(←\: }}}[[화살표]] {{{#!if 문단2 != null & 앵커2 == null
문서의 [[화살표#s-|]]번 문단}}}{{{#!if 문단2 == null & 앵커2 != null
문서의 [[화살표#|]] 부분}}}}}}{{{#!if 문서명3 != null
 * {{{#!if 설명3 != null
: }}}[[]] {{{#!if 문단3 != null & 앵커3 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단3 == null & 앵커3 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명4 != null
 * {{{#!if 설명4 != null
: }}}[[]] {{{#!if 문단4 != null & 앵커4 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단4 == null & 앵커4 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명5 != null
 * {{{#!if 설명5 != null
: }}}[[]] {{{#!if 문단5 != null & 앵커5 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단5 == null & 앵커5 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명6 != null
 * {{{#!if 설명6 != null
: }}}[[]] {{{#!if 문단6 != null & 앵커6 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단6 == null & 앵커6 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명7 != null
 * {{{#!if 설명7 != null
: }}}[[]] {{{#!if 문단7 != null & 앵커7 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단7 == null & 앵커7 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명8 != null
 * {{{#!if 설명8 != null
: }}}[[]] {{{#!if 문단8 != null & 앵커8 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단8 == null & 앵커8 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명9 != null
 * {{{#!if 설명9 != null
: }}}[[]] {{{#!if 문단9 != null & 앵커9 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단9 == null & 앵커9 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명10 != null
 * {{{#!if 설명10 != null
: }}}[[]] {{{#!if 문단10 != null & 앵커10 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단10 == null & 앵커10 != null
문서의 [[#|]] 부분}}}}}}

수와 연산 Numbers and Operations
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	<colbgcolor=#765432> 수 체계	자연수(수학적 귀납법 · 홀수 · 짝수 · 소수 · 합성수) · 정수 · 유리수(정수가 아닌 유리수) · 실수(무리수 · 초월수) · 복소수(허수) · 사원수 · 팔원수
표현	숫자(아라비아 숫자 · 로마 숫자 · 그리스 숫자) · 기수법(자연어 수 표기법 · 과학적 표기법 · E 표기법 · 커누스 윗화살표 표기법 · 콘웨이 연쇄 화살표 표기법 · BEAF · 버드 표기법) · 진법(십진법 · 이진법 · 8진법 · 12진법 · 16진법 · 60진법) · 분수(분모 · 분자 · 기약분수 · 번분수 · 연분수 · 통분 · 약분) · 소수{유한소수 · 무한소수(순환소수 · 비순환소수)} · 환원 불능 · 미지수 · 변수 · 상수
연산	사칙연산(덧셈 · 뺄셈 · 곱셈_(구구단) · 나눗셈) · 역수 · 절댓값 · 제곱근(이중근호) · 거듭제곱 · 로그(상용로그 · 자연로그 · 이진로그) · 역산 · 검산 · 연산자 · 교환자
	방식	암산 · 세로셈법 · 주판 · 산가지 · 네이피어 계산봉 · 계산기 · 계산자
용어	이항연산(표기법) · 항등원과 역원 · 교환법칙 · 결합법칙 · 분배법칙
기타	수에 관련된 사항(0과 1 사이의 수 · 음수 · 작은 수 · 큰 수) · 혼합 계산(48÷2(9+3) · 111+1×2=224 · 2+2×2) · 0으로 나누기(바퀴 이론) · 0의 0제곱		}}}}}}}}}

1. 개요2. 하이퍼 연산3. 상세4. 화살표 표기를 거듭제곱의 꼴로 쓰기5. 같이 보기

1. 개요

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

2. 하이퍼 연산

덧셈을 반복하면 곱셈, 곱셈을 반복하면 거듭제곱(지수셈)이다. 이에 거듭제곱을 반복한 연산도 있을 수 있음을 생각해볼 수 있다.

덧셈을 1차 연산, 곱셈을 2차 연산, 거듭제곱을 3차 연산이라고 할 때, 이렇게 개념을 확장하여 4차 이상의 연산들도 똑같이 정의할 수 있으며 이 [math(n)]차 연산을 하이퍼 연산(hyperoperation)이라고 부른다. 하이퍼 연산의 일반적인 명칭은 4차 연산의 경우 테트레이션(tetration), 5차 연산의 경우 펜테이션(pentation), 6차 연산의 경우 헥세이션(hexation) 등 각 연산 차수를 뜻하는 접두사를 가져와 '-ation'을 붙여서 부른다.

3. 상세

커누스 윗화살표 표기법은 다음과 같이 정의된다.

실수 [math(a)], 자연수 [math(b)], 자연수 [math(n)]에 대해

a \uparrow b &= a^b \\
a \;\underbrace{\uparrow\uparrow\cdots\uparrow\uparrow}_{n개} \;b &= a \uparrow^n b \\
a \uparrow^{n+1} b &= \underbrace{a \uparrow^n a \uparrow^n \cdots \uparrow^n a \uparrow^n a}_{a가\;b개}
\end{aligned} )]||

[math(0)]이 아닌 실수 [math(a)], 자연수 [math(n)]에 대해

a \uparrow^n 0 = 1
\end{aligned} )]||
윗화살표 표기법은 2개의 수 사이에 윗화살표를 넣는 연산 표기법이다. 화살표 1개짜리 연산은 거듭제곱과 같고, 화살표 [math(n)]개짜리 연산은 화살표 [math((n-1))]개짜리 연산을 1번째 수로 2번째 수만큼 반복한다는 의미이다. [math(n)]차 연산이 [math((n-1))]차 연산의 반복이라는 것과 일맥상통한다. 여기서 화살표 1개짜리 연산인 거듭제곱은 3차 연산이므로 [math(\uparrow^n)]는 정확하게 [math((n+2))]차 연산과 같음을 알 수 있다. 이 표기법을 처음 접하는 경우엔 이해가 잘 안 될 수도 있으므로, 아래의 예시 문단을 참고하면 좋다.

거듭제곱의 반복의 계산을 [math(a^{b^{c^d}} = a^{(b^{(c^d)})} \ne ((a^b)^c)^d = a^{bcd})]처럼 맨 위의 지수부터 아래로 하는 것과 동일하게, 여러 개의 화살표 연산이 있을 때는 다음과 같이 괄호가 따로 없으면 맨 오른쪽의 화살표부터 왼쪽으로 계산한다.

[math(\displaystyle \begin{aligned}
a \uparrow^l b \uparrow^m c \uparrow^n d = a \uparrow^l (b \uparrow^m (c \uparrow^n d))
\end{aligned} )]

[math(a)], [math(b)]가 모두 [math(2)]일 경우, 화살표 연산의 특징에 따라 화살표의 개수에 상관없이 값이 항상 [math(4)]가 된다. 즉, [math(2 \uparrow^n 2 = 4)]이다.

==# 예시 #==

화살표가 한 개인 경우

3 \uparrow 0 &= 3^0 = 1 \\
3 \uparrow 1 &= 3^1 = 3 \\
3 \uparrow 2 &= 3^2 = 9 \\
3 \uparrow 3 &= 3^3 = 27 \\
3 \uparrow 4 &= 3^4 = 81
\end{aligned} )]||

화살표가 두 개인 경우

3 \uparrow\uparrow 0 &= 1 \\
3 \uparrow\uparrow 1 &= 3 \\
3 \uparrow\uparrow 2 &= 3 \uparrow 3 = 3^3 = 27 \\
3 \uparrow\uparrow 3 &= 3 \uparrow 3 \uparrow 3 = 3^{3^3} = 3^{27} = 7,\!625,\!597,\!484,\!987 \\
3 \uparrow\uparrow 4 &= 3 \uparrow 3 \uparrow 3 \uparrow 3 = 3^{3^{3^3}} = 3^{7,625,597,484,987}
\end{aligned} )]||

화살표가 세 개인 경우

3 \uparrow\uparrow\uparrow 0 &= 1 \\
3 \uparrow\uparrow\uparrow 1 &= 3 \\
3 \uparrow\uparrow\uparrow 2 &= 3 \uparrow\uparrow 3 = 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 \uparrow 3 \uparrow \cdots \uparrow 3 \uparrow 3}_{3이\;7,625,597,484,987개} = \underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{3이\;7,625,597,484,987개} \\
3 \uparrow\uparrow\uparrow 4 &= 3 \uparrow\uparrow 3 \uparrow\uparrow 3 \uparrow\uparrow 3
\end{aligned} )]||

화살표가 네 개인 경우

3 \uparrow\uparrow\uparrow\uparrow 0 &= 1 \\
3 \uparrow\uparrow\uparrow\uparrow 1 &= 3 \\
3 \uparrow\uparrow\uparrow\uparrow 2 &= 3 \uparrow\uparrow\uparrow 3 \\
3 \uparrow\uparrow\uparrow\uparrow 3 &= 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \\
3 \uparrow\uparrow\uparrow\uparrow 4 &= 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3
\end{aligned} )]||

화살표의 개수의 변화에 따른 결과

3 \uparrow 5 &= 3^5 \\
3 \uparrow\uparrow 5 &= 3 \uparrow 3 \uparrow 3 \uparrow 3 \uparrow 3 = 3^{3^{3^{3^3}}} \\
3 \uparrow\uparrow\uparrow 5 &= 3 \uparrow\uparrow 3 \uparrow\uparrow 3 \uparrow\uparrow 3 \uparrow\uparrow 3 \\
3 \uparrow^4 5 &= 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 \\
3 \uparrow^5 5 &= 3 \uparrow^4 3 \uparrow^4 3 \uparrow^4 3 \uparrow^4 3
\end{aligned} )]||

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차 연산인 제곱의 꼴만으로 표기하기에는 한계가 있고 하이퍼 연산을 간단하게 표기하기 위해 이러한 하이퍼 연산 표기법이 필요함을 알 수 있는 예이다.

[math(^nn)] 꼴의 지수 탑을 쌓는 것보다도 화살표의 개수를 늘리는 게 훨씬 더 빠르다.[3] 이곳 참고.

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

5. 같이 보기

[1] Knuth, Donald E. (1976) "Mathematics and Computer Science: Coping with Finiteness", Science, 194(4271), 1235–1242, Bibcode: 1976Sci...194.1235K, DOI: 10.1126/science.194.4271.1235, PMID 17797067[2] 도널드 커누스는 TeX을 만들어낸 사람이기도 하다.[3] 그나마 비슷하게 비교하자면

식으로 하면 된다.