콘웨이 연쇄 화살표 표기법

콘웨이 연쇄 화살표 표기법(Conway chained arrow notation)은 존 호턴 콘웨이가 개발한 아주 큰 수를 표기하는 방법이다. 단순히 오른쪽 화살표로 구분되는 자연수들의 수열이다.

대부분의 조합론적 표기법처럼, 이 표기법의 정의도 재귀적이다. 이 표기법은 결국 가장 왼쪽의 수의 (보통 엄청 큰) 거듭제곱을 나타낸다.

정의 및 개요

"콘웨이 연쇄 화살표 표기법"은 다음과 같이 정의된다.

• 어떤 자연수는 길이가 1인 연쇄 화살표이다.
• 길이가 n인 연쇄 화살표에 오른쪽 화살표 →와 자연수가 따라붙으면, 길이가 $n+1$인 연쇄 화살표가 된다.

모든 연쇄 화살표는 아래의 네 규칙을 따르는 정수를 나타낸다. 두 연쇄 화살표가 같은 정수를 나타낸다면 동등하다고 한다.

$p$와 $q$가 양의 정수이고, $X$ 가 부분 연쇄 화살표라고 하면,

1. 빈 연쇄 화살표 (또는 길이가 0인 연쇄 화살표)는 1을 나타내고, 연쇄 화살표 $p$는 $p$를 나타낸다.
2. $p\to q$는 거듭제곱 표현 $p^{q}$를 나타낸다. (The Book of Numbers에서 콘웨이는 길이가 2인 연쇄 화살표 $p\rightarrow q$를 정의하지 않았지만, 3번 째 변수 [$p\rightarrow q\rightarrow r$의 r]이 있을 때는 커누스 윗화살표로 간주하기 때문에 오른쪽 끝에 있는 $\to 1$을 떼어내도 이 규칙은 적용이 된다.)
3. $X\to 1$는 $X$와 동등하다.
4. $X\to p\to (q+1)$은 $X\to (X\to (\cdots (X\to (X)\to q)\cdots )\to q)\to q$
   (X가 p개, q가 p − 1개, 그리고 p − 1쌍의 괄호가 있다. q > 0일 때만 적용이 된다)와 동등하다.

마지막 규칙은 줄임표를 피하기 위해서 재귀적으로 설명할 수 있다:

4a. $X\to 1\to (q+1)=X$

4b. $X\to (p+1)\to (q+1)=X\to (X\to p\to (q+1))\to q$

특성

1. 길이가 3인 연쇄 화살표는 하이퍼 연산과 커누스 윗화살표 표기법에 대응한다:

   ${\begin{matrix}p\to q\to r=p[r+2]q=p\!\!\!&\underbrace {\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow } &\!\!\!q=p\uparrow ^{r}q.\\&\!\!\!r{\text{ arrows}}\!\!\!\end{matrix}}$

2. 연쇄 화살표 X → Y는 X → p의 형태이다:
3. a로 시작하는 연쇄 화살표는 a의 거듭제곱이다
4. 연쇄 화살표 1 → Y는 1이다
5. 연쇄 화살표 X → 1 → Y는 X이다
6. 연쇄 화살표 2 → 2 → Y는 4이다
7. 연쇄 화살표X → 2 → 2는 X → (X) (자신의 값이 X에 연결된 연쇄 화살표)이다

해석

연쇄 화살표를 전체로 생각 해야 한다는 점에 유의해야 한다. 연쇄 화살표 표기법은 이항 연산이 반복된 것을 표시한 것이 아니다. 다른 삽입된 기호들(예: 3 + 4 + 5 + 6 + 7)은 의미의 변동(결합법칙을 보라)이 없거나 적어도 차례차례 어떤 순서대로 계산(예: 3⁴⁵⁶⁷는 오른쪽에서 왼쪽으로)해야 하지 않을 때는 종종 조각내서 생각한다(예: (3 + 4) + 5 + (6 + 7)). 콘웨이 화살표 표기법에서는 그렇지 않다.

예를 들면:

• $2\rightarrow 3\rightarrow 2={}^{3}2=2^{2^{2}}=16$
• $2\rightarrow \left(3\rightarrow 2\right)=2^{(3^{2})}=2^{3^{2}}=512$
• $\left(2\rightarrow 3\right)\rightarrow 2=\left(2^{3}\right)^{2}=64$

네번째 규칙이 핵심이다: 3 이상의 길이를 가지고 2 이상의 숫자로 끝나는 연쇄 화살표는 같은 길이에 대개 끝에서 두번째 원소가 늘어난 연쇄 화살표가 된다. 하지만 마지막 원소는 줄어들어서, 결국 세 번째 규칙을 만족해서 연쇄 화살표의 길이가 짧아진다. 그리고, 연쇄 화살표는 두 개의 원소로 줄어들고 두 번째 규칙이 재귀를 끝낸다.

예시

예시는 빠르게 꽤 복잡해진다. 다음은 작은 예시들이다:

n

= n (규칙 1에 따라)

p→q

= p^q (규칙 2에 따라)

Thus 3→4 = 3⁴ = 81

1→(어떤 연쇄 화살표 표현)

= 1 전체 표현은 결국 1^숫자 = 1이 되기 때문이다. (실제로 1이 포함되는 연쇄 화살표는 1 앞에서 잘라버릴 수 있다. 예: 어떤 (포함된) 연쇄 화살표 X,Y에 대해서 X→1→Y=X이다.)

4→3→2

= 4→(4→(4)→1)→1 (규칙 4) 그리고, 안의 괄호에서 바깥쪽으로 진행한다,

= 4→(4→4→1)→1 (잉여 괄호를 제거(remove redundant parentheses))

= 4→(4→4)→1 (3)

= 4→(256)→1 (2)

= 4→256→1 (rrp)

= 4→256 (3)

= 4²⁵⁶ (2)

= 정확히 13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 096 ≈ 1.34078079299 × 10¹⁵⁴

2→2→4

= 2→(2)→3 (규칙 4)

= 2→2→3 (rrp)

= 2→2→2 (4, rrp)

= 2→2→1 (4, rrp)

= 2→2 (3)

= 4 (2) (사실, 2 두 개로 시작하는 연쇄 화살표는 4이다.)

2→4→3

= 2→(2→(2→(2)→2)→2)→2 (by 4) X(여기에서는 2)의 네 복사본은 q (여기에서는 마찬가지로 2)의 세 복사본과 구분하기 위해서 굵은 글씨로 표시했다

= 2→(2→(2→2→2)→2)→2 (rrp)

= 2→(2→(4)→2)→2 (이전 예시)

= 2→(2→4→2)→2 (rrp) (다음 식에서 확장시키는 것을 양 쪽 다 굵은 글씨로 표시했다)

= 2→(2→(2→(2→(2)→1)→1)→1)→2 (4)

= 2→(2→(2→(2→2→1)→1)→1)→2 (rrp)

= 2→(2→(2→(2→2)))→2 (3 반복)

= 2→(2→(2→(4)))→2 (2)

= 2→(2→(16))→2 (2)

= 2→65536→2 (2,rrp)

= 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (4) 괄호가 65535쌍

= 2→(2→(2→(...2→(2→(2))...))) (3 반복)

= 2→(2→(2→(...2→(4))...))) (2)

= 2→(2→(2→(...16...))) (2)

= $2^{2^{\dots ^{2}}}$ (2¹⁶ = 65536층의 탑)

= ⁶⁵⁵³⁶2 (테트레이션을 보라)

2→3→2→2

= 2→3→(2→3)→1 (규칙 4)

= 2→3→8 (2와 3)

= 2→(2→2→7)→7 (규칙 4)

= 2→4→7 (앞의 2 두 개는 4이다 [특성6])

= 2→(2→(2→2→6)→6)→6 (4)

= 2→(2→4→6)→6 (특성6)

= 2→(2→(2→(2→2→5)→5)→5)→6 (4)

= 2→(2→(2→4→5)→5)→6 (특성6)

= 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6 (4)

= 2→(2→(2→(2→4→4)→4)→5)→6 (특성6)

= 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4) →5)→6 (4)

= 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6 (특성6)

= 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6 (이전 예시)

= 이전의 숫자보다 훨씬 큼

3→2→2→2

= 3→2→(3→2)→1 (4)

= 3→2→9 (2와 3)

= 3→3→8 (4)

체계적인 예시

(2보다 작은 정수가 없는) 네 항을 가지는 가장 간단한 예시:

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

(마지막으로 언급한 특성을 따른다)

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

여기서 패턴을 볼 수 있다. 어떤 연쇄 화살표 X에 대해서 $f(p)=X\to p$라고 두면 $X\to p\to 2=f^{p}(1)$이다 (함수의 거듭제곱을 보라).

이것을 $X=a\to b$에 적용하면 $f(p)=a[p+2]b$이고 $a\to b\to p\to 2=a[a\to b\to (p-1)\to 2+2]b=f^{p}(1)$이다

따라서 예를 들어 보면 $10\to 6\to 3\to 2=10[10[1000002]6+2]6$이다.

다음으로 넘어간다:

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

또다시 일반화 할 수 있다. $g_{q}(p)=X\to p\to q$라고 하면 $X\to p\to q+1=g_{q}^{p}(1)$이 된다. 즉, $g_{q+1}(p)=g_{q}^{p}(1)$이다. 위의 경우에서, $g_{2}(p)=a\to b\to p\to 2=f^{p}(1)$이고 $g_{3}(p)=g_{2}^{p}(1)$이므로 $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)$이다.

아커만 함수

아커만 함수는 콘웨이 연쇄 화살표 표기법으로 표시할 수 있다:

m > 2일 때 A(m, n) = (2 → (n + 3) → (m − 2)) − 3 (하이퍼 연산으로 A(m, n) = 2 [m] (n + 3) - 3이기 때문이다)

따라서

n > 2일 때 2 → n → m = A(m + 2,n − 3) + 3

(n = 1과 n = 2는 논리적으로 A(m, −2) = −1과 A(m, −1) = 1에 대응하도록 추가할 수 있다).

그레이엄 수

그레이엄 수 $G$ 자체는 콘웨이 표기법으로 간결하게 표현할 수는 없지만, 중간의 함수 $f(n)=3\rightarrow 3\rightarrow n$를 정의하면 다음을 얻을 수 있다: $G=f^{64}(4)$ (함수의 거듭제곱을 보라)이고, $3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2$이다

증명: 규칙 3과 규칙 4의 정의를 순서대로 적용하면 다음을 얻을 수 있다:

$f^{64}(1)$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))$ (64 $3\rightarrow 3$이 64개)

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1)\cdots )\rightarrow 1)\rightarrow 1$

$=3\rightarrow 3\rightarrow 64\rightarrow 2;$

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

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))$ ($3\rightarrow 3$이 64개)

$f^{64}(27)$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))$ ($3\rightarrow 3$이 64개)

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\cdots ))$ ($3\rightarrow 3$이 65개)

$=3\rightarrow 3\rightarrow 65\rightarrow 2$ (위에서 한 것처럼 계산한다).

f가 강한 증가 함수이기 때문에

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

이므로 $3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2$를 얻을 수 있다.

연쇄 화살표 표기법을 사용하면, 이것보다도 더 큰 수를 특정하는 것이 매우 쉽다. 예를 들면,

$3\rightarrow 3\rightarrow 3\rightarrow 3~~=~~3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2\,~~=~~f^{3\rightarrow 3\rightarrow 27\rightarrow 2}(1)~~=~~f^{f^{27}(1)}(1)$

이 수는 그레이엄 수 보다 훨씬 크다. 왜냐하면 $3\rightarrow 3\rightarrow 27\rightarrow 2$ = f²⁷(1)은 65보다 훨씬 크기 때문이다.

같이 보기

• 커누스 윗화살표 표기법
• 그레이엄 수

외부 링크

• Factoids > big numbers
• Robert Munafo's Large Numbers
• The Book of Numbers by J. H. Conway and R. K. Guy