최근 수정 시각 : 2023-10-25 00:00:57

커누스 윗화살표 표기법


파일:나무위키+유도.png  
은(는) 여기로 연결됩니다.
존 호튼 콘웨이의 화살표 표기법에 대한 내용은 콘웨이 연쇄 화살표 표기법 문서
번 문단을
부분을
, 화살표(←\에 대한 내용은 화살표 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
, 에 대한 내용은 문서
번 문단을
번 문단을
부분을
부분을
참고하십시오.
연산
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차 이상의 연산들도 똑같이 정의될 수 있으며 이 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차 연산인 제곱의 꼴만으로 표기하기에는 한계가 있고 하이퍼 연산을 간단하게 표기하기 위해 이러한 하이퍼 연산 표기법이 필요함을 알 수 있는 예이다.

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

하지만 이 무시무시한 연산도 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] [math(a^{b^{c^d}} = a^{(b^{(c^d)})} \ne ((a^b)^c)^d = a^{bcd})]