그레이엄 수(Graham's number)는 미국의 수학자 로널드 그레이엄(Ronald Graham)이 이름을 붙인 특정한 자연수이다. 이 수는 조합론의 램지 이론(Ramsey theory)에서 등장하는 문제의 상계(upper bound)로 제시된 매우 큰 수이며, 현재까지 알려진 가장 큰 구체적인 양의 정수 중 하나로 유명하다.
정의
그레이엄 수는 특수한 반복 지수 표기법인 커누스 윗화살표 표기법(Knuth's up‑arrow notation)을 이용해 다음과 같이 정의된다.
- $g_1 = 3 \uparrow\uparrow\uparrow\uparrow 3$
- $g_{n+1} = 3 \uparrow^{,g_n} 3$ (여기서 $\uparrow^{,k}$는 위쪽 화살표가 $k$개인 연산)
그레이엄 수 $G$는 $g_{64}$ 로 정의된다. 즉, 위 과정을 64번 반복한 값이 바로 그레이엄 수이다.
역사·배경
- 1970년대: 램지 이론에서 특정 그래프 색칠 문제의 상한값을 구하기 위해 그레이엄이 이 수를 제시하였다.
- 1977년: 과학 저널 Scientific American에 이 수가 일반 대중에게 소개되면서 큰 관심을 받았다.
- 1980년: 기네스 세계 기록에 등재되어 “가장 큰 정수”로 기록되었다. 이후 수학적 연구에서 더 큰 수가 등장했지만, 그레이엄 수는 여전히 대중에게 가장 유명한 초거대수 중 하나이다.
수학적 의의
- 램지 이론: 그레이엄 수는 특정 차원의 초입방체(하이퍼큐브)에서 두 색으로 색칠된 가장자리 중, 같은 색으로만 이루어진 4개의 꼭짓점이 평면에 존재하지 않도록 하는 최소 차원을 추정하는 문제와 관련된다.
- 극한 성장: 커누스 위화살표 표기법을 사용한 정의 때문에, 그레이엄 수는 일반적인 재귀 수열이나 “바쁜 비버 수”보다도 훨씬 빠르게 증가한다.
- 실제 계산 불가능: 전체 자릿수를 표현하려면 관측 가능한 우주의 모든 물질을 플랑크 부피 단위로 전부 사용해도 부족할 정도로 크다. 다만, 마지막 13자리(…7262464195387)와 같은 일부 부분은 특수 알고리즘을 통해 계산할 수 있다.
관련 개념
- 구골플렉스(Googleplex), 스큐스 수(Skewes’s number), 모서 수(Moser’s number) 등도 매우 큰 수의 예시이지만, 그레이엄 수는 위의 수들보다도 훨씬 큰 것으로 알려져 있다.
- 이후 연구에서는 TREE(3), Friedman’s large numbers 등 그레이엄 수보다 큰 상계가 제시되었다.
참고 문헌·출처
- 위키백과, “그레이엄 수” (한국어) – 로널드 그레이엄이 정의한 수와 그 수학적 배경에 대한 상세 설명.
- 나무위키, “그레이엄 수” – 일반 대중에게 소개된 과정 및 문화적 영향.
본 항목은 검증된 학술·백과 자료에 기반하여 기술했으며, 확인되지 않은 추측이나 비공식적인 정보는 포함하지 않았다.
