커누스 윗화살표 표기법

틀:위키데이터 속성 추적 커누스 윗화살표 표기법(Knuth's up-arrow notation)은 도널드 커누스가 1976년에 개발한 아주 큰 수를 표기하는 방법이다. 이 표기법은 아커만 함수와 특히 하이퍼 연산 수열과 매우 밀접한 관련이 있으며, 곱셈은 반복되는 덧셈으로 볼 수 있고, 거듭제곱도 반복되는 곱셈으로 볼 수 있다는 사실에 기반해서 아이디어를 얻었다. 이런 방식으로 계속하면 테트레이션(반복된 거듭제곱)과 보통 커누스 윗화살표 표기법으로 표시되는 하이퍼 연산 수열의 나머지로 이어진다. 이 표기법은 명시적으로 쓸 수 있는 수보다 훨씬 더 큰 수를 간단하게 표기할 수 있다.

윗화살표 한 개는 거듭제곱(반복되는 곱셈)을 의미하고, 한 개 이상의 윗화살표는 한 개 적은 화살표를 반복하는 것을 의미한다.

예를 들어,

• 윗화살표 한 개는 곱셈의 반복(거듭제곱)이다 $2\uparrow 4=2*(2*(2*2))=2^4=16$
• 윗화살표 두 개는 거듭제곱의 반복(테트레이션)이다 $2\uparrow \uparrow 4=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^2}}=65536$
• 윗화살표 세 개는 테트레이션의 반복(펜테이션)이다 $$\begin{array}{cc}2\uparrow \uparrow \uparrow 3& =2\uparrow \uparrow (2\uparrow \uparrow 2)\\ & =2\uparrow \uparrow (2\uparrow 2)\\ & =2\uparrow \uparrow 2^2\\ & =2\uparrow \uparrow 4\\ & =2\uparrow 2\uparrow 2\uparrow 2\\ & =2^{2^{2^2}}\\ & =65536\end{array}$$

이 표기법의 일반적인 정의는 다음과 같다(정수 a와 음이 아닌 정수 b,n에 대해서):

$a{\uparrow }^{n}b=\{\begin{array}{cc}{a}^b,& \text{if }n=1;\\ 1,& \text{if }n\ge 1\text{ and }b=0;\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1)),& \text{otherwise }\end{array}$

소개

덧셈, 곱셈, 그리고 거듭제곱의 일반 산술 연산은 자연적으로 다음과 같이 하이퍼 연산의 수열로 확장된다.

자연수에 의한 곱셈은 덧셈의 반복으로 정의된다:

$\begin{array}{ccc}a\times b& =& \underbrace{a+a+\dots +a}\\ & & b\text{ copies of }a\end{array}$

예를 들면,

$\begin{array}{ccccc}3\times 4& =& \underbrace{4+4+4}& =& 12\\ & & 3\text{ copies of }4\end{array}$

자연수 지수 $b$에 의한 거듭제곱은 곱셈의 반복으로 정의되며, 커누스는 윗화살표 한 개로 표기했다:

$\begin{array}{cc}a\uparrow b=a^b=& \underbrace{a\times a\times \dots \times a}\\ & b\text{ copies of }a\end{array}$

예를 들면,

$\begin{array}{cccc}4\uparrow 3=4^3=& \underbrace{4\times 4\times 4}& =& 64\\ & 3\text{ copies of }4\end{array}$

연산의 수열을 거듭제곱을 넘어서 확장하기 위해서 커누스는 거듭제곱의 반복(테트레이션)을 의미하는 “이중 윗화살표” 연산을 정의했다:

$\begin{array}{ccccc}a\uparrow \uparrow b& ={}^{b}a=& \underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}& =& \underbrace{a\uparrow (a\uparrow (\dots \uparrow a))}\\ & & b\text{ copies of }a& & b\text{ copies of }a\end{array}$

예를 들면,

$\begin{array}{cccccccccc}4\uparrow \uparrow 3& ={}^{3}4=& \underbrace{4^{4^4}}& =& \underbrace{4\uparrow (4\uparrow 4)}& =& 4^{256}& \approx & 1.34078079\times 10^{154}& \\ & & 3\text{ copies of }4& & 3\text{ copies of }4\end{array}$

여기와 아래의 계산은 오른쪽에서 왼쪽으로 일어난다, 왜냐하면 커누스 윗화살표 연산(거듭제곱과 같은)은 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}$

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

etc.

이것만 해도 상당히 큰 수가 나오지만 커누스는 이 표기법을 확장했다. 커누스는 테트레이션의 반복(펜테이션)을 의미하는 “삼중 윗화살표” 연산을 정의했다:

$\begin{array}{cc}a\uparrow \uparrow \uparrow b=& \underbrace{a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))}\\ & b\text{ copies of }a\end{array}$

잇따라 “사중 윗화살표“ 연산은 펜테이션의 반복(헥세이션)을 의미한다:

$\begin{array}{cc}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\end{array}$

그리고 계속된다. 일반적인 규칙은 $n$중 윗화살표 연산은 right-associative ($n-1$)중 윗화살표 연산으로 확장할 수 있다는 것이다. 기호적으로는

$\begin{array}{c}a\underset{n}{\underbrace{{\uparrow }_{}\uparrow \dots \uparrow }}b=\underset{b\text{ copies of }a}{\underbrace{a\underset{n-1}{\underbrace{\uparrow \dots \uparrow }}(a\underset{n-1}{\underbrace{{\uparrow }_{}\dots \uparrow }}(\dots \underset{n-1}{\underbrace{{\uparrow }_{}\dots \uparrow }}a))}}\end{array}$

예시:

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

$\begin{array}{cc}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=& \underbrace{3_{}\uparrow 3\uparrow \dots \uparrow 3}\\ & 3\uparrow 3\uparrow 3\text{ copies of }3\end{array}\begin{array}{cc}=& \underbrace{3_{}\uparrow 3\uparrow \dots \uparrow 3}\\ & \text{7,625,597,484,987 copies of 3}\end{array}\begin{array}{cc}=& \underbrace{3^{3^{3^{3^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^3}}}}}}}}\\ & \text{7,625,597,484,987 copies of 3}\end{array}$

$a{\uparrow }^{n}b$의 표기는 일반적으로 $a\uparrow \uparrow \dots \uparrow b$에서 윗화살표가 n개인 것을 나타낸다. 사실 $a{\uparrow }^{n}b$는 하이퍼 연산으로 a [n+2] b이다. 예를 들어, $39\uparrow \uparrow 14$는 39 [4] 14 ("[4]"는 테트레이션을 의미한다)로 쓸 수 있지만 39 [2] 14 = 39 × 14 = 546인 것은 아니다. 비슷하게, $77{\uparrow }^{77}77$은 77 [79] 77이지 77 [77] 77이 아니다.

표기법

$a^b$와 같은 표현에서, 거듭제곱의 표기법은 보통 지수 $b$를 밑 $a$의 윗 첨자로 쓴다. 하지만 많은 프로그래밍 언어나 이메일같은 환경은 윗첨자 조판을 지원하지 않는다. 이런 환경에서 선형 표기법인 $a\uparrow b$를 적용했다. 윗화살표는 '다음을 지수로 올린다'는 것을 제시한다. 문자 인코딩에서는 윗화살표를 포함하지 않기 때문에 캐럿(^)을 대신해서 쓴다.

윗첨자 표기법 $a^b$는 일반화에 도움이 되지 않는다, 이것이 커누스가 인라인 표기법 $a\uparrow b$를 대신에 쓴 이유이다.

$a{\uparrow }^{n}b$는 윗화살표 n개의 더 짧은 표기법이다. 따라서 $a{\uparrow }^{4}b=a\uparrow \uparrow \uparrow \uparrow b$이다.

윗화살표 표기법을 거듭제곱으로 쓰기

$a\uparrow \uparrow b$를 익숙한 윗첨자 표기법으로 쓰려고 하면 거듭제곱의 탑을 얻게 된다.

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

b가 변수면 (또는 너무 크면), 거듭제곱의 탑은 점들과 탑의 높이를 나타내는 표시로 써야 할 수 있다.

$a\uparrow \uparrow b=\underset{b}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}$

이 표기법으로 계속하면, $a\uparrow \uparrow \uparrow b$는 각각이 위의 탑의 높이를 나타내는 거듭제곱의 탑의 스택으로 쓸 수 있다.

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

또 b가 변수거나 너무 클 경우에는 스택도 점들과 스택의 높이를 나타내는 표시로 써야 할 수 있다.

$a\uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}b$

더 나아가서, $a\uparrow \uparrow \uparrow \uparrow b$는 각각이 왼쪽의 스택의 개수를 나타내는 거듭제곱의 탑의 스택의 열로 쓸 수 있다:

$a\uparrow \uparrow \uparrow \uparrow 4=a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow a))=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}a$

또다시 일반적으로:

$a\uparrow \uparrow \uparrow \uparrow b=\underset{b}{\underbrace{\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\cdots \}a}}$

이것은 $a{\uparrow }^{n}b$을 어떤 a, n과 b에 대해서든지 (비록 이것이 분명히 더 번거롭지만) 반복되는 거듭제곱의 반복외는 거듭제곱으로 부정적으로 나타낼 수 있다는 것을 나타낸다.

테트레이션을 사용

테트레이션 표기법 $b^{}a$는 여전히 기하학적 표현 (이것을 테트레이션의 탑이라고 부른다)을 사용하지만 이 다이어그램을 약간 간단하게 만든다.

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

$a\uparrow \uparrow \uparrow b=\underset{b}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}$

$a\uparrow \uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}\}b$

결국, 한 예로 네 번째 아커만 수 $4{\uparrow }^{4}4$는 다음과 같이 나타낼 수 있다:

$\underset{\underset{\underset{4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}=\underset{\underset{{}^{{}^{{}^{4}4}4}4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}$

일반화

어떤 수는 너무 커서 커누스 윗화살표 표기법으로 쓰기에도 버거울 수 있다. 그러면 n중 화살표 연산 ${\uparrow }^n$이나 동동한 하이퍼 연산이 유용하다 (그리고 화살표의 개수가 변수일 때를 나타낼 때도 유용하다).

어떤 수는 너무 커서 이 표기법도 충분하지 않을 수 있다. 그러면 콘웨이 연쇄 화살표 표기법을 쓸 수 있다: 세 원소들의 연쇄 화살표는 다른 표기법과 동일하지만, 길이가 4 이상이면 더 강력하다.

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

보통 커누스 윗화살표는 비교적 작은 수에, 연쇄 화살표나 하이퍼 연산은 더 큰 수에 써야 한다고 주장한다.틀:누가

정의

윗화살표 표기법은 공식적으로 $b\ge 0,n\ge 0$인 모든 정수 $a,b,n$에 대해서 다음과 같이 정의된다.

$a{\uparrow }^{n}b=\{\begin{array}{cc}ab,& \text{if }n=0;\\ 1,& \text{if }n\ge 1\text{ and }b=0;\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1)),& \text{otherwise }\end{array}$

이 정의는 곱셈을 기본 연산으로 두고$(a{\uparrow }^{0}b=ab)$, 거듭제곱 $(a{\uparrow }^{1}b=a\uparrow b=a^b)$을 곱셈의 반복으로, 테트레이션 $(a{\uparrow }^{2}b=a\uparrow \uparrow b)$을 거듭제곱의 반복으로, 등등을 얻는다. (이 정의는 더 기본적인 두 함수가 없는것을 제외하고 하이퍼 연산 수열과 동등핟다. 여기서 없는 함수는 다음수와 덧셈으로, 이 함수를 포함하려면 정의를 더 복잡하게 하는 추가 시작값을 필요로 한다.)

모든 윗화살표 연산(평범한 거듭제곱 $a\uparrow b$를 포함해서)은 right associative이다. 즉, 수식의 오른쪽에서 왼쪽으로 계산한다.
$a\uparrow b\uparrow c=a\uparrow (b\uparrow c)$ —— not $(a\uparrow b)\uparrow c$.
$3\uparrow \uparrow 3=3^{3^3}$ is $3^{(3^3)}=3^{27}=7625597484987$ —— not ${\left(3^3\right)}^3=27^3=19683.$

right-associativity 때문에 $b\ge 1,n\ge 1$일 때 다음과 같다

$\begin{array}{ccc}a{\uparrow }^{n}b& =& a{\uparrow }^{n-1}a{\uparrow }^{n-1}\cdots a{\uparrow }^{n-1}a(\text{with }ba\text{'s})\\ & =& a{\uparrow }^{n-1}a{\uparrow }^{n-1}\cdots a{\uparrow }^{n-1}a{\uparrow }^{n-1}1(\text{with }ba\text{'s})\\ & =& (a{\uparrow }^{n-1}{)}^{b}1\end{array}$

각 $a$는 화살표 연산의 왼쪽 항으로 나타나고 (화살표 연산은 가환이 아니기 때문에 이 점은 중요하다), $(a{\uparrow }^m{)}^b$는 함수 $f(x)=a{\uparrow }^{m}x$를 b번 합성한 것으로 썼다. $(a{\uparrow }^m{)}^{0}n=n$이기 때문에, 원래 정의를 $b\ge 0,n\ge 0$인 모든 정수 $a,b,n$에 대해 다음과 같이 간결하게 쓸 수 있다:

$a{\uparrow }^{n}b=\{\begin{array}{cc}ab,& \text{if }n=0;\\ (a{\uparrow }^{n-1}{)}^{b}1& \text{if }n\ge 1\end{array}$

값들의 표

2↑^m n 계산

$2{\uparrow }^{m}n$을 계산하는 것은 무한한 표에서 재기술 할 수 있다. $2^n$을 가장 윗 행에 채우고, 왼쪽 열에 2로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 얻어서 이전 행의 그 값의 위치에 있는 값을 얻는다.

$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	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ copies of }2\end{array}$	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ \underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ copies of }2\end{array}$	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ \underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ \underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ copies of }2\end{array}$	$2\uparrow \uparrow \uparrow n$
4	2	4	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ copies of }2\end{array}$				$2\uparrow \uparrow \uparrow \uparrow n$

이 표는 $m$과 $n$이 약간 밀린 것과 모든 값에 3이 더해진 것을 제외하고는 아커만 함수의 표와 같다.

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}$	$3^{3^{7,625,597,484,987}}$	$3\uparrow \uparrow n$
3	3	7,625,597,484,987	$\begin{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7,625,597,484,987\text{ copies of }3\end{array}$			$3\uparrow \uparrow \uparrow n$
4	3	$\begin{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7,625,597,484,987\text{ copies of }3\end{array}$				$3\uparrow \uparrow \uparrow \uparrow n$

4↑^m n의 계산

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

$4{\uparrow }^{m}n$ = hyper(4, m + 2, n) = 4 → n → m의 값

m\n	1	2	3	4	5	공식
1	4	16	64	256	1024	$4^n$
2	4	256	$1.3407807930\times 10^{154}$	$4^{1.3407807930\times 10^{154}}$	$4^{4^{1.3407807930\times 10^{154}}}$	$4\uparrow \uparrow n$
3	4	$4^{1.3407807930\times 10^{154}}$	$\begin{array}{c}\underbrace{4_{}^{4^{{}^{.{}^{.{}^{.{}^4}}}}}}\\ 4^{1.3407807930\times 10^{154}}\text{ copies of }4\end{array}$			$4\uparrow \uparrow \uparrow n$
4	4	$\begin{array}{c}\underbrace{4_{}^{4^{{}^{.{}^{.{}^{.{}^4}}}}}}\\ \underbrace{4_{}^{4^{{}^{.{}^{.{}^{.{}^4}}}}}}\\ 4^{1.3407807930\times 10^{154}}\text{ copies of }4\end{array}$				$4\uparrow \uparrow \uparrow \uparrow n$

10↑^m n의 계산

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

$10{\uparrow }^{m}n$ = hyper(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	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\text{ copies of }10\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ \underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\text{ copies of }10\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ \underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ \underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\text{ copies of }10\end{array}$		$10\uparrow \uparrow \uparrow n$
4	10	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10\text{ copies of }10\end{array}$	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ \underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10\text{ copies of }10\end{array}$			$10\uparrow \uparrow \uparrow \uparrow n$

2 ≤ n ≤ 9일 때 $10{\uparrow }^{m}n$의 수치적인 순서는 m이 가장 우선적인 사전식 순서여서 이 8열에서 수치적인 순서는 단순히 행의 순서대로인 것을 보라. 3 ≤ n ≤ 99인 97열에도 마찬가지로 적용이 되고, m = 1에서 시작하면 3 ≤ n ≤ 9,999,999,999까지 가능하다.

하이퍼 연산 수열에 기반한 기수법

루벤 루이스 굿스타인은 커누스 화살표와 다른 표기법 시스템을 가지고 $(+,\times ,\uparrow ,\uparrow \uparrow ,\dots )$으로 표기한 하이퍼 연산 수열을 이용해서 음이 아닌 정수에 대한 기수법을 만들었다. 대괄호 ([1], [2], [3], [4], ... )를 각각의 하이퍼 연산$(+,\times ,\uparrow ,\uparrow \uparrow ,\dots )$을 나타낸다고 하면 소위 b를 밑으로 하는 정수 n의 k단계 완전 hereditary 표현은 처음 k 하이퍼 연산과 0, 1, ..., b − 1의 자릿수와 밑인 b 자신을 포함하는 숫자들만을 이용해서 다음과 같이 나타낼 수 있다:

• 0 ≤ n ≤ b-1일 때는, n은 단순히 대응하는 숫자로 표현한다.
• n > b-1일 때는, n의 표현은 재귀적으로 찾는다. 먼저 n은 다음의 형태로 나타난다:

b [k] x_k [k - 1] x_k-1 [k - 2] ... [2] x₂ [1] x₁

이 때 x_k, ..., x₁는 다음을 (차례로)만족하는 가장 큰 정수이다.

b [k] x_k ≤ n

b [k] x_k [k - 1] x_{k - 1} ≤ n

...

b [k] x_k [k - 1] x_{k - 1} [k - 2] ... [2] x₂ [1] x₁ ≤ n

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 표현의 종류에서, 밑 자신이 {0, 1, ..., b-1}의 "자릿수"처럼 표현에서 나타난다는 점을 주목하라. 이 표현은 문자가 밑을 b로 표시했을 때 일반적인 이진법과 비교된다. 예를 들어, 일반적인 이진법에서는 6 = (110)₂ = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0이고 밑이 2인 3단계 hereditary 표현은 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, [4] 1, 등등의 요소를 제거해서 간략하게 만들 수 있다. 예를 들어, 위의 밑이 2인 6의 3단계 표현은 2 [3] 2 [1] 2로 간단히 할 수 있다.

예: 266의 밑이 2인 유일한 1, 2, 3, 4, 그리고 5단계 표현은 다음과 같다:

1단계: 266 = 2 [1] 2 [1] 2 [1] ... [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

그레이엄 수 표기

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

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

같이 보기

• 원시 재귀 함수
• 하이퍼 연산
• 커틀러 묶음부호 표기법
• 테트레이션
• 펜테이션
• 콘웨이 화살표 사슬 표기법
• 아커만 함수
• 그레이엄 수
• 스테인하우스-모서 표기법

외부 링크

• 틀:매스월드
• Robert Munafo, Large Numbers