그레이엄 수

그레이엄 수는 수학적 증명에 사용된 매우 큰 수로, 램지 이론과 관련된 문제에서 상한으로 등장한다. 이 수는 수학적 표기법에서조차 표현하기 매우 어려울 정도로 커서, 일상적인 표기법으로는 나타낼 수 없다. 그레이엄 수는 수학자 로널드 그레이엄(Ronald Graham)의 이름을 따서 명명되었다.

개요

그레이엄 수는 특정한 재귀 알고리즘을 통해 정의되는데, 이 알고리즘은 화살표 표기법이라고 불리는 커누스 윗화살표 표기법을 반복적으로 적용하여 수를 급격하게 증가시킨다. 그레이엄 수는 이 표기법을 사용하여 정의된 g1부터 시작하여 g64까지 이어지는 수열의 마지막 항인 g64로 정의된다.

정의

그레이엄 수를 정의하는 과정은 다음과 같다. 먼저, 커누스 윗화살표 표기법을 확장한 다음과 같은 연산자를 정의한다:

• a ↑ b = a^b (a의 b제곱)
• a ↑↑ b = a ↑ (a ↑ (a ↑ ... a)) (a가 b개, 오른쪽부터 계산)
• a ↑↑↑ b = a ↑↑ (a ↑↑ (a ↑↑ ... a)) (a가 b개, 오른쪽부터 계산)
• 일반적으로, a ↑ⁿ b = a ↑^(n-1) (a ↑^(n-1) (a ↑^(n-1) ... a)) (a가 b개, 오른쪽부터 계산)

이 표기법을 이용하여, 그레이엄 수는 다음과 같이 정의된다.

1. g1 = 3 ↑↑↑↑ 3
2. gn+1 = 3 ↑^(gn) 3 (여기서 ↑^(gn)은 윗화살표가 gn개 있다는 의미)

따라서 그레이엄 수는 g64로 정의된다.

크기

그레이엄 수는 너무나 커서, 그 크기를 직관적으로 이해하는 것은 불가능하다. 이를 설명하기 위해, 우주의 모든 원자를 잉크로 덮어 그 위에 숫자를 적는다고 해도 그레이엄 수를 표현하기에는 턱없이 부족하다는 비유가 사용된다.

중요성

그레이엄 수는 수학적으로 의미 있는 큰 수의 대표적인 예시이며, 계산 가능성과 표현 가능성의 한계를 보여주는 사례로 자주 인용된다. 또한, 큰 수에 대한 연구 및 표기법 개발에 영감을 제공하는 역할을 한다.