콘웨이 체인 화살표 표기법

수학자 존 호튼 콘웨이가 만든 콘웨이 체인 화살표 표기법은 어떤 극히 큰 숫자를 표현하는 수단이다.^[1] 단순히 우측 화살표로 분리된 양의 정수의 유한 시퀀스일 뿐이다$.$ 예를 들어${\displaystyle ,}$ $2{\displaystyle \mathrm{}}$ →${\displaystyle 3}$ →${\displaystyle 4}$ →${\displaystyle 5}$ → ${\displaystyle 6}$ $[\displaystyle 2\to 3\to 4\to 5\}$

대부분의 조합어 표기와 마찬가지로 정의는 재귀적이다. 이 경우 표기법은 결국 일부(대개 엄청난) 정수 전력으로 상승된 가장 왼쪽 숫자로 결정된다.

정의 및 개요

"콘웨이 체인"은 다음과 같이 정의된다.

• 임의의 양의 정수는 $길이{\displaystyle \mathrm{}}$ 1${\displaystyle 1}$의 체인이다$.$
• 길이 n의 체인에 이어 오른쪽 화살표 → 그리고 양의 정수가 함께 길이 $n{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle n+1}$의 체인을 형성한다$.$

어떤 체인은 아래의 다섯 가지 (기술적으로 4) 규칙에 따라 정수를 나타낸다. 두 체인은 같은 정수를 나타내는 경우 등가라고 한다.

$a{\displaystyle }$, ${\displaystyle b}$, c ${\displaystyle a,b,c}$은(는) 양의 정수를 나타내고$$${\displaystyle \mathrm{}}$# ${\displaystyle \#}$은(는) 체인의 변경되지 않은 나머지를 나타내도록$$ 한다. 다음:

1. 빈 체인(또는 길이 0의 체인)은 $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$과(와) 같음
2. 체인 $p{\displaystyle }$ ${\displaystyle p}$은(는) $숫자{\displaystyle }$ p ${\displaystyle p}$을(를) 나타낸다$$$.$
3. 체인 $a{\displaystyle }$→ ${\displaystyle b}$ ${\displaystyle a\rightarrow$ b$}$은(는) 숫자 ${\displaystyle b^{}}$ p ${\$b^{$p}$를 나타낸다$$$.$
4. 체인 $a{\displaystyle }$→ ${\displaystyle b}$→ ${\displaystyle c}$ ${\displaystyle a\rightarrow$ b$\rightarrow c}$는 ${\displaystyle {}^{}}$ ${\displaystyle c^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle a\uparrow ^{c}b}$을(Knuth의 위쪽 화살표 표기법 참조)를 나타낸다$$.$$
5. 체인${\displaystyle \mathrm{}}$#${\displaystyle }$→ ${\displaystyle 1}$ ${\displaystyle \#\오른쪽$ 화살표 $1}$은 체인${\displaystyle \mathrm{}}$# ${\displaystyle \#}$과(와) 같은 번호를 나타낸다.
6. 그렇지 않으면 체인${\displaystyle \mathrm{}}$#${\displaystyle }$→ ${\displaystyle (+}$ ${\displaystyle 1}$)${\displaystyle }$→ ${\displaystyle (\mathrm{b}}$+ 1${\displaystyle }$) ${\displaystyle \#\오른쪽$ 화살표$(a+1)\오른쪽$ 화살표$(b+1)}$은 체인$$${\displaystyle \mathrm{}}$#${\displaystyle }$→${\displaystyle }$( # →${\displaystyle a}$ → a${\displaystyle }$→ ${\displaystyle (b}$+ ${\displaystyle 1)}$→ $\displaysty \#\오른쪽 화살표(b+1$$오른쪽 화살표$.

특성.

1. 체인은 첫 번째 숫자의 완벽한 힘으로 평가한다.
2. 따라서 $1{\displaystyle \mathrm{}}$→ ${\displaystyle Y}$ ${\displaystyle 1\to Y}$은(는) $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$과(와) 같다.
3. ${\displaystyle X}$→ ${\displaystyle 1}$→ ${\displaystyle Y}$ ${\displaystyle X\to 1\to Y}$은(는) $X{\displaystyle }$ ${\displaystyle$ X$}$과(와) 동일함
4. ${\displaystyle 2}$→ ${\displaystyle 2}$→ Y ${\displaystyle 2\to 2\to Y}$이(가) $4{\displaystyle \mathrm{}}${\$displaystyle 4}$과(와) 같음
5. ${\displaystyle X}$→ ${\displaystyle 2}$→ 2 ${\displaystyle$ X$\to$ 2$\to 2}$은(는) $X{\displaystyle }$→${\displaystyle }$(${\displaystyle X}$ ${\displaystyle )}$ ${\displaystyle X\to (X)}($$X{\displaystyle }$→ X → ${\displaystyle X}$ ${\displaysty$ X$\to X}$와 혼동되지 않음)와 같다$.$

해석

화살 사슬을 전체적으로 다루기 위해서는 조심해야 한다. 화살표 체인은 이항 연산자의 반복적 적용을 설명하지 않는다. 다른 혼합된 기호의 체인(예: 3 + 4 + 5 + 6 + 7)은 의미 변경(연관성 참조) 없이 단편적으로(예: (3 + 4) + 5 + (6 + 7))로 간주할 수 있는 경우가 많으며, 적어도 3은⁴⁵⁶⁷ 콘웨이의 화살표 체인과는 다르게 규정된 순서에 따라 단계별로 평가할 수 있다.

예를 들면 다음과 같다.

• ${\displaystyle 2\오른쪽 화살표 2=2\오른쪽 화살표 \uparrow 3=2^{2^{2}}=16}$
• ${\displaystyle 2\오른쪽 화살표 \왼쪽(3\오른쪽 화살표 2\오른쪽)=2^{3^{2}=2^{3^{2}}=1998}$
• ${\displaystyle \왼쪽(2\오른쪽)\오른쪽)\오른쪽 화살표 2=\왼쪽(2^{3}\오른쪽)^{2}=64}$

네 번째 규칙은 핵심이다. 2개 이상으로 끝나는 4개 이상의 원소의 체인은 (대개 광대한) 증가된 음속 원소와 같은 길이의 체인이 된다. 그러나 그것의 궁극적인 요소는 감소되어 결국 두 번째 규칙이 체인을 단축할 수 있게 된다. 그 후 크누스를 "much details"라고 비유하면 체인은 세 가지 요소로 축소되고 세 번째 규칙은 재귀를 종료한다.

예

예는 금방 복잡해진다. 여기 몇 가지 작은 예가 있다.

${\displaystyle n}$

${\displaystyle =}$ n ${\displaystyle =n}($${\displaystyle \mathrm{규칙}}$ 1)

$p\to q}$

${\displaystyle =}$ ${\displaystyle {}^{}}$ ${\displaystyle q^{}}$ ${\$규칙 5 기준)

따라서 $3{\displaystyle \mathrm{}}$→ ${\displaystyle 4}$= 3 ${\displaystyle {4\mathrm{}}^{}}$= ${\displaystyle 81}$ {\$displaystyle 3\to 4=3^{4}=81}$

$4대 3대 2로 표시$

${\displaystyle =}$ ${\displaystyle 4}$ ${\displaystyle \uparrow \uparrow }$ ${\displaystyle 3}$ ${\displaystyle =4\uparrow \uparrow$ 3$}($규칙 3)

${\displaystyle =4\uparrow (4\uparrow 4)}$

${\displaystyle =4\uparrow 256}$

${\displaystyle =4^{256}}$

${\displaystyle =13,407,807,929,942,594,024,029,024,998,846,479,998,820,592,393,377,723,561,41,721,764,073,}$ ${\displaystyle 546,976,801,874,298,1903,427,690,031,080,080,858,190,486,050,035,853,753,882,811,946,569,946,084,096}$

${\displaystyle \ 약 1.34*10^{115}}$

$2에서 2로 a로$

${\displaystyle =}$ 2${\displaystyle }$[ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle 2}$ ${\displaystyle =2[\uparrow ^{a}]2}($규칙 3)

${\displaystyle =}$ ${\displaystyle 4}$ $[\displaystyle =4}$ $$(Knuth의 위쪽 화살표 표기법 참조)

$2에서 4까지 3까지$

${\displaystyle =}$ ${\displaystyle 2}$ ${\displaystyle \uparrow \uparrow \uparrow \uparrow }$ 4 ${\displaystyle =2\uparrow \uparrow \uparrow 4}($규칙 3)

${\displaystyle =2\uparrow \uparrow \uparrow (2\uparrow \uparrow 2)}$

${\displaystyle =2\uparrow \uparrow \uparrow (2\uparrow \uparrow 4)}$

${\displaystyle =2\uparrow \uparrow (2\uparrow (2\uparrow 2)}$

${\displaystyle =2\uparrow \uparrow (2\uparrow 4)}$

${\displaystyle =2\uparrow \uparrow (2\uparrow 16)}$

${\displaystyle =2\uparrow \uparrow(65536)}$

${\displaystyle =}$ ${\displaystyle {65536}^{}}$ ${\displaystyle {}^{}\mathrm{}}$ ${\$테타레이션 참조)

$2 대 3 대 2$

${\displaystyle =}$ ${\displaystyle 2}$→ ${\displaystyle 3}$→ ${\displaystyle (2}$→ 3${\displaystyle }$)${\displaystyle }$→ 1 ${\displaystyle =2\to 3\to$ ($2\to$ 3$)\to$ 1$}($규칙 4)

${\displaystyle =}$ ${\displaystyle 2}$→ ${\displaystyle 3}$→ ${\displaystyle 8}$→ 1 ${\displaystyle =2\to 3\to 8\to$ 1$}($규칙 5)

${\displaystyle =}$ ${\displaystyle 2}$→ ${\displaystyle 3}$→ 8 ${\displaystyle =2\to 3\to$ 8$}($규칙 2)

${\displaystyle =}$ ${\displaystyle 2}$ ${\displaystyle \uparrow \uparrow \uparrow \uparrow \uparrow }$ 3 ${\displaystyle 3}$ 3 ${\displaystyle =2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3}$ ($$규칙 3)

= 이전 수보다 훨씬 큼

$3대 2대 2대 2대 2로$

${\displaystyle =}$ ${\displaystyle 3}$→ ${\displaystyle 2}$→${\displaystyle }$( ${\displaystyle 3}$→ ${\displaystyle 2}$)${\displaystyle }$→ 1 ${\displaystyle =3\to 2\to$ ($3\to 2)\to$ 1$}($규칙 4)

${\displaystyle =}$ ${\displaystyle 3}$→ ${\displaystyle 2}$→ ${\displaystyle 9}$→ 1 ${\displaystyle =3\to 2\to 9\to$ 1$}($규칙 5)

${\displaystyle =}$ ${\displaystyle 3}$→ ${\displaystyle 2}$→ 9 $[\displaystyle =3\to 2\to$ 9$}$ ($$규칙 2)

${\displaystyle =}$ ${\displaystyle 3}$ ${\displaystyle \uparrow \uparrow \uparrow \uparrow \uparrow }$ 2 2 ${\displaystyle 2}$ ${\displaystyle =3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow }($규칙 3)

= 훨씬, 이전 수보다 훨씬 큼

체계적 예

4개 항(정수가 2 이하인 경우 포함)으로 가장 간단한 경우는 다음과 같다.

• $a\to b\to 2\to 2}$
  ${\displaystyle =a\to b\to 2\to (1+1)}$
  $(a\displaystyle =a\to b\to (a\to b)\to 1}$
  ${\displaystyle =a\to b\to a^{b}}$
  ${\displaystyle =a[a^{b}+2]b}$

(마지막으로 언급된 재산에 대한 설명)

• $a\to b\to 3\to 2}$
  $#\displaystyle =a\to b\to 3\to(1+1)}$
  $(a\displaystyle =a\to b\to b\to (a\to b)\to 1}$
  $(a\displaystyle =a\to b\to (a\to a^{b})}$
  $#\displaystyle =a[a\to b\to 2\to 2+2]b}$
• $b\to b\to 4\to 2}$
  $(a\displaystyle =a\to b\to b\to (a\to a^{b})}$
  $#\displaystyle =a[a\to b\to 3\to 2+2]b}$

우리는 여기서 패턴을 볼 수 있다. 만일 어떤 체인 $X{\displaystyle }$ ${\displaystyle X}$에 대해서라도$$$f{\displaystyle }$(${\displaystyle p}$)${\displaystyle }$= ${\displaystyle X}$→ ${\displaystyle p}$ ${\displaystyle f(p)(p)=X$\$to 2=f^{p$}{p$}$을(를) X${\displaystyle }$→ ${\displaystyle p}$→ p${\displaystyle }$→ ${\displaystyle 2}$ = ${\displaystyle \mathrm{p}{}^{}}$= f$^{p}를($기능력 참조)로 한다.$$

Applying this with ${\displaystyle X=a\to b}$, then ${\displaystyle f(p)=a[p+2]b}$ and ${\displaystyle a\to b\to p\to 2=a[a\to b\to (p-1)\to 2+2]b=f^{p}(1)}$

예를 들어, ${\displaystyle 10}$→ ${\displaystyle 6}$→ 3${\displaystyle }$→ ${\displaystyle 2}$= ${\displaystyle 10}$[ ${\displaystyle 10}$[ ${\displaystyle 1000002}$ ${\displaystyle ]}$ ${\displaystyle 6}$+ ${\displaystyle 2}$ ${\displaystyle ]}$ ${\displaystyle 6}$ ${\displaystyle 10\to 6\to$ 3=$10[1000002]6$

다음 단계로 이동:

• $a\to b\to 2\to 3}$
  ${\displaystyle =a\to b\to 2\to (2+1)}$
  $(a\displaystyle =a\to b\to b\to (a\to b)\2}$
  $a^{b}\to 2}$
  ${\displaystyle =f^{a^{b}(1)$

우리는 다시 일반화할 수 있다. When we write ${\displaystyle g_{q}(p)=X\to p\to q}$ we have ${\displaystyle X\to p\to q+1=g_{q}^{p}(1)}$, that is, ${\displaystyle g_{q+1}(p)=g_{q}^{p}(1)}$. In the case above, ${\d$$isplaystyle g_{2}(p)=a\to b\to p\to 2=f^{p}(1)}$ and ${\displaystyle g_{3}(p)=g_{2}^{p}(1)}$, so ${\displaystyle a\to b\to 2\to 3=g_{3}(2)=g_{2}^{2}(1)=g_{2}(g_{2}(1))=f^{f(1)}(1)=f^$${a^{b}(1)$

아커만 함수

Ackermann 함수는 Conway 체인 화살표 표기법을 사용하여 표시할 수 있다.

${\displaystyle A(m,n)=(2\to (n+3)\to (m-2))-3}$ for ${\displaystyle m\geq 3}$ (Since ${\displaystyle A(m,n)=2[m](n+3)-3}$ in hyperoperation)

이 때문에

${\displaystyle }$${\displaystyle }$→ ${\displaystyle n}$→ ${\displaystyle m}$= A ${\displaystyle (\mathrm{m}}$+ 2${\displaystyle }$, ${\displaystyle n}$- ${\displaystyle 3}$)${\displaystyle }$+ ${\displaystyle \mathrm{n}}$> 2 (\$displaystyle 2\to n\to n=A(m$+2,n-3$)+3}$의 경우 2 $(\displaystyle n)2}$

(${\displaystyle }$= $1{\displaystyle }$ ${\displaystyle n=1$} 및 ${\displaystyle \mathrm{n<img\; alt="n=1"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425"\; style="vertical-align:\; -0.338ex;\; width:5.656ex;\; height:2.176ex;"\; papago-attr-id="159">}}$= $2{\displaystyle }$ ${\displaystyle n=2$$\}$ = - 1 ${\displaystyle \{\backslash \mathrm{displaystyle}}$$(m$,-2)=-1} 및 A${\displaystyle (\mathrm{m},}$ -$1$${\displaystyle }$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystytle A(m,-1)=1}$과 대응하며$$, 논리적으로 추가할 수 있다.

그레이엄 수

그레이엄의 숫자 $G{\displaystyle }$ ${\displaystyle G}$ 자체는$$ 콘웨이 체인 화살표 표기법으로 간결하게 표현할 수 없지만, 다음과 같은 경계가 있다.

$오른쪽 화살표 3\오른쪽 화살표 3\오른쪽 화살표 2<G>3\오른쪽 화살표 3\오른쪽 화살표 65\오른쪽 화살표 2}$

Proof: We first define the intermediate function ${\displaystyle f(n)=3\rightarrow 3\rightarrow n={\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \uparrow } 3\\{\text{n arrows}}\end{matrix}}}$, which can be used to define Graham's number as ${\displa$$Ystyle G=f^{64}(4)}$. (위첨자 64는 기능적 힘을 나타낸다.)

규칙 2와 규칙 4를 거꾸로 적용하여 다음을 단순화한다.

${\displaystyle f^{64}(1)$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))}$ (with 64 ${\displaystyle 3\rightarrow 3}$'s)

$(\displaystyle =3\오른쪽 화살표 3\오른쪽 화살표 3\오른쪽 화살표 3\오른쪽 화살표 3\오른쪽 화살표 3\오른쪽 화살표 1\오른쪽 화살표 1)\오른쪽 화살표 1}$

${\displaystyle =3\오른쪽 화살표 3\오른쪽 화살표 64\오른쪽 화살표 2;}$

${\displaystyle f^{64}(4)=G;}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))}$ (with 64 ${\displaystyle 3\rightarrow 3}$'s)

${\displaystyle f^{64}(27)}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))}$ (with 64 ${\displaystyle 3\rightarrow 3}$'s)

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\cdots ))}$ (with 65 ${\displaystyle 3\rightarrow 3}$'s)

${\displaystyle =}$ ${\displaystyle 3}$→ ${\displaystyle 3}$→ ${\displaystyle 65}$→ ${\displaystyle 2}$ $[\displaystyle =3\오른쪽$ 화살표 $3\오른쪽$ 화살표 65$\오른쪽$ 화살표 $2}$ $$(위 내용과 동일함).

${\displaystyle =f^{65}(1)$

f는 엄격히 증가하고 있기 때문에,

${\displaystyle f^{64}(1)<f^{64}(4)<f^{64}(27)}$

그것이 주어진 불평등이다.

연결된 화살표를 사용하면 $G{\displaystyle }$ ${\displaystyle G}$보다 훨씬 큰 숫자를 지정하기가 매우 쉽다$.$ 예를 들어, ${\displaystyle 3}$→${\displaystyle }$3${\displaystyle }$→ ${\displaystyle 3}$ → ${\displaystyle 3}$ ${\displaystyle 3\오른쪽$ 화살표 $3\오른쪽$ 화살표 $3$

$3번 오른쪽 화살표 3번 오른쪽 화살표 3번 오른쪽 화살표 3번 화살표 3번$

$3\displaystyle =3\오른쪽 화살표 3\오른쪽 화살표 3\오른쪽 화살표 27\오른쪽 화살표 2)\오른쪽 화살표 2\,}$

${\displaystyle =f^{3\오른쪽 화살표 3\오른쪽 화살표 27\오른쪽 화살표 2}(1)$

${\displaystyle =f^{f^{27}(1)(1)$

숫자 $3{\displaystyle \mathrm{}}$→ ${\displaystyle 3}$→ ${\displaystyle 27}$→ 2$[\displaystyle 3\rightarrow 3\\$rightarrow ${\displaystyle {27}^{}}$$rightarrow 2}$${\displaystyle }$= ${\displaystyle {}^{}}$ 27 ( ${\displaystyle 1}$) ${\displaysty =f^{27}(1$)이$$ ${\displaystyle 65}$ ${\displaysty 65}$보다 훨씬 크기 때문에 그레이엄의 수보다 훨씬 많다$.$

CG 함수

콘웨이와 가이(Conway and Guy)는 다음과 같이 정의되는, 전체 표기법에 걸쳐 대각선을 이루는 간단한 단일 인수 함수를 만들었다.

${\displaystyle cg(n)=\underbrace {n\rightarrow n\rightarrow n\rightarrow \rightarrow \rightarrow n} _{n}}}}$

즉, 시퀀스는 다음과 같다.

${\displaystyle cg(1)=1}$

${\displaystyle cg(2)=2\to 2=2^{2}=4}$

${\displaystyle cg(3)=3\to 3\to 3=3\uparrow \uparrow \uparrow 3}$

$(\displaystyle cg(4)=4\to 4\to 4\to 4}$

$cg(5)=5\to 5\to 5\to 5\to 5}$

...

이 기능은, 예상할 수 있듯이, 엄청나게 빠르게 성장한다.

피터 허포드 증축

웹 개발자 겸 통계학자인 피터 허포드는 이 표기법의 확장을 다음과 같이 정의했다.

${\style a\wrightarrow _{b}c=\underbrace {a\오른쪽 화살표 _{b-1a\오른쪽 화살표 _{b-1a}\오른쪽 화살표 _{b-1}\오른쪽 화살표 _{b-1a\오른쪽 화살표 _{b-1}a}{c-1}텍스트 화살표 }a}}}}}}}}a}}}}}}:{c{{{n1}a}}}}}}}}}}}}}}}}}}}}}}}}}아래의 화살표$

${\display a\rightarrow _{1}b=a\rightarrow b}$

그렇지 않으면 모든 정상적인 규칙은 변하지 않는다.

${\displaystyle a\rightarrow _{2}(a-1)}$ is already equal to the aforementioned ${\displaystyle cg(a)}$, and the function ${\displaystyle f(n)=n\rightarrow _{n}n}$ is much faster growing than Conway and Guy's ${\displaystyle cg(n)}$.

$b{\displaystyle }$${\displaystyle {}_{}}$${\displaystyle b}$과 $d{\displaystyle }$ ${\displaystyle$ $a\rightarrow _{b$}$c$$\$rightarrow $_{d}e$$}$와 같은 표현은 숫자가 다르면$$ 불법이며$$, 하나의 체인은 한 가지 유형의 오른쪽 화살표만 있어야 한다는 점에 유의하십시오.

그러나 다음과 같이 약간 수정하면 다음과 같다.

${\displaystyle a\rightarrow _{b}c\rightarrow _{d}e=a\rightarrow _{b}\underbrace {c\rightarrow _{d-1}c\rightarrow _{d-1}c\rightarrow _{d-1}\dots \rightarrow _{d-1}c\rightarrow _{d-1}c\rightarrow _{d-1}c} _{e{\text{ arrows}}}}$

그러면 $a{\displaystyle {}_{}}$→ ${\displaystyle {}_{}}$ c${\displaystyle {}_{}}$→ ${\displaystyle {}_{}}$ ${\displaystyle e_{}}$ ${\displaystyle a\rightarrow _{b}c\rightarrow _{d}$^[2]e}가 합법화될 뿐만 아니라 전체적으로$$ 표기법이 훨씬 강해진다.

참고 항목

• 스타인하우스-모저 표기법
• 더욱 빠르게 증가하는 시퀀스를 체계적으로 생성

참조

외부 링크

• 팩토이드 > 큰 숫자
• 로버트 무나포의 거수
• J. H. Conway와 R. K. Guy의 숫자책