The largest number representable in 64 bits

Most people believe 9,223,372,036,854,775,807, or 0xFFFFFFFFFFFFFFFF in hexadecimal, to be the largest number representable in 64 bits. Which is indeed the case if we are talking about 64 bit unsigned integers such as represented by the datatype uint64_t in C or u64 in Rust. We can reach quite a bit further with floating point values. The 64-bit double floating point format finds its largest representable value in the 309 digit number 2^1023*(2^53-1)/2^52 = 17976931...24858368.

What if we allow representations beyond mere datatypes? Such as a program small enough to fit in 64 bits. For most programming languages, there is very little you can do in so few bits. 64 bits is only 8 characters or bytes after all.

In the C language that only leaves you with "main(){}", which doesn't do much. But there are plenty languages that require no such scaffolding. For instance, on Linux there is bc, an arbitrary precision calculator language. It happily computes the 954242 digit number 9^999999 = 35908462...48888889, which can thus be said to be representable in 64 bits. We can imagine a similar language featuring the symbol ! for computing factorials, which makes 9!!!!!!! a much larger number representable in 64 bits.

Allowing such primitives feels a bit like cheating though. Would we allow a language that has the Ackerman function predefined, which sports the 8 byte expression ack(9,9) representing a truly huge number?

As it turns out, the question is moot. There is a very simple language with no built in primitives of any kind. Not even primitives for arithmetic. Not even numbers themselves. A language in which all those must be defined from scratch. And yet, a carefully optimized 63 bit program in this language represents a number unfathomably larger than even ack(9,9). Its discovery can be credited to Code Golf users Patcail and 2014MELO03, who came up with the best answer to a Code Golf challenge asking for the "Shortest terminating program whose output size exceeds Graham's number".

This is the program: 010001010110010110000000010101101110110101010100000011100111010

It's the Binary Lambda Calculus encoding of term (λ 1 (1 (λ λ λ 1 3 2 1) 1) 1 1) (λ λ 2 (2 1)), where λ (lambda) denotes an anonymous function, and number i is the variable bound by the i-th nested λ. This is known as De Bruijn notation, a way to avoid naming variables. A more conventional notation using variable names would be

(λt. t (t (λh λf λn. n h f n) t) t t) (λf λx, f (f x))

The last 16 bits of the program---making up more than a quarter of its size---encodes the term λf λx. f (f x), which takes arguments f and x in turn, and iterates f twice on x. This is the standard way of representing numbers in lambda calculus, known as Church numerals. Church numeral n iterates a given function n times on a given argument.

The whole program can be read as let 2 = Church_Numeral_2 in 2 (2 H 2) 2 2, where H equals λh λf λn. n h f n.

In a later section we will prove that this program computes a number beyond Graham's.

Busy Beavers

The program is an excellent example of a so-called Busy Beaver: a program that computes the maximum possible value within some program size constraint. Historically, Turing Machines were the computational model of choice for studying Busy Beavers. I recently proposed a λ-calculus based alternative that, besides greater simplicity, has the advantage of measuring program size in bits rather than the less comparable notion of Turing Machine states. An n-state Turing Machine of the kind used in the traditional busy beaver function requires n*2*(2+⌈log2(n+1)⌉) bits to specify in straightforward manner. So our 63 bit program is more concise than even a hypothetical 7-state Turing Machine whose output exceeds Graham's Number, as that takes 7*2*(2+log2(7+1)) = 70 bits to describe. The current best effort at such a large output however, after many rounds of optimization, is stuck at 16 states, weighing in at over 16*2*(2+4) = 192 bits.

Proof of exceeding Graham's Number

It assumes some familiarity with the Fast-growing hierarchy. We'll treat all numbers as Church Numerals, so we can write n f instead of the usual fn and write f n instead of f(n) as normally done in lambda calculus.

Definitions:

• H h f n = n h f n
• H2 = H 2
• 2H2 = 2 H 2 = H (H 2) = H H2

Lemmas, all assuming n >= 2:

1. For all ordinals α: H2 fα n = n 2 fα n = 2n fα n > n fα n = fα+1 n
2. Proof by Induction that for all i: i 2H2 2 n > fω*i n
   1. Case i=0: 0 2H2 2 n = 2 n = n2 > n+1 = f0 n
   2. Case i+1: (i+1) 2H2 2 n = H H2 (i 2H2 2) n = n H2 (i 2H2 2) n >(by Induction) n H2 fω*i n >(by Lemma 1) fω*i+n n = fω*i+ω n = fω*(i+1) n

Lemma 2 with i=n=2 proves that the Program = 2 2H2 2 2 > fω*2 2 = fω+2 2 = 2 fω+1 2 = fω+1 (fω+1 2) = fω+1 (2 fω 2) = fω+1 (fω (fω 2)) = fω+1 (fω (f2 2)) = fω+1 (fω 8) = fω+1 (f8 8). In comparison, Graham's number is known to be less than the much smaller fω+1 64.