최근 수정 시각 : 2024-03-28 22:27:22

콘웨이 연쇄 화살표 표기법


수와 연산
Numbers and Operations
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		<colbgcolor=#765432> 수 체계 자연수 ( 홀수 · 짝수 · 소수 · 합성수) · 정수 · 유리수 ( 정수가 아닌 유리수) · 실수 ( 무리수 · 초월수) · 복소수 ( 허수) · 사원수
표현 숫자 ( 아라비아 숫자 · 로마 숫자 · 그리스 숫자) · 기수법( 과학적 기수법 · E 표기법 · 커누스 윗화살표 표기법 · 콘웨이 연쇄 화살표 표기법 · BEAF· 버드 표기법) · 진법 ( 십진법 · 이진법 · 8진법 · 12진법 · 16진법 · 60진법) · 분수 ( 분모 · 분자 · 기약분수 · 번분수 · 연분수 · 통분 · 약분) · 소수 { 유한소수 · 무한소수 ( 순환소수 · 비순환소수)} · 환원 불능 · 미지수 · 변수 · 상수
연산 사칙연산 ( 덧셈 · 뺄셈 · 곱셈 구구단 · 나눗셈) · 역수 · 절댓값 · 제곱근 ( 이중근호) · 거듭제곱 · 로그 ( 상용로그 · 자연로그 · 이진로그) · 검산 · 연산자 · 교환자
방식 암산 · 세로셈법 · 주판 · 산가지 · 네이피어 계산봉 · 계산기 · 계산자
용어 이항연산( 표기법) · 항등원과 역원 · 교환법칙 · 결합법칙 · 분배법칙
기타 수에 관련된 사항 ( 0과 1 사이의 수 · 음수 · 작은 수 · 큰 수) · 혼합 계산 ( 48÷2(9+3) · 111+1×2=224 · 2+2×2) · 0으로 나누기( 바퀴 이론) · 0의 0제곱 }}}}}}}}}

1. 개요2. 정의3. 성질4. 계산 예시
4.1. 사용

1. 개요

Conway chained arrow notation

큰 수의 표기법 중 하나로, 1995년에 존 호튼 콘웨이가 만들었다. 커누스 윗화살표 표기법과 비교했을 때 화살표의 방향만 달라진 것처럼 보여도 차원이 다른 성장률을 가졌다.[1][2]

2. 정의

  1. 모든 자연수는 길이가 [math(1)]인 연쇄 화살표이다.
  2. 길이가 [math(n)]인 연쇄 화살표에 오른쪽 화살표([math(\to)])와 자연수가 따라붙으면, 길이가 [math(n+1)]인 연쇄 화살표가 된다.

위 정의를 바탕으로 [math(p)], [math(q)], [math(r)]을 임의의 자연수, [math(X)]를 임의의 연쇄 화살표라 할 때, 모든 연쇄 화살표는 다음 규칙에 따라 자연수로 표현된다.
  1. 길이가 [math(0)]인 연쇄 화살표(an empty chain)는 자연수 [math(1)]과 같다.
  2. 연쇄 화살표 [math(p)]는 자연수 [math(p)]와 같다.
  3. 연쇄 화살표 [math(p\to q)]는 자연수 [math(p^q)]와 같다.
  4. 연쇄 화살표 [math(p\to q\to r)]은 자연수 [math(p\uparrow^rq)]와 같다.
  5. 연쇄 화살표 [math(X\to1)]은 연쇄 화살표 [math(X)]와 같다.
  6. 연쇄 화살표 [math(X\to(p+1)\to(q+1))]은 연쇄 화살표 [math(X\to(X\to p\to(q+1))\to q)]와 같다.

3. 성질

위 정의를 바탕으로 다음의 성질을 도출해낼 수 있다.
  1. [math(1\to X)]는 [math(1)]과 같다.
  2. [math(X\to1\to Y)]는 [math(X)]와 같다.
  3. [math(2\to2\to X)]는 [math(4)]와 같다.
  4. [math(X\to2\to2)]는 [math(X\to(X))]와 같다.

4. 계산 예시

  • [math(3 \rightarrow 3 \\
= 3^3 \\
= 27)]

* [math(4 \rightarrow 3 \rightarrow 2 \\
= 4 \rightarrow (4 \rightarrow 2 \rightarrow 2) \rightarrow 1 \\
= 4 \rightarrow (4 \rightarrow 2 \rightarrow 2) \\
= 4 \rightarrow (4 \rightarrow (4 \rightarrow 1 \rightarrow 2) \rightarrow 1) \\
= 4 \rightarrow (4 \rightarrow (4 \rightarrow 1 \rightarrow 2)) \\
= 4 \rightarrow (4 \rightarrow 4) \\
= 4 \rightarrow 4^4 \\
= 4^{4^4} \\
= 4^{256} \\
\approx 1.34 \times 10^{154})]

* [math(p \rightarrow q \rightarrow 2 \\
= p \rightarrow (p \rightarrow (q-1) \rightarrow 2) \rightarrow 1 \\
= p \rightarrow (p \rightarrow (q-1) \rightarrow 2) \\
= p \rightarrow (p \rightarrow (p \rightarrow (q-2) \rightarrow 2) \rightarrow 1) \\
= p \rightarrow (p \rightarrow (p \rightarrow (q-2) \rightarrow 2)) \\
\quad \cdots \\
= \underbrace{p \rightarrow (\cdots \rightarrow (p \rightarrow (p \rightarrow (p}_q \rightarrow 1 \rightarrow 2 )))\cdots) \\
= \underbrace{p \rightarrow (\cdots \rightarrow (p \rightarrow (p}_{q-1} \rightarrow p))\cdots) \\
= \underbrace{p \rightarrow (\cdots \rightarrow (p}_{q-2} \rightarrow p^p)\cdots) \\
\quad \cdots \\
= \underbrace{p^{p^{\cdot^{\cdot^{\cdot^p}}}}}_q \\
= p \uparrow\uparrow q)]

* [math(3 \rightarrow 3 \rightarrow 3 \\
= 3 \rightarrow (3 \rightarrow 2 \rightarrow 3) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow (3 \rightarrow 1 \rightarrow 3) \rightarrow 2) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow 3 \rightarrow 2) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow (3 \rightarrow 2 \rightarrow 2) \rightarrow 1) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow (3 \rightarrow 2 \rightarrow 2)) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow (3 \rightarrow (3 \rightarrow 1 \rightarrow 2) \rightarrow 1)) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow (3 \rightarrow (3 \rightarrow 1 \rightarrow 2))) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow (3 \rightarrow 3)) \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow 3^3) \rightarrow 2 \\
= 3 \rightarrow 3^{3^3} \rightarrow 2 \\
= 3 \rightarrow (3 \rightarrow (3^{3^3}-1) \rightarrow 2) \rightarrow 1 \\
= 3 \rightarrow (3 \rightarrow (3^{3^3}-1) \rightarrow 2) \\
\quad \cdots \\
= 3 \uparrow\uparrow\uparrow 3)]

* 그레이엄 수는 [math(3 \rightarrow 3 \rightarrow 64 \rightarrow 2)]보다는 크고 [math(3 \rightarrow 3 \rightarrow 65 \rightarrow 2)]보다는 작다.

* 그레이엄 수보다 더 크고 콘웨이의 테트라트리라고도 불리는 [math(3 \rightarrow 3 \rightarrow 3 \rightarrow 3)]은 [math(G(G(26)))]보다는 크고 [math(G(G(27)))]보다는 작다.

4.1. 사용

일상적으로는 거의 사용되지는 않지만, 큰 수를 표기할 때 가끔씩 사용된다. 큰 수 문서를 참고할 것.
[1] 임의의 자연수 [math(p)], [math(q)], [math(r)]에 대해 길이가 3인 연쇄 화살표 [math(p→q→r)]은 커누스 윗화살표 표기법 [math(p \uparrow^r q)]로 정의된다. 그리고 연쇄 화살표의 길이가 4 이상이 되면 커누스 윗화살표 표기법의 성장률을 아득히 능가하기 시작한다. 길이 5부터는 재귀 등의 방법으로는 따라잡을 수 없다. [2] 콘웨이 연쇄 화살표 표기법의 성장률은 결국 [math(\omega^2)]을 넘어서지 못한다. 물론 이것만으로도 그레이엄 수는 물론 하이퍼 그레이엄 수까지도 따위(?)로 만들어버리는 어마어마하게 큰 수다. 다만, fgh가 워낙 강력한 것뿐이다,

분류