콘웨이 연쇄 화살표 표기법 문서 원본 보기

{{위키데이터 속성 추적}}
'''콘웨이 연쇄 화살표 표기법'''(Conway chained arrow notation)은 [[존 호턴 콘웨이]]가 개발한 아주 [[대수 (수학)|큰 수]]를 표기하는 방법이다. 단순히 오른쪽 화살표로 구분되는 [[자연수]]들의 수열이다.

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

== 정의 및 개요 ==
"콘웨이 연쇄 화살표 표기법"은 다음과 같이 정의된다.
* 어떤 자연수는 길이가 1인 연쇄 화살표이다.
* 길이가 ''n''인 연쇄 화살표에 오른쪽 화살표 →와 자연수가 따라붙으면, 길이가 <math>n+1</math>인 연쇄 화살표가 된다.

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

<math>p</math>와 <math>q</math>가 양의 정수이고, <math>X</math> 가 부분 연쇄 화살표라고 하면,
# 빈 연쇄 화살표 (또는 길이가 0인 연쇄 화살표)는 1을 나타내고, 연쇄 화살표 <math>p</math>는 <math>p</math>를 나타낸다.
# <math>p \to q</math>는 [[거듭제곱]] 표현 <math>p^q</math>를 나타낸다. (''The Book of Numbers''에서 콘웨이는 길이가 2인 연쇄 화살표 <math>p\rightarrow q</math>를 정의하지 않았지만<ref>John H. Conway & Richard K. Guy, The Book of Numbers, 1996, p.59-62</ref>, 3번 째 변수 [<math>p \rightarrow q \rightarrow r</math>의 ''r'']이 있을 때는 커누스 윗화살표로 간주하기 때문에 오른쪽 끝에 있는 <math>\to 1</math>을 떼어내도 이 규칙은 적용이 된다.)
# <math>X \to 1</math>는 <math>X</math>와 동등하다.
# <math>X \to p \to (q + 1)</math>은 <math>X \to ( X \to ( \cdots (X \to ( X ) \to q)\cdots ) \to q ) \to q</math> <br />(''X''가 ''p''개, ''q''가 ''p''&nbsp;&minus;&nbsp;1개, 그리고 ''p''&nbsp;&minus;&nbsp;1쌍의 괄호가 있다. ''q''&nbsp;>&nbsp;0일 때만 적용이 된다)와 동등하다.

마지막 규칙은 [[줄임표]]를 피하기 위해서 재귀적으로 설명할 수 있다:
:4a. <math>X \to 1 \to (q + 1) = X</math>
:4b. <math>X \to (p + 1) \to (q + 1) = X \to (X \to p \to (q+1)) \to q</math>

==특성==
# 길이가 3인 연쇄 화살표는 [[하이퍼 연산]]과 [[커누스 윗화살표 표기법]]에 대응한다:
#:<math>\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}</math>
# 연쇄 화살표 ''X''&nbsp;→&nbsp;''Y''는 ''X''&nbsp;→&nbsp;''p''의 형태이다:
# ''a''로 시작하는 연쇄 화살표는 ''a''의 거듭제곱이다
# 연쇄 화살표 1&nbsp;→&nbsp;''Y''는 1이다
# 연쇄 화살표 ''X''&nbsp;→&nbsp;1&nbsp;→&nbsp;''Y''는 ''X''이다
# 연쇄 화살표 2&nbsp;→&nbsp;2&nbsp;→&nbsp;''Y''는 4이다
# 연쇄 화살표''X''&nbsp;→&nbsp;2&nbsp;→&nbsp;2는 ''X''&nbsp;→&nbsp;(''X'') (자신의 값이 ''X''에 연결된 연쇄 화살표)이다

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

예를 들면:
* <math>2\rightarrow3\rightarrow2 = {}^32 = 2^{2^2} = 16</math>
* <math>2\rightarrow\left(3\rightarrow2\right) = 2^{(3^2)} = 2^{3^2} = 512</math>
* <math>\left(2\rightarrow3\right)\rightarrow2 = \left(2^3\right)^2 = 64</math>

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

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

''n''
:= ''n'' (규칙 1에 따라)

''p→q''
:= ''p<sup>q</sup>'' (규칙 2에 따라)
:Thus 3→4 = 3<sup>4</sup> = 81

1→(''어떤 연쇄 화살표 표현'')
:= 1 전체 표현은 결국 1<sup>숫자</sup> = 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)
:= 4<sup>256</sup> (2)
:=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
:≈1.34078079299×10<sup>154</sup>

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)
:= <math>2^{2^{\dots^2}}</math> (2<sup>16</sup> = 65536층의 탑)
:= <sup>65536</sup>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보다 작은 정수가 없는) 네 항을 가지는 가장 간단한 예시:
* <math>a \to b \to 2 \to 2</math><br><math>= a \to b \to 2 \to (1 + 1)</math><br><math>= a \to b \to (a \to b) \to 1</math><br><math>= a \to b \to a^b</math><br><math>= a [a^b + 2] b</math>
: (마지막으로 언급한 특성을 따른다)
* <math>a \to b \to 3 \to 2</math><br><math>= a \to b \to 3 \to (1 + 1)</math><br><math>= a \to b \to (a \to b \to (a \to b) \to 1) \to 1</math><br><math>= a \to b \to (a \to b \to a^b)</math><br><math>= a [a\to b \to 2 \to 2 + 2] b</math>
* <math>a \to b \to 4 \to 2</math><br><math>= a \to b \to (a \to b \to (a \to b \to a^b))</math><br><math>= a [a \to b \to 3 \to 2 + 2] b</math>

여기서 패턴을 볼 수 있다. 어떤 연쇄 화살표 ''X''에 대해서 <math>f(p) = X \to p</math>라고 두면 <math>X \to p \to 2 = f^p(1)</math>이다 ([[함수의 합성|함수의 거듭제곱]]을 보라).

이것을 <math>X = a \to b</math>에 적용하면 <math>f(p) = a [p + 2]b</math>이고 <math>a \to b \to p \to 2 = a [a \to b \to (p - 1) \to 2 + 2] b = f^p(1)</math>이다

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

다음으로 넘어간다:
* <math>a \to b \to 2 \to 3</math><br><math>= a \to b \to 2 \to (2 + 1)</math><br><math>= a \to b \to (a \to b) \to 2</math><br><math>= a \to b \to a^b \to 2</math><br><math>= f^{a^b}(1)</math>

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

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

:''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'' &minus; 3) + 3

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

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

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

<math>f^{64}(1)</math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1))\cdots ))</math> (64 <math>3 \rightarrow 3</math>이 64개)
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3) \rightarrow 1) \cdots ) \rightarrow 1) \rightarrow 1</math>
:<math>= 3 \rightarrow 3 \rightarrow 64 \rightarrow 2;</math>

<math>f^{64}(4) = G;</math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 4))\cdots ))</math> (<math>3 \rightarrow 3</math>이 64개)

<math>f^{64}(27)</math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27))\cdots ))</math> (<math>3 \rightarrow 3</math>이 64개)
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (3 \rightarrow 3)))\cdots ))</math> (<math>3 \rightarrow 3</math>이 65개)
:<math>= 3 \rightarrow 3 \rightarrow 65 \rightarrow 2</math> (위에서 한 것처럼 계산한다).

''f''가 [[강한 증가 함수]]이기 때문에
:<math>f^{64}(1) < f^{64}(4) < f^{64}(27)</math>
이므로 <math>3 \rightarrow 3 \rightarrow 64 \rightarrow 2 < G < 3 \rightarrow 3 \rightarrow 65 \rightarrow 2</math>를 얻을 수 있다.

연쇄 화살표 표기법을 사용하면, 이것보다도 더 큰 수를 특정하는 것이 매우 쉽다. 예를 들면,
:<math> 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) </math>
이 수는 그레이엄 수 보다 훨씬 크다. 왜냐하면 <math>3 \rightarrow 3 \rightarrow 27 \rightarrow 2</math> = f<sup>27</sup>(1)은 65보다 훨씬 크기 때문이다.

== 같이 보기 ==
* [[커누스 윗화살표 표기법]]
* [[그레이엄 수]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* [http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm Factoids &gt; big numbers]
* [http://www.mrob.com/pub/math/largenum.html Robert Munafo's Large Numbers]
* [https://docs.google.com/viewer?a=v&q=cache:gv7MebfOp6oJ:futuretg.com/FTHumanEvolutionCourse/FTFreeLearningKits/01-MA-Mathematics,%2520Economics%2520and%2520Preparation%2520for%2520University/011-MA11-UN03-10-Number%2520Theory%2520and%2520Cryptography/Additional%2520Resources/J.H.%2520Conway,%2520R.K.%2520Guy%2520-%2520The%2520Book%2520of%2520Numbers.pdf+The+Book+of+Numbers+by+J.+H.+Conway+and+R.+K.+Guy&hl=en&pid=bl&srcid=ADGEEShgWcsuShpVnS-hYtNfbwOq4TEpkeQ7YOZGVEk-omzaiEs4VKdsXFz1Su-Uh1po2QEXnmSivKhRixbQK6puTsf92WYUWuAcxyeOpXvn4JcEs-wsAJ1aF1Bk5I4JU7WCKoOUQCTL&sig=AHIEtbT5_BLlXtiF0i6dMiG6hNP8C58zKw The Book of Numbers by J. H. Conway and R. K. Guy]

{{큰 수}}

[[분류:수학 표기법]]
[[분류:큰 수]]