람다 계산법 : 64비트 최댓값? 타입 말고 ‘프로그램’으로 보자

혹시 “64비트로 표현할 수 있는 가장 큰 수” 하면 바로 2^64 - 1(= 0xFFFFFFFFFFFFFFFF)부터 떠올리시나요?
그런데 “숫자 타입”이 아니라 “64비트짜리 프로그램”까지 허용하면, 이야기가 완전히 달라져요.

64비트의 상식: uint64_t 최대값 vs double 최대값

일반적으로 64비트에서 최댓값은 부호 없는 정수(unsinged integer) 기준 **2^64 - 1**이에요. C라면 uint64_t, Rust라면 u64로 다루는 바로 그 범위죠. 그래서 값으로는 18,446,744,073,709,551,615가 끝처럼 보이기도 해요.

하지만 **부동소수점(floating point, 지수부로 범위를 늘리는 표현)**을 꺼내면 훨씬 커져요. 예를 들어 64비트 double은 지수(exponent) 덕분에 **약 1.8 * 10^308**까지(유한한 값으로) 표현 가능해요. 즉 “64비트”라고 해서 항상 같은 크기의 수만 다룰 수 있는 건 아니고, 표현 방식이 무엇인지가 핵심이 되는 거예요.

여기서 한 발 더 나가면 이런 질문이 생겨요. “그럼 64비트에 담긴 ‘데이터’가 아니라, 64비트로 된 ‘프로그램’이 계산해서 출력하는 수는 어디까지 커질 수 있을까?” 한번 살펴볼까요?

64비트로 ‘프로그램’까지 허용하면: 8바이트로도 초거대 수가 나와요

글의 관점은 이거예요. “표현(represent)”을 단순 숫자 리터럴이 아니라 ‘계산 가능한 형태(=프로그램)’로 확장하자는 거죠. 단, 조건이 있어요. 프로그램 자체가 64비트(8바이트) 안에 들어가야 해요.

C는 여기서 좀 불리해요. 가장 작은 유효 C 프로그램이 "main(){}"인데 ASCII 문자 8개라서 딱 64비트를 꽉 채우거든요. 사실상 64비트로는 “아무것도 안 하는 프로그램”만 가능하다는 해석이 나와요.

반면 bc 같은 계산기 언어는 훨씬 유리해요. 예를 들어 9^999999 같은 표현은 몇 바이트로 끝나는데 결과는 954,242자리 정수예요. 더 나아가 9^9^9^99처럼 지수탑 형태는 자리수 자체가 상상을 벗어나죠(물론 계산은 현실적으로 어렵고요). 이런 걸 보면 “내장 연산이 많은 언어는 반칙 아닌가?”라는 의문도 자연스럽게 나와요. 예컨대 언어에 **아커만 함수(Ackermann function, 극단적으로 빠르게 증가하는 함수)**가 내장돼 있으면 ack(9,9) 같은 8바이트 표현이 말도 안 되게 큰 수를 의미할 테니까요.

그런데 흥미롭게도, 원문은 “아커만 내장 같은 건 중요하지 않다”고 말해요. 내장 프리미티브 없이도(심지어 숫자 자체 없이도) 64비트로 아커만 따위는 훨씬 넘어설 수 있다는 거예요.

Busy Beaver와 튜링 머신: 64비트로는 BB(6)이 한계선

여기서 유명한 **Busy Beaver 함수(BB, n상태 튜링머신이 멈추기 전까지의 최대 스텝 수)**가 등장해요. 개념은 단순하지만 값이 미친 듯이 커져서, 계산/증명이 거의 불가능한 영역으로 가요.

다만 중요한 현실적인 포인트가 있어요. Busy Beaver는 “n상태”로 크기를 재는데, 우리는 “비트 수”로 프로그램 크기를 재잖아요. 그래서 원문은 튜링 머신을 비트로 인코딩하는 방식을 설명해요. 상태 n에서, 테이프 심볼 2개 각각에 대해 “쓸 값(1비트) + 이동방향(1비트) + 다음 상태(약 ceil(log2(n+1))비트)”를 기록하는 식이죠.

그 결과가 인상적이에요.

• 6-state TM은 약 60비트로 인코딩 가능
• 7-state TM은 약 70비트 필요

즉, 64비트 안에 들어가는 최강 튜링머신은 6-state 정도로 보고, 결론적으로 “64비트로 프로그래밍 가능한 가장 큰 Busy Beaver 수”는 **BB(6)**이 돼요.

문제는 BB(6)의 정확한 값은 모른다는 점이에요. 현재 챔피언 결과로 BB(6) > 2↑↑2↑↑2↑↑10 같은 하한만 알려져 있죠(↑↑는 크누스 업애로우 표기법, 거대한 지수탑을 뜻해요). 그리고 7-state로 가면 BB(7)은 이미 ack(9,9)보다 크다고 알려져요.

λ-계산법(lambda calculus): 64비트에서 그레이엄 수를 ‘가볍게’ 넘어요

원문에서 가장 재밌는 전환은 여기예요. 튜링 머신보다 더 “날것”처럼 보이는 **λ-계산법(λ-calculus, 함수 적용/치환만으로 계산을 표현하는 모델)**로 가면, 오히려 초거대 수를 더 “효율적으로” 만든다는 거죠.

특히 Code Golf(최단 코드 경쟁)에서 나온 49비트짜리 Binary Lambda Calculus 프로그램이 소개돼요. 이 프로그램은 결국 **그레이엄 수(Graham’s Number, 유명한 초거대 수)**를 넘는 크기의 처치 수(Church numeral, λ-계산법에서 숫자를 함수 반복으로 표현)를 계산해요. 원문에서는 이를 발견자 이름을 따서 **Melo**라고 부르고, 결과물을 “Melo’s Number”라고 해요.

여기서 핵심 메시지는 이거예요.

• 튜링 머신으로 그레이엄 수급을 넘기려면 상태 수가 커지고 인코딩 비트도 많이 든다
• 그런데 λ-계산법 쪽은 49비트로 이미 그걸 해낸다
• 즉 **같은 ‘비트 예산’에서 λ-계산법이 훨씬 프로그래머블(programmable)**하다는 해석이 붙어요

이 관점은 실무에도 은근히 연결돼요. “표현력이 높은 추상(고수준 모델)”이 같은 크기 제약에서 더 강력한 결과를 만든다는 이야기니까요.

결론: 64비트로 현재 “가장 크게” 알려진 것은 w218(61비트 λ-텀)

마지막은 한 단계 더 나가요. 49비트 Melo를 “먼지로 만들어버리는” 61비트짜리 λ-텀이 등장합니다. Discord 유저들이 찾은 **w218**이라는 항인데, 이게 만들어내는 값은 원문 기준으로 **BBλ(61)과 BBλ2(63)에 대한 강력한 하한(lower bound)**이 돼요. (여기서 **BBλ(n)**은 “n비트 크기의 닫힌 λ-텀이 만들 수 있는 최대 베타 정규형 크기”를 의미해요.)

원문의 최종 결론은 명확해요.
현재 알려진 범위에서, 64비트로 ‘표현 가능하다’고 할 수 있는 가장 큰 수는 w218이 만들어내는 값이라는 거예요. 단순히 2^64-1 같은 타입 한계를 말하는 게 아니라, “64비트짜리 계산 가능한 기술(프로그램)”의 관점으로요.

마무리: “비트 수”보다 중요한 건 표현 모델이에요

정리해보면, 64비트의 한계는 숫자 타입에서 끝나지 않아요. 무엇을 ‘표현’이라고 볼지를 바꾸는 순간, 8바이트는 그냥 숫자 저장 공간이 아니라 “초거대 수를 정의하는 압축된 설명”이 돼요.

여러분이라면 “64비트로 표현 가능한 최댓값”을 어떤 모델로 정의하고 싶으신가요? 정수 타입, 튜링 머신, λ-계산법… 기준이 바뀌면 결론도 완전히 달라져요.