64비트로 표현할 수 있는 가장 큰 수: 18,446,744,073,709,551,615가 끝이 아닙니다

우리는 흔히 64비트 정수형(uint64_t)의 한계를 18,446,744,073,709,551,615 ($2^{64}-1$)라고 생각합니다. 16진수로는 0xFFFFFFFFFFFFFFFF죠. 개발자라면 이 숫자를 보고 “아, 오버플로우 조심해야지” 정도의 생각을 할 겁니다.

하지만 만약 관점을 바꿔서, 이 64비트를 단순한 데이터가 아니라 실행 가능한 프로그램 코드 라고 가정한다면 어떨까요? 이 작은 8바이트 공간 안에서 생성해낼 수 있는 ‘가장 큰 수’는 과연 어디까지일까요?

최근 John Tromp가 갱신한 블로그 포스트와 이에 대한 Hacker News의 논쟁은 단순한 숫자 놀음을 넘어, 계산 이론(Computational Theory)과 정보 밀도에 대한 매우 흥미로운 통찰을 줍니다. 오늘은 이 ‘숫자 괴물’들에 대해 이야기해보려 합니다.

데이터가 아니라 ‘프로그램’입니다

단순 데이터 타입으로서의 double은 대략 $1.8 \times 10^{308}$까지 표현 가능합니다. 크긴 하지만, 수학적으로 ‘거대하다’고 말하기엔 귀여운 수준입니다.

진정한 거대 수는 연산(Computation) 에서 나옵니다. 64비트짜리 프로그램을 작성해서 어떤 숫자를 출력하고 종료한다고 가정해봅시다. 가장 먼저 떠오르는 건 리눅스의 bc 같은 계산기나 C 언어입니다. 하지만 C언어의 최소 문법인 main(){}만 해도 이미 8바이트(64비트)를 다 써버립니다. 아무것도 못 하죠.

여기서 우리는 좀 더 원시적이고 강력한 모델인 튜링 머신(Turing Machine) 과 람다 대수(Lambda Calculus) 의 세계로 넘어가야 합니다.

Busy Beaver: 튜링 머신의 한계

전산학 전공 때 졸지 않으셨다면 Busy Beaver(BB) 함수를 들어보셨을 겁니다. $n$개의 상태(state)를 가진 튜링 머신이 멈추기 전까지 테이프에 쓸 수 있는 1의 최대 개수(혹은 스텝 수)를 의미합니다.

64비트 공간에는 6개의 상태를 가진 튜링 머신(BB(6))을 인코딩할 수 있습니다. 현재 알려진 BB(6)의 하한값은 $2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 10$보다 큽니다. 여기서 $\uparrow\uparrow$는 커누스 윗화살표 표기법(Knuth’s up-arrow notation)으로, 거듭제곱의 거듭제곱을 의미합니다. 이미 상상을 초월하는 크기죠.

하지만 저는 개인적으로 튜링 머신을 별로 좋아하지 않습니다. 상태 변환 테이블을 비트로 인코딩하는 과정이 너무 비효율적입니다. “프로그래밍하기에 너무 구식”이라는 느낌을 지울 수 없습니다. 실제로 6-state 튜링 머신보다 훨씬 더 효율적으로 큰 수를 만들어내는 방법이 있습니다.

진정한 승자: 람다 대수 (Lambda Calculus)

함수형 프로그래밍의 조상님, 람다 대수가 여기서 빛을 발합니다. John Tromp는 Binary Lambda Calculus (BLC) 를 사용하여 64비트 안에 들어가는 괴물 같은 람다 항(term)들을 소개합니다.

그레이엄 수(Graham’s Number)는 이제 명함도 못 내밉니다

수학적으로 ‘가장 큰 수’라고 하면 대중적으로 그레이엄 수가 유명합니다. 하지만 람다 대수의 세계에서는 이조차도 가볍게 뛰어넘습니다.

Melo’s Number 라고 불리는 49비트짜리 프로그램이 있습니다:

01 00 01 10 10 00 01 10 01 10 00 00 01 01 10 110 00 00 01 110 01 110 10

이 비트열은 람다 식으로 (λ 1 1) (λ 1 (1 (λ λ 1 2 (λ λ 2 (2 1)))))를 의미합니다. 이 짧은 코드가 그레이엄 수를 압도적으로 초과합니다.

현존 최강: w218 (61비트)

그리고 이 글의 주인공, 64비트 안에 들어가는 현재까지 알려진 가장 큰 수를 생성하는 프로그램 w218 이 등장합니다. 단 61비트입니다.

01 00 01 01 10 10 10 00 01 10 01 10 00 00 00 01 01 01 10 1110 110 00 00 01 110 01 110 10

이 프로그램은 람다 대수의 처치 수(Church numerals)와 함수 합성을 극한으로 활용합니다. 이 숫자의 크기는 대략 $2 \uparrow\uparrow 18$번의 함수 반복 적용을 통해 만들어집니다. FGH(Fast Growing Hierarchy)로 표현하면 $f_{\omega+1}(64)$ 수준인 그레이엄 수보다 훨씬 높은 단계에 있습니다.

솔직히 말해서, 이 정도 크기면 우주의 모든 입자 수는 0에 수렴하는 오차 범위 내에 불과합니다. 인간의 뇌로는 이해가 불가능한 영역이죠.

Hacker News의 반응: “이거 사기 아닙니까?”

이 주제가 Hacker News에 올라왔을 때, 댓글 반응이 아주 뜨거웠습니다. 엔지니어들이라면 누구나 한 번쯤 해봤을 생각들이 쏟아졌죠.

어떤 유저는 “나는 1비트로 가장 큰 수를 표현할 수 있다. 0은 0이고, 1은 무한대(혹은 정의할 수 있는 가장 큰 수 + 1)라고 정의하면 된다” 라고 주장했습니다. 전형적인 ‘정의(definition) 해킹’이죠.

하지만 원작자와 커뮤니티의 반박이 인상적입니다:

“튜링 머신이나 람다 대수가 의미 있는 이유는, 이 모델들이 ‘큰 수를 만들기 위해’ 조작된 것이 아니라, 컴퓨팅의 여명기부터 존재했던 고정된(fixed) 모델 이기 때문이다.”

즉, 게임의 룰을 바꾸지 않고, 주어진 제약(64비트, 표준 람다 대수) 안에서 최적화를 해냈다는 점이 핵심입니다. 엔지니어링의 본질은 제약 조건 속에서의 최적화니까요.

결론: 64비트의 우주

우리가 매일 다루는 long long 변수 하나, 혹은 포인터 하나가 들어가는 64비트 공간. 그곳은 단순히 $2^{64}$가지의 경우의 수를 담는 그릇이 아닙니다. 적절한 해석기(Interpreter)만 있다면, 그 공간은 인간의 인지 능력을 아득히 초월하는 거대한 우주를 담을 수 있습니다.

이 글을 읽고 나면, 메모리 덤프에서 보이는 0x08B50CC02B76073A 같은 16진수 값들이 예전과는 조금 다르게 보일지도 모릅니다. 어쩌면 그 값은, 우주 멸망까지 계산해도 끝나지 않을 거대한 루프의 씨앗일 수도 있으니까요.

References: