그레이엄 수

그레이엄 수(Graham's number)는 미국의 수학자 로널드 그레이엄이 이름을 붙인 특정한 자연수의 명칭으로서, 로 표시한다. 램지 이론에 대한 수학 문제의 해결과정에서 상계(upper bound)로 제시된 큰 수로서, 1980년 기네스 북에 의해 수학적 의미를 갖는 수 가운데 가장 큰 수의 일례로 들리기도 했다. 일상적인 자연수 표기법이나 거듭제곱의 방법으로는 도저히 나타낼 수 없어서, 특수하게 정의된 큰 수 표기법을 사용하여 나타낸다. 이 수 전체는 아직까지 계산된 적도, 또한 그렇게 계산된 수를 나열하는 것도 불가능하다. 다만, 계산 과정에 규칙성이 있기 때문에 1의 자리부터 마지막 500자리까지의 수는 알려져 있다.

하지만 이보다 큰 수는 만들어낼 수 있다. 덧셈을 재귀하면 곱셈, 지수, 화살표, G(n), 콘웨이 화살표 식으로 가게 된다. 단순히 재귀만 해도 하이퍼 그레이엄은 물론, {3,3,3,2}까지도 넘을 수 있다. 그리고 콘웨이 화살표 이후부터는 재귀만 해서는 다음 단계로 넘어갈 수 없다.

문제 

N차원 초입방체의 모서리, 모든 대각선을 포함한 완전 그래프 을 그린다. 그래프의 변을 두 가지 색으로 칠할 때, 몇 차원 이상이 되면 초입방체의 한평면에 있는 4개의 점에 대해서 4 개 꼭짓점을 이은 완전 그래프 는 하나의 색으로 되어 있다. 그레이엄은 이 N의 상계로서 그레이엄의 수를 제시하였다.

유도 방법 
그레이엄 수의 기본은 3이다. 3을 밑으로 하여 3의 연산을 무수히 반복하는 과정이 되풀이된다. 물론 실제로 무수히 반복하지는 않고 유한하지만, 그 수의 크기가 극도로 크다는 말로는 모자라기 때문에 이 수를 감당해내는 것조차도 불가능하다. 이 연산을 나타내기 위해서 커누스 윗화살표 표기법의 이해가 필요하다. 커누스 윗화살표 표기법은 하이퍼연산자라고도 하며, 덧셈-곱셈-거듭제곱-테트레이션-펜테이션-....등으로 그 직전 연산의 반복으로 상위 연산을 정의하는 기호이다. 이 커누스 윗화살표 표기법을 재귀하면 G(n)에 도달한다.

커누스 윗화살표 표기법을 이용하여 f(n)를 다음과 같이 정의하자.

지수를 조금만 쌓았음에도 벌써 조단위다. 게다가 이 지수는 앞으로 늘어날 화살표 앞에서는 먼지만도 못하다.

   (f(2)번 반복)  (7,625,597,484,987번 반복)

벌써부터 상상을 깨버린 수가 나왔다. 화살표 3개만 되었음에도 지수로 표시하기에도 그냥 써서는 평생 써도 다 못 쓸 정도로 크며, 2cm 크기로 써도 지수 계단의 높이는 지구에서 태양까지 도달한다. 만약 구골플렉스 진법으로 이보다 큰 수를 만들려면 숫자를 하나씩 써서는 당연히 못 쓰고, 임의의 숫자 뒤에 숫자를 쭉 쓴 후 모두 선택 후 복붙을 반복해서 얻은 수만큼 진법을 늘리기를 반복해야만 한다. 하지만 그레이엄 수까지는 아직이다, 아직 멀었다.

   (G(3)번 반복) 
             (f(3)번 반복)

이렇게 급격히 증가하며, f(3)부터 이미 계산하거나 표기하기가 곤란해진다. 여기서 라 정의된다. 그러면

 (화살표가 f(4)개, 여기서 지수는 합성 횟수를 뜻한다.)

 (화살표가 f2(4)개)

 (화살표가 f3(4)개)

...

 (화살표가 f62(4)개)

 (화살표가 f63(4)개)

이와 같이 증가하여 로 정의되는 G가 그레이엄 수이다.

결과 
그레이엄 수는 너무 크기 때문에 10진수로 표기하는 것이 불가능하지만, 마지막 500자리의 수는 다음과 같이 알려져 있다.(그리고, 그레이엄 수가 정확히 몇 자리의 수인지도 알려져 있지 않고, 그것을 정확히 알아내는 것도 불가능하다. 위 수학 문제만 해도 실제로 그만한 차원의 도형에 하나씩 선을 그은 것도 아닌데, 아래의 수는 계산 패턴을 통해 알아낸 것.)

  …02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387

수의 규모 
 그레이엄 수를 플랑크 길이의 크기로 인쇄하더라도, 그 수의 전체 길이는 우주의 직경보다 더 크다.
 그레이엄 수를 1초에 구골플렉스 글자씩 빠르게 적더라도, 우주의 나이보다 더 오랜 시간이 필요하다.
 그레이엄 수는 우주에 존재하는 모든 소립자의 개수보다 더 크다.
 그레이엄 수를 지수를 사용해 쓰더라도, 쓸 종이를 우주에 다 구겨넣을 수 없다.
 그레이엄 수 만큼의 모래들이 만약 있다면, 넓디 넓은 모든 우주를 총 동원해도 턱없이 부족하며, 지구상 관측 가능 우주 크기의 9999 나유타×99초과관수 이상의 9를 9999경 면적을 곱해 합쳐도 터무니 없이 부족하다.
 그레이엄 수의 숫자를 수백 항하사 개의 소립자가 들어갈 수 있는 세계에서 가장 작은 크기(기준)인 초극암원 A3원자(超極暗原 A3原子)의 크기로 채워도(써도) 모든 전 우주는 공간이 모자라다.
 그레이엄 수는 구골플렉스보다도 더 크다.

더 보기 
 큰 수
 커누스 윗화살표 표기법
 하이퍼 연산
 아커만 함수
 램지의 정리

참고 문헌 
  The explicit formula for N appears on p. 290. This is not the "Graham's number" G published by Martin Gardner.
 Graham, R. L.; Rothschild, B.L. (1978). "Ramsey Theory", Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80–99.  On p. 90, in stating "the best available estimate" for the solution, the explicit formula for N is repeated from the 1971 paper.
 ; reprinted (revised) in Gardner (2001), cited below.
 
 
  Exoo refers to the Graham & Rothschild upper bound N by the term "Graham's number". This is not the "Graham's number" G published by Martin Gardner.

외부 링크 
 "A Ramsey Problem on Hypercubes" by Geoff Exoo
 Mathworld article on Graham's number
 How to calculate Graham's number
 Some Ramsey results for the n-cube prepublication mentions Graham's number
 

큰 수
정수
램지 이론