콘웨이 연쇄 화살표 표기법

**콘웨이 연쇄 화살표 표기법**(Conway chained arrow notation)은 존 호턴 콘웨이가 개발한 아주 큰 수를 표기하는 방법이다. 단순히 오른쪽 화살표로 구분되는 자연수들의 수열이다. 대부분의 조합론적 표기법처럼, 이 표기법의 정의도 재귀적이다. 이 표기법은 결국 가장 왼쪽의 수의 (보통 엄청 큰) 거듭제곱을 나타낸다.
# 정의 및 개요
"콘웨이 연쇄 화살표 표기법"은 다음과 같이 정의된다. * 어떤 자연수는 길이가 1인 연쇄 화살표이다. * 길이가 *n*인 연쇄 화살표에 오른쪽 화살표 →와 자연수가 따라붙으면, 길이가 n+1인 연쇄 화살표가 된다. 모든 연쇄 화살표는 아래의 네 규칙을 따르는 정수를 나타낸다. 두 연쇄 화살표가 같은 정수를 나타낸다면 동등하다고 한다. p와 q가 양의 정수이고, X 가 부분 연쇄 화살표라고 하면, # 빈 연쇄 화살표 (또는 길이가 0인 연쇄 화살표)는 1을 나타내고, 연쇄 화살표 p는 p를 나타낸다. # p \to q는 거듭제곱 표현 p^q를 나타낸다. (*The Book of Numbers*에서 콘웨이는 길이가 2인 연쇄 화살표 p\rightarrow q를 정의하지 않았지만John H. Conway & Richard K. Guy, The Book of Numbers, 1996, p.59-62, 3번 째 변수 [p \rightarrow q \rightarrow r의 *r*]이 있을 때는 커누스 윗화살표로 간주하기 때문에 오른쪽 끝에 있는 \to 1을 떼어내도 이 규칙은 적용이 된다.) # X \to 1는 X와 동등하다. # 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
# 특성
# 길이가 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} # 연쇄 화살표 *X* → *Y*는 *X* → *p*의 형태이다: # *a*로 시작하는 연쇄 화살표는 *a*의 거듭제곱이다 # 연쇄 화살표 1 → *Y*는 1이다 # 연쇄 화살표 *X* → 1 → *Y*는 *X*이다 # 연쇄 화살표 2 → 2 → *Y*는 4이다 # 연쇄 화살표*X* → 2 → 2는 *X* → (*X*) (자신의 값이 *X*에 연결된 연쇄 화살표)이다
# 해석
연쇄 화살표를 *전체*로 생각 해야 한다는 점에 유의해야 한다. 연쇄 화살표 표기법은 이항 연산이 반복된 것을 표시한 것이 아니다. 다른 삽입된 기호들(예: 3 + 4 + 5 + 6 + 7)은 의미의 변동(결합법칙을 보라)이 없거나 적어도 차례차례 어떤 순서대로 계산(예: 34567는 오른쪽에서 왼쪽으로)해야 하지 않을 때는 종종 조각내서 생각한다(예: (3 + 4) + 5 + (6 + 7)). 콘웨이 화살표 표기법에서는 그렇지 않다. 예를 들면: * 2\rightarrow3\rightarrow2 = {}^32 = 2^{2^2} = 16 * 2\rightarrow\left(3\rightarrow2\right) = 2^{(3^2)} = 2^{3^2} = 512 * \left(2\rightarrow3\right)\rightarrow2 = \left(2^3\right)^2 = 64 네번째 규칙이 핵심이다: 3 이상의 길이를 가지고 2 이상의 숫자로 끝나는 연쇄 화살표는 같은 길이에 대개 끝에서 두번째 원소가 늘어난 연쇄 화살표가 된다. 하지만 *마지막* 원소는 줄어들어서, 결국 세 번째 규칙을 만족해서 연쇄 화살표의 길이가 짧아진다. 그리고, 연쇄 화살표는 두 개의 원소로 줄어들고 두 번째 규칙이 재귀를 끝낸다.
# 예시
예시는 빠르게 꽤 복잡해진다. 다음은 작은 예시들이다: *n* := *n* (규칙 1에 따라) *p→q* := *pq* (규칙 2에 따라) :Thus 3→4 = 34 = 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 (잉여 괄호를 제거(**r**emove **r**edundant **p**arentheses)) := 4→(4→4)→1 (3) := 4→(256)→1 (2) := 4→256→1 (rrp) := 4→256 (3) := 4256 (2) :=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 :≈1.34078079299×10154 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 (216 = 65536층의 탑) := 655362 (테트레이션을 보라) 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 = f27(1)은 65보다 훨씬 크기 때문이다.