콘웨이 연쇄 화살표 표기법(Conway chained arrow notation)은 영국의 수학자 존 호턴 콘웨이(John Horton Conway)가 리처드 K. 가이(Richard K. Guy)와의 공저 《숫자의 책》(The Book of Numbers, 1996)에서 개발한 큰 수를 표기하는 방법이다. 이 표기법은 자연수들을 오른쪽 화살표(→)로 구분한 유한 수열로 구성되며, 재귀적 정의를 통해 매우 큰 수를 간결하게 표현할 수 있다.
정의
콘웨이 연쇄 화살표는 다음과 같이 정의된다. 임의의 자연수는 길이가 1인 연쇄 화살표이며, 길이가 n인 연쇄 화살표에 오른쪽 화살표(→)와 자연수가 따라붙으면 길이가 n+1인 연쇄 화살표가 된다. 모든 연쇄 화살표는 다음 여섯 가지 규칙에 따라 하나의 정수를 나타낸다. p, q, r을 양의 정수, X를 길이 1 이상의 부분 연쇄 화살표라고 할 때:
- 빈 연쇄 화살표(길이 0)는 1을 나타낸다.
- 연쇄 화살표 p는 p 자신을 나타낸다.
- p → q는 p의 q제곱(p^q)을 나타낸다.
- p → q → r은 커누스 윗화살표 표기법으로 p ↑^r q와 같다.
- X → 1 및 X → 1 → p는 X와 동등하다.
- X → (p+1) → (q+1)은 X → (X → p → (q+1)) → q와 동등하다.
특성
이 표기법의 주요 성질은 다음과 같다. 1로 시작하는 연쇄 화살표는 항상 1이다. X → 1 → Y는 X와 같다. 2 → 2 → Y는 항상 4이다. X → 2 → 2는 X → (X)와 같다. 길이가 3인 연쇄 화살표 p → q → r은 커누스 윗화살표 표기법과 하이퍼 연산에 대응하며, 길이가 4 이상이 되면 커누스 윗화살표 표기법의 성장률을 훨씬 능가한다.
계산 예시
3 → 3 = 3^3 = 27
4 → 3 → 2 = 4 → (4 → 2 → 2) → 1 = 4 → (4 → 4) = 4 → 256 = 4^256 ≈ 1.34 × 10^154
2 → 2 → 4 = 2 → (2) → 3 = 2 → 2 → 3 = 2 → 2 → 2 = 2 → 2 → 1 = 2 → 2 = 4
그레이엄 수와의 관계
그레이엄 수 G는 콘웨이 연쇄 화살표 표기법으로 직접 간결하게 표현할 수는 없지만, 다음과 같은 범위로 나타낼 수 있다:
3 → 3 → 64 → 2 < G < 3 → 3 → 65 → 2
이는 중간 함수 f(n) = 3 → 3 → n을 정의하고 G = f^64(4)임을 이용하여 증명된다. 3 → 3 → 3 → 3은 그레이엄 수보다 훨씬 더 큰 수이다.
아커만 함수와의 관계
아커만 함수는 콘웨이 연쇄 화살표 표기법으로 다음과 같이 표현할 수 있다. m ≥ 3일 때 A(m, n) = (2 → (n+3) → (m-2)) - 3이다.
CG 함수
콘웨이와 가이는 표기법 전체를 대각화하는 단일 인자 함수 cg(n)을 정의했다. cg(n)은 n이 n개 나열된 연쇄 화살표 n → n → n → ... → n을 의미하며, 매우 빠르게 증가하는 함수이다.
확장
피터 허포드(Peter Hurford)는 이 표기법에 아래첨자를 도입한 확장을 제안했으며, 쿠키폰스터(Cookiefonster)는 화살표 유형을 위첨자로 표시하는 다른 확장을 제안했다. 이러한 확장들은 원래 표기법보다 더 빠른 성장률을 가진다.
의의
콘웨이 연쇄 화살표 표기법은 커누스 윗화살표 표기법을 일반화한 것으로, 큰 수 표기법의 발전에 중요한 역할을 했다. 이 표기법은 조너선 바워스의 선형 배열 표기법에서 4항 배열과 대략 비슷한 수준의 성장률을 가지며, 빠르게 증가하는 계층(FGH)에서 ω^2에 해당하는 성장률을 보인다.
