크누스의 위쪽 화살표 표기법

수학에서 크누스의 위 화살표 표기법은 1976년 도널드 크누스가 도입한 매우 큰 정수에 대한 표기법입니다.^[1]

1947년 그의 논문에서,^[2] R. L. 굿스타인은 현재 하이퍼 오퍼레이션이라고 불리는 특정한 오퍼레이션 시퀀스를 소개했습니다. Goodstein은 또한 지수화를 넘어서는 확장 연산을 위해 그리스어 이름인 tetration, pentation 등을 제안했습니다. 수열은 단항 연산(n = 0인 계승 함수)으로 시작하여 덧셈(n = 1), 곱셈(n = 2), 지수화(n = 3), 테테이션(n = 4), 펜테이션(n = 5) 등의 이진 연산으로 계속됩니다. 하이퍼 오퍼레이션을 나타내기 위해 다양한 표기법이 사용되었습니다. 그러한 표기법 중 하나는 ${\displaystyle {Hn}_{}a,}$ b${\displaystyle )}$ ${\displaystyle H_{n}(a,$ b$)}$입니다$.$ 크누스의 업 arrow 표기법 ↑ {\$displaystyle \uparrow}$는 또 다른 표기법입니다. 예:

• 단일 화살표 ↑ {\$displaystyle \uparrow }$은 지수화(반복 곱셈)를 나타냅니다.
  $${\displaystyle 2\uparrow 4=H_{3}(2,4)=2\times(2\times 2)=2^{4}=16}$$

  
• 이중 화살표 ↑↑ {\$displaystyle \uparrow \uparrow }$은 테트레이션(반복 지수화)을 나타냅니다.
  $${\displaystyle 2\uparrow \uparrow 4=H_{4}(2,4)=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=2^{16}=65,536}$$

  
• 3중 화살표 ↑↑↑ {\$displaystyle$ \$uparrow \uparrow }$는 pentation(반복 사선화)을 나타냅니다.
  $${\displaystyle {\begin{aligned}2\uparrow \uparrow 4=H_{5}(2,4)=2\uparrow \uparrow (2\uparrow \uparrow \uparrow 2)\\&=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow 2))\\&=2\uparrow \uparrow (2\uparrow \uparrow 4)\\&=\underbrace {2\uparrow (2\uparrow (2\uparrow \dots ))} \;=\;\underbrace {\;2^{2^{\cdots ^{2}}}} \\&\;\;\;\;\;2\uparrow \uparrow 4{\mbox{ copies of }}2\;\;\;\;\;{\mbox{65,536 2s}}\\\end{aligned}}}$$

  

${\displaystyle \mathrm{위쪽}}$ 화살표 표기법의 일반적인 정의는 다음과 같습니다$($≥ $0$, ${\displaystyle \mathrm{n}}$ ≥$$1, b ≥$0 {\displaystyle$a\geq 0, n\geq 1, b\geq 0}).

${\displaystyle {}^{}}$서 ↑ n {\$displaystyle \uparrow ^{n}}$는 n개의 화살표를 나타내므로 예를 들어 대괄호는 하이퍼 연산의 또 다른 표기법입니다.

서론

초연산은 자연스럽게 덧셈과 곱셈의 산술 연산을 다음과 같이 확장합니다. 자연수에 의한 덧셈은 반복적인 증가로 정의됩니다.

${\displaystyle {\begin {matrix}H_{1}(a,b)=a+b=&a+\underbrace {1+1+\dots +1} \\&b{\mbox{ copies of }}1\end{matrix}}}$

자연수에 의한 곱셈은 반복 덧셈으로 정의됩니다.

${\displaystyle {\begin {matrix}H_{2}(a,b)=a\times b=&\underbrace {a+a+\dots+a} \\&b{\mbox{copy of }a\end{matrix}}$

예를들면,

${\displaystyle {\begin{matrix}4\times 3&=&\underbrace {4+4} &=&12\&3{\mbox{copy of }4\end{matrix}}}$

자연 거듭제곱 $b{\displaystyle }$ ${\displaystyle b}$에 대한 지수화는 반복 곱셈으로 정의되며$$, Knuth는 위 화살표 하나로 다음과 같이 표시합니다.

${\displaystyle {\begin{matrix}a\uparrow b=H_{3}(a,b)=a^{b}=&\underbrace {a\times a\times a} \\&b{\mbox{copy of }a\end{matrix}}}$

예를들면,

${\displaystyle {\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4} &=&64\&3{\mbox{copy of }4\end{matrix}}}$

테트레이션은 반복 지수화로 정의되며, 크누스는 이를 "이중 화살표"로 표시합니다.

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=&\underbrace {a^{.\,^{.\,^{.\,^{.\,^{a}}}} &=\&\underbrace {a\uparrow(\uparrow(\uparrow a))}\\&b{\mbox{copy of }a&b{\mbox{copy of }a\end{matrix}}}$

예를들면,

${\displaystyle {\begin{matrix}4\uparrow\underbrace {4^{4}} &=&\underbrace {4\uparrow(4)} &=&\underbrace {4\uparrow(4)} &=&4^{256}&\approx &1.34078079\times 10^{154}&\&3{\mbox{copy of }4\end{matrix}}}$

연산자가 오른쪽 연관 관계로 정의되기 때문에 식이 오른쪽에서 왼쪽으로 평가됩니다.

이 정의에 따르면,

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

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

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}}}$

기타.

이것은 이미 상당히 많은 수를 초래하지만, 하이퍼 연산자 시퀀스는 여기서 멈추지 않습니다.

반복된 사구체화로 정의되는 사구체화는 "3중 화살표"로 표시됩니다.

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{5}(a,b)=&\underbrace {a_{}\uparrow(\uparrow \uparrow \uparrow a)}\\&b{\mbox{copy of }a\end{matrix}}$

반복된 펜테이션으로 정의되는 헥세이션은 "4중 화살표"로 표시됩니다.

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=H_{6}(a,b)=&\underbrace {a_{}\uparrow \uparrow(\uparrow \uparrow \uparrow a)}\&b{\mbox{copy of matrix}a\end{dots}}$

등등. $일반적$인 규칙은 ${\displaystyle n}$ - 화살표$$ 연산자가 (${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle n-1})$ $$- 화살표 연산자의 오른쪽 연관 시리즈로 확장된다는 것입니다. 상징적으로.

${\displaystyle {\begin{matrix}a\밑줄 {\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{copy of }}\end{matrix}}}$

예:

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

${\displaystyle {\begin{matrix}3\uparrow \uparrow \3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow 3)=&\\언더레이스 {3_{}\uparrow \dots \uparrow 3}\&3\uparrow 3\uparrow 3}\end{matrix}}{\begin{matrix}=&\언더레이스 {3_{}\uparrow 3\uparrow \dots \uparrow 3}\&{mbox{copies}\&\언더레이스 \uparrow \uparrow 3}\&{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}{\begin{matrix}=&\underbrace {3^{3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}}}} \\&{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}}$

표기법

${\displaystyle b^{}}$ ${\$와 같은 표현에서$$지수화에 대한 표기법은 일반적으로 $지수{\displaystyle }$ b ${\displaystyle$ b$}$를 기본 $번호{\displaystyle }$ a ${\displaystyle a}$의 위첨자로 쓰는 것입니다$.$ 그러나 프로그래밍 언어 및 일반 텍스트 전자 메일과 같은 많은 환경에서는 위첨자 유형 설정을 지원하지 않습니다. 사람들은 그러한 환경에 대해 선형 표기법 $a$ ↑ ${\displaystyle b}$ {\$display$ $a\uparrow$ b$}$를 채택했습니다. 위 arrow는 '의 거듭제곱으로 올리기'를 제안합니다. 문자 집합에 위쪽 화살표가 없으면 대신 캐럿(^)이 사용됩니다.

위첨자 표기 ${\displaystyle a^{}}$ b ${\displaystyle a^{b}}$는 일반화에 잘 적용되지 않으므로 크누스가 대신 인라인 표기 $a$ ↑ ${\displaystyle b}$ {\$displaystyle$ a$\uparrow$ b$}$에서 $작업하기$로 선택한 이유입니다.

${\displaystyle a}$ ↑ ${\displaystyle n^{}}$ b $displaystyle$ a$\uparrow ^{n}b}$는 n개의 상행선에 대한 더 짧은 대체 표기법입니다. 따라서 $a$ ↑ 4 ${\displaystyle {}^{}}$ = a ↑↑↑↑ ${\displaystyle b}$ {\displaystyle a\uparrow ^{4} b = a\uparrow \uparrow \uparrow b}.

멱함수의 관점에서 위쪽 화살표 표기법 작성

익숙한 위첨자 표기법을 사용하여 ↑↑ ${\displaystyle b}$ {\$displaystyle$ $a\uparrow \uparrow$ b$}$를 작성하려고 하면 전력탑이 나타납니다.

예를 들어 $a$ ↑↑ ${\displaystyle 4}$ = a$$↑ ($a$ ↑ a ) = a {\displaystyle a\uparrow \uparrow 4 = a\uparrow (a\uparrow a)) = a^{a^{a^{$a}}}$

b가 변수인 경우(또는 너무 큰 경우) 전력탑은 점과 탑의 높이를 나타내는 노트를 사용하여 기록될 수 있습니다.

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

이 표기법을 계속 사용하여 ↑↑↑ ${\displaystyle b}$ {\$displaystyle$ a$\uparrow \uparrow b}$를 그러한 전력 타워의 스택과 함께 작성할 수 있으며, 각 타워는 그 위에 있는 타워의 크기를 설명합니다.

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

다시 말하지만, b가 변수이거나 너무 크면 점과 높이를 나타내는 노트를 사용하여 스택을 작성할 수 있습니다.

${\displaystyle a\uparrow \uparrow \uparrow b=\left.\언더브레이스 {a^{a^{.^{.^{.{a}}}}_{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}b}$

$또한$ ↑↑↑↑ ${\displaystyle b}$ {\$display$ $a\uparrow \uparrow \uparrow$ b$}$는 $이러한$ 전력 타워 스택의 여러 열을 사용하여 작성할 수 있으며 각 열은 스택의 전력 타워 수를 왼쪽에 설명합니다.

${\displaystyle a\uparrow \uparrow \uparrow \uparrow 4= a\uparrow \uparrow (a\uparrow \uparrow \uparrow (a\uparrow \uparrow a)=\left.\left.\left.\언더브레이스 {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}$

그리고 더 일반적으로 다음과 같습니다.

${\displaystyle a\uparrow \uparrow \uparrow b=\underbrace {\left.\left.\left.\언더브레이스 {a^{a^{.^{.^{.{a}}}}_{\underbrace {a^{a^{.^{.^{.{a}}}}_{\underbrace {\vdots}_{a}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}_{\underbrace {a^{a^{.^{.^{.{a}}}}_{\언더브레이스 {\vdots}_{a}}\right\}\cdots \right\}a}_{b}$

이것은 어떤 a, n 및 b에 대해 반복되는 지수의 지수화를 반복함에 따라 ↑ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ {\$displaystyle$ $a\uparrow ^{n}b}$를 나타내기 위해 무한히 수행될 수 있습니다(비록 다소 번거로워지기는 하지만).

테트라테이션 사용

테테이션을 위한$$ 루디 루커 표기법 ${\displaystyle {}^{}}$ ${\displaystyle ^{b}a}$를 사용하면 기하학적 표현을 사용하면서 이러한 다이어그램을 약간 더 단순화할 수 있습니다(우리는 이러한 테테이션 타워라고 부를 수 있습니다).

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

${\displaystyle a\uparrow \uparrow b=\underbrace {^{^{^{a}}}:{b}}$

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

마지막으로, 예를 들어 네 번째 Ackerman $number$ 4 ↑ ${\displaystyle {}^{}}$ {\$displaystyle$ $4\uparrow ^{4}}$는 다음과 같이 나타낼 수 있습니다.

${\displaystyle \underbrace {^{^{^{4}}}_{\underbrace {^{^{4}}}_{\underbrace {^{^{^{4}}}_{\underbrace {^{^{4}}}_{4}}=\underbrace {^{^{^{4}}}}_{\underbrace {^{^{4}}}_{\underbrace {^{^{4}}_{^{^{4}}}_{{^{4}}}_{^{^{4}4}}}$

일반화

일부 숫자는 너무 커서 크누스의 상위 arrow 표기법의 여러 화살표가 너무 번거로워집니다. 그런 다음 n-arrow ${\displaystyle {}^{}}$ ↑ n {\$displaystyle \uparrow$^{n}}는 유용합니다(가변한 수의 화살표가 있는 설명에도 유용합니다.) 또는 이와 동등하게 하이퍼 연산자도 유용합니다.

어떤 숫자들은 너무 커서 그 표기조차 충분하지 않습니다. 그러면 콘웨이 연결 화살표 표기법을 사용할 수 있습니다: 세 개의 원소로 이루어진 사슬은 다른 표기법과 동일하지만, 네 개 이상의 사슬은 훨씬 더 강력합니다.

${\displaystyle {\begin{matrix}a\uparrow ^{n}b&=&a[n+2]b&=&a\to b\to n\{\mbox{(Knuth)}}&{\mbox{(과다동작)}}}}&&{\mbox{(Conway)}}\end{matrix}}}$

${\displaystyle 6}$ ↑↑ ${\displaystyle 4}$ {\$displaystyle$ $6\uparrow \uparrow$ =${\displaystyle \mathrm{}}$$66$ 4 ${\displaystyle$ \$underbrace {6^{$$^{.^{.$$^{6}}}}}} _{4}}$, Since ${\displaystyle 6\uparrow \uparrow 4}$ = ${\displaystyle 6^{6^{6^{6}}}}$ = ${\displaystyle 6^{6^{46,656}}}$, Thus the result comes out with ${\displaystyle \underbrace {6^{6^{.$$^{.^{.$$^{6}}}}}} _{4}}$

${\displaystyle 10}$ ↑ ${\displaystyle (}$3${\displaystyle \times \mathrm{}10}$ ↑ (3 ×$10$ ↑ $15$ ) + 3 ) {\displaystyle ${\displaystyle \underset{}{\underset{}{10}}}$\uparrow(3\times 10\uparrow(3\times 10\uparrow 15)+${\displaystyle 3}$)} = 100,000${\displaystyle \underset{}{\underset{}{\mathrm{...}}}}$${\displaystyle \underset{\underset{}{\underset{}{\mathrm{300000...}}}}{\underbrace{000}}}$${\displaystyle \underset{}{\underset{\underset{}{\underset{}{\mathrm{300000...}}}}{\underbrace{003}}}}$$000$$000} _{\언더그라운드 {300000...$$003} _{\언더브레이스 {300000...$$000} _{15}}}$ 또는$$ ${\displaystyle {103\mathrm{}}^{}}$× ${\displaystyle {{103\mathrm{}}^{}}^{}}$× ${\displaystyle {{{10}^{}}^{}}^{}}$ ${\displaystyle {{{15}^{}}^{}}^{}}$+ ${\displaystyle 3^{}}$ ${\$ (페틸리온)

더 빠르게 증가하는 함수는 빠르게 증가하는 계층 구조라고 불리는 순서형 분석을 사용하여 분류할 수 있습니다. 빠르게 성장하는 계층은 연속적인 함수 반복과 대각화를 사용하여 일부 기본 $함수$ f${\displaystyle (x)}$ ${\displaystyle f(x)}$에서 빠르게 성장하는 함수를 체계적으로 만듭니다$.$ $f$ ${\displaystyle 0_{}x)}$ = ${\displaystyle \mathrm{x}}$+ 1$${\displaystyle f_{0}(x) = x + 1}을 사용하여 빠르게 성장하는 표준 계층의 경우, ${\displaystyle f_{}}$ ${\displaystyle 2_{}}$( ${\displaystyle x}$) ${\displaystyle f_{2}(x)}$는 이미 지수 성장을 나타내고, $f$ ${\displaystyle 3_{}}$( ${\displaystyle x}$) ${\displaystyle f_{3}(x)}$는 정방 성장과 유사하며 처음 4개의 하이퍼 연산자를 포함하는 함수에 의${\displaystyle {\mathrm{해\; 상위\; bo}}_{}}$unded입니다. $그렇다면$ f$$ω (x) {\$displaystyle f_{\omega$}(x)}는 아커만${\displaystyle {}_{}}$함수와 ${\displaystyle {비슷하고}_{}}$,${\displaystyle {}_{}}$f$$ω + 1 (x) ${\displaystyle$f_{\omega + 1}(x)}는 색인화된 화살표의 범위를 이미 벗어났지만 Graham의 수를 근사하는 데 사용할 수 있습니다. $그리고$ f${\displaystyle }$ω$$2(x) {\$displaystyle f_{\omega$^{2}}(x)}는 임의로 긴 콘웨이 연결 화살표 표기법과 유사합니다.

이 기능들은 모두 계산이 가능합니다. Goodstein 시퀀스 및 TREE 시퀀스와 같이 더 빠른 계산 기능은 큰 서수를 사용해야 하는 특정 조합론적 및 증명 이론적 맥락에서 발생할 수 있습니다. Busy Beaver와 같이 계산할 수 없을 정도로 빠르게 성장하는 기능이 있습니다. 그 자체의 성질은 어떤 위쪽 화살표나 심지어 어떤 순서에 기반한 분석에서도 완전히 손이 닿지 않을 것입니다.

정의.

하이퍼 오퍼레이션에 대한 언급 없이, 위 화살표 연산자는 다음에 의해 공식적으로 정의될 수 있습니다.

${\displaystyle 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}}}$

${\displaystyle \mathrm{모든}}$ 정수 $a$${\displaystyle ,}$ b${\displaystyle ,}$ ${\displaystyle n}$ ${\displaystyle$ a$,$$b$$,n$${\displaystyle \}}$에 대해 ≥ 0, n ≥ 1, b ≥ 0 {\displaystyle a\geq 0,n\geq 1,b\geq 0}.

이 정의는 지수화$({\displaystyle a}$ ↑ ${\displaystyle 1}$ b${\displaystyle }$= a ↑ ${\displaystyle b}$= ${\displaystyle b}$ ) {\displaystyle($a$\uparrow ^{1}b = a\uparrow b = a^{b})}를 기본 케이스로 사용하고 테테이션(a ↑ 2 b = a ↑↑ b) {\displaystyle(a\uparrow ^{2}b = a\uparrow \uparrow b)}을 반복 지수화로 사용합니다. 이것은 계승, 덧셈, 곱셈의 세 가지 기본 연산을 생략한 것을 제외하고는 하이퍼 오퍼레이션 시퀀스와 동등합니다.

또는 기본 케이스로 곱셈$({\displaystyle a}$ ↑ ${\displaystyle {}^{}}$ b = ${\displaystyle a}$×$$b) {\displaystyle(a\uparrow ^{0}b = a\times b)}을 선택하여 반복할 수 있습니다. 그러면 지수화는 반복 곱셈이 됩니다. 공식적인 정의는

${\displaystyle 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}}}$

${\displaystyle \mathrm{모든}}$ 정수 $a{\displaystyle ,}$ b${\displaystyle ,}$ ${\displaystyle n}$ ${\displaystyle a,b,n}$에 대해 ≥ 0${\displaystyle ,}$ $n$ ≥ 0, b ≥ 0 {\displaystyle a\geq 0,n\geq 0,b\geq 0}.

그러나 Knuth가 "nil-arrow"를 정의하지 않았다는 점에 유의하십시오(↑ 0 $displaystyle \uparrow$ ^{0}). 인덱싱의 지연을 제외하고 전체 하이퍼오퍼레이션 시퀀스와 일치하는 방식으로 부정적인 인덱스(n ≥ -2)로 표기법을 확장할 수 있습니다.

${\displaystyle H_{n}(a,b)=a[n]b=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.}$

상향 arrow 연산은 오른쪽 연관 연산입니다. $즉$, ${\displaystyle a}$ ↑ b ↑ $c$${\displaystyle a\uparrow b\uparrow$ c}은 (a ↑ b) ↑ c {\displaystyle b\uparrow c} 대신 ↑ (b ↑ c) {\displaystyle a\uparrow c)}로 이해됩니다. 모호성이 이슈가 되지 않는 경우 괄호가 삭제되는 경우가 있습니다.

값표

컴퓨팅 0↑ b

$0$ ↑ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ = ${\displaystyle H_{}}$ n${\displaystyle }$+ ${\displaystyle 2}$(0, b ) = 0 [ n + 2 ] b {\displaystyle 0\uparrow ^{n} b = H_{n+2} (0, b) = 0 [n+2] b} 계산 결과

0, when n = 0 ^{[nb 2]}

1, when n = 1 and b = 0 ^{[nb 1][nb 3]}

0, n = 1이고 b > 0일 때

1, n > 1이고 b가 짝수일 때 (0 포함)

0, n > 1이고 b가 홀수일 때

컴퓨팅 2↑ b

계산 $2$ ↑ ${\displaystyle {}^{}}$ b {\$displaystyle$ $2\uparrow ^{n}b}$는 무한 테이블로 재작성할 수 있습니다. 맨 위 행에$$ ${\displaystyle {숫자}^{}}$ $2{\displaystyle {\mathrm{}}^{}}$ b ${\$를 넣고 왼쪽 열에 값 2를 채웁니다. 표에서 숫자를 알아내려면, 바로 왼쪽에 있는 숫자를 선택한 다음, 방금 선택한 숫자에 의해 주어진 위치에서 이전 행에서 필요한 숫자를 찾아보세요.

$2$ ↑ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ {\$displaystyle$ 2$\uparrow ^{n}b}$ = H $n$$$+ 2 (${\displaystyle 2}$, b) ${\displaystyle$ H_{$n+2$} ($2$, b)} = 2 [n + 2 ] b {\displaystyle 2[n+2] b} = 2 → b → n

b ⁿ	1	2	3	4	5	6	공식
1	2	4	8	16	32	64	${\displaystyle 2^{b}}$
2	2	4	16	65536	${\displaystyle 2^{65{,}536}\approx 2.0\times 10^{19{,}728}}$	${\displaystyle 2^{2^{65{,}536}}\approx 10^{6.0\times 10^{19{,}727}}}$	${\displaystyle 2\uparrow \uparrow b}$
3	2	4	65536	${\displaystyle {\begin{matrix}\underbrace {2_{}^{.\,^{.\,^{.\,^{.\,^{2}}}}\\65{,}536{\mbox{copy of }}2\end{matrix}}$	${\displaystyle {\begin{matrix}\underbrace {2_{}^{.\,^{.\,^{.\,^{2}}}\\\underbrace {2_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{2}}}\\\65{,}536{\mbox{{copy of }}2\end{matrix}}$	${\displaystyle {\begin{matrix}\underbrace {2_{}^{.\,^{.\,^{.\,^{2}}}\\\underbrace {2_{}^{.\,^{.\,^{.\,^{.\,^{2}}}\\\,\underbrace {2_{}^{.\,^{.\,^{.\,^{.\,^{2}}}\\65{,}536{\mbox{copy of }}2\end{matrix}}}$	${\displaystyle 2\uparrow \uparrow b}$
4	2	4	${\displaystyle {\begin{matrix}\underbrace {2_{}^{.\,^{.\,^{.\,^{.\,^{2}}}}\\65{,}536{\mbox{copy of }}2\end{matrix}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{2}}}.}2}2} \\\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65{,}536{\mbox{ copies of }}2\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{2}}}.}2}2} \\\underbrace {^{^{^{^{^{2}.}.}.}2}2} \\\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65{,}536{\mbox{ copies of }}2\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{2}}}.}2}2} \\\underbrace {^{^{^{^{^{2}.}.}.}2}2} \\\underbrace {^{^{^{^{^{2}.}.}.}2}2} \\\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65{,}536{\mbox{ copies of }}2\end{matrix}}}$	${\displaystyle 2\uparrow \uparrow \uparrow b}$

테이블은 $n{\displaystyle }$ ${\displaystyle n}$ 및$$ $b{\displaystyle }$ ${\displaystyle b}$의 이동과$$모든 값에 3을 추가한 것을 제외하고는 Ackerman 함수와 동일합니다.

컴퓨팅 3↑ b

맨 위 행에$$ ${\displaystyle {숫자}^{}}$ $3{\displaystyle {\mathrm{}}^{}}$ b ${\$를 넣고 왼쪽 열에 값 3을 채웁니다. 표에서 숫자를 알아내려면, 바로 왼쪽에 있는 숫자를 선택한 다음, 방금 선택한 숫자에 의해 주어진 위치에서 이전 행에서 필요한 숫자를 찾아보세요.

${\displaystyle {}^{}}$ ↑ ${\displaystyle n^{}}$ b {\$displaystyle$ 3$\uparrow ^{n}b}$ = H ${\displaystyle n}$$$+ 2 (3, b) {\displaystyle H_{n+2} (3, b)} = 3 [n + 2 ] b {\displaystyle 3[n+2] b} = 3 → b → n

b ⁿ	1	2	3	4	5	공식
1	3	9	27	81	243	${\displaystyle 3^{b}}$
2	3	27	7,625,597,484,987	${\displaystyle 3^{7{,}625{,}597{,}484{,}987}\approx 1.3\times 10^{3{,}638{,}334{,}640{,}024}}$	${\displaystyle 3^{3^{7{,}625{,}597{,}484{,}987}}}$	${\displaystyle 3\uparrow \uparrow b}$
3	3	7,625,597,484,987	${\displaystyle {\begin{matrix}\underbrace {3_{}^{.\,^{.\,^{.\,^{.\,^{3}}}}\\7{,}625{,}597{,}484{,}987{\mbox{copies of }3\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {3_{}^{.\,^{.\,^{.\,^{3}}}\\\underbrace {3_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{3}}}\\\7{,}625{,}597{,}484{,}987{\mbox{{copy of }3\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {3_{}^{.\,^{.\,^{.\,^{3}}}\\\underbrace {3_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{3}}}\\\,\underbrace {3_{}^{.\,^{.\,^{.\,^{3}}}\\,{.\,^{.,{3}}}\\7{,}625{,}597{,}484{,}987{\mbox{copy of }3\end{matrix}}}$	${\displaystyle 3\uparrow \uparrow b}$
4	3	${\displaystyle {\begin{matrix}\underbrace {3_{}^{.\,^{.\,^{.\,^{.\,^{3}}}}\\7{,}625{,}597{,}484{,}987{\mbox{copies of }3\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{3}}}.}3}3} \\\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7{,}625{,}597{,}484{,}987{\mbox{ copies of }}3\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{3}}}.}3}3} \\\underbrace {^{^{^{^{^{3}.}.}.}3}3} \\\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7{,}625{,}597{,}484{,}987{\mbox{ copies of }}3\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{3}}}.}3}3} \\\underbrace {^{^{^{^{^{3}.}.}.}3}3} \\\underbrace {^{^{^{^{^{3}.}.}.}3}3} \\\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7{,}625{,}597{,}484{,}987{\mbox{ copies of }}3\end{matrix}}}$	${\displaystyle 3\uparrow \uparrow \uparrow b}$

컴퓨팅 4↑ b

맨 위 행에$$ 숫자 ${\displaystyle {4b}^{}}$ ${\$를 넣고 왼쪽 열에 값 4를 채웁니다. 표에서 숫자를 알아내려면, 바로 왼쪽에 있는 숫자를 선택한 다음, 방금 선택한 숫자에 의해 주어진 위치에서 이전 행에서 필요한 숫자를 찾아보세요.

${\displaystyle {}^{}}$ ↑ ${\displaystyle n^{}}$ b {\$displaystyle$ 4$\uparrow ^{n}b}$ = H ${\displaystyle n}$$$+ 2 ($4$, b) {\displaystyle H_{n+2}(4, b)} = 4 [n + 2] b {\displaystyle 4[n+2] b} = 4 → b → n

b ⁿ	1	2	3	4	5	공식
1	4	16	64	256	1024	${\displaystyle 4^{b}}$
2	4	256	${\displaystyle 4^{256}\approx 1.34\times 10^{154}}$	${\displaystyle 4^{4^{256}}\approx 10^{8.0\times 10^{153}}}$	${\displaystyle 4^{4^{256}}}$	${\displaystyle 4\uparrow \uparrow b}$
3	4	${\displaystyle 4^{4^{256}}\approx 10^{8.0\times 10^{153}}}$	${\displaystyle {\begin{matrix}\underbrace {4_{}^{.\,^{.\,^{.\,^{\,^{4}}}}\\\4^{4^{256}}{\mbox{copy of }4\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {4^{}^{.\,^{.\,^{.\,^{4}}}\\\underbrace {4_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{4}}}\\\4^{256}{\mbox{copy of }4\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {4_{}^{.\,^{.\,^{.\,^{4}}}\\\underbrace {4_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{4}}}\\\underbrace {4_{}^{.\,^{.\,^{.\,^{.\,^{4}}}\\\4^{256}}{\mbox{copy of }4\end{matrix}}}\{{}4\end{matrix}}}}}\\\underbrace {4_{}}}$	${\displaystyle 4\uparrow \uparrow b}$
4	4	${\displaystyle {\begin{matrix}\underbrace {4^{}^{.\,^{.\,^{.\,^{4}}}\\\underbrace {4_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{4}}}\\\4^{256}{\mbox{copy of }4\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{4}}}\\\underbrace {4_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{4}}}\\,\underbrace {4_{}^{.\,^{.\,^{.\,^{.\,^{.,^{4}}}\\\4^{256}{\mbox{copy of }4\end{matrix}}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{4}}}\\\underbrace {^{^{4}}}\\\underbrace {4_{}^{{}^{.\,^{.\,^{.\,^{.\,^{.\,^{4}}}\\,\underbrace {4_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{4}}}\\\4^{256}}\mbox{ 복사본}}\{4\end{matrix}}}\{\end}}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{4}}}\\\underbrace {^{^{4}}}\\\underbrace {^{^{4}}}\\\underbrace {^{^{4}}}\\,^{.\,^{.\,^{.\,^{.\,^{.,^{.\,^{4}}}\\\underbrace {4_{}^{.\,^{.\,^{.\,^{4}}}\\,^{.\,^{4}}}\\\4^{256}}{\mbox{copy of }4\end{}}}\matrix}}$	${\displaystyle 4\uparrow \uparrow \uparrow b}$

컴퓨팅 10↑ b

맨 위 행에$$ 숫자 ${\displaystyle {10}^{}}$ b ${\$를 넣고 왼쪽 열에 값 10을 채웁니다. 표에서 숫자를 알아내려면, 바로 왼쪽에 있는 숫자를 선택한 다음, 방금 선택한 숫자에 의해 주어진 위치에서 이전 행에서 필요한 숫자를 찾아보세요.

${\displaystyle {}^{}}$ ↑ ${\displaystyle n^{}}$ b {\$displaystyle$ $10\uparrow ^{n}b}$ = H ${\displaystyle n}$$$+ 2 (10, b) {\displaystyle H_{n+2} (10, b)} = 10 [n + 2 ] b {\displaystyle 10[n+2] b = 10 → b → n

b ⁿ	1	2	3	4	5	공식
1	10	100	1,000	10,000	100,000	${\displaystyle 10^{b}}$
2	10	10,000,000,000	${\displaystyle 10^{10,000,000,000}}$	${\displaystyle 10^{10,000,000}}$	${\displaystyle 10^{10^{10,000,000}}}$	${\displaystyle 10\uparrow \uparrow b}$
3	10	${\displaystyle {\begin{matrix}\underbrace {10_{}^{.\,^{.\,^{\,^{.\,^{10}}}}\\\10{\mbox{copy of }}10\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {10^{}^{.\,^{.\,^{.\,^{10}}}\\\underbrace {10_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{{10}}}\\\10{\mbox{copy of }\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {10_{}^{.\,^{.\,^{.\,^{10}}}\\\underbrace {10_{}^{.\,^{.\,^{.\,^{.\,^{}}}\\\,\underbrace {10_{}^{.\,^{.\,^{.\,^{.\,^{.,^{10}}}\\\10{\mbox{copy of }}10\end{matrix}}}}\\10\end{{}}}}}$	${\displaystyle {\begin{matrix}\underbrace {10_{}^{{.\,^{.\,^{.\,^{10}}}\\\underbrace {10_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{}}}\\\\underbrace {10_{}^{.\,^{.\,^{.\,^{.\,^{}}}\\\underbrace {10_{}^{.\,^{.\,^{.\,^{.\,^{.\,^{}}}\\\\mbox{{copy of }}\10\end{matrix}}}\10\end{{}}}}}}\\10\mbox{copy of }$	${\displaystyle 10\uparrow \uparrow b}$
4	10	${\displaystyle {\begin{matrix}\underbrace {^{^{^{10}}.}}10}\\10{\mbox{copy of }}\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{10}}}\\\underbrace {^{^{10}}}\\\underbrace {^{^{10}}}\\displaystyle {\mbox{copy of }}\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{10}}}\\underbrace {^{^{10}}}\\\underbrace {^{^{^{10}}}\\\underbrace {^{^{^{10}}}\\underbrace {^{^{^{10}}}}\\10{\mbox{copy of }10\end{matrix}}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{10}}\underbrace {^{^{10}}}\\\underbrace {^{^{10}}}\\\underbrace {^{^{^{10}}}}\\\underbrace {^{^{^{10}}}\\displaystyle {\mbox{copy of }}\end{matrix}}}\\displaystyle {\mbox{copy of }}\end{}}}\displaystyle {{^{^{^{10}}\end{matrix}}}\displaystyle {mbox{copy of }}\displaystyle}\displaystyle}\displace{10\end{{{}}}\displace{{mbox{copy of }}$	${\displaystyle 10\uparrow \uparrow \uparrow b}$

2 ≤ b ≤ 9인 경우 숫자 ${\displaystyle 10}$ ↑ ${\displaystyle {}^{}}$ ${\displaystyle b^{}}$ {\$displaystyle$ $10\uparrow ^{n}b}$의 숫자 순서는 n을 가장 중요한 숫자로 하는 사전적 순서이므로 이 8개 열의 숫자 순서는 단순히 한 줄로 늘어납니다. 3 ≤ b ≤ 99인 97열의 숫자도 마찬가지이며, 3 ≤ b ≤ 9,999,999인 경우에도 n = 1부터 시작하면 됩니다.

참고 항목

• 원시 재귀
• 하이퍼 오퍼레이션
• 바쁜 비버
• 커틀러 막대 표기법
• 테트레이션
• 펜테이션
• 아커만 함수
• 그레이엄의 번호
• 슈타인하우스-모저 표기법

메모들

참고문헌

외부 링크

• Weisstein, Eric W. "Knuth Up-Arrow Notation". MathWorld.
• 로버트 무나포, 라지 넘버: 상위 하이퍼 연산자