The largest number representable in 64 bits
2 days ago
- #large-numbers
- #busy-beaver
- #lambda-calculus
- The largest number representable in 64 bits is explored, starting with the maximum value of a 64-bit unsigned integer (18446744073709551615).
- Floating-point data types can represent much larger values due to their base 2 exponent, with the largest finite 64-bit double being approximately 1.8*10^308.
- The concept of representing numbers beyond plain data types is introduced, considering computable representations via small programs in programming languages.
- The smallest valid C program is "main(){}", which fits in 64 bits but does nothing. Other languages like 'bc' can compute much larger numbers within 8 bytes.
- The Busy Beaver function (BB(n)) is introduced as a measure of the largest number computable by an n-state Turing Machine before halting, with BB(6) being the largest number programmable in 64 bits for TMs.
- The exact value of BB(6) is unknown, but it is known to be greater than a very large number represented using Knuth's up-arrow notation.
- Lambda calculus is presented as a more efficient way to represent large numbers, with a 49-bit program (Melo) exceeding Graham's Number.
- A 61-bit lambda calculus term (w218) is shown to vastly exceed Melo's Number, leveraging the Fast-growing hierarchy for comparison.
- The functional Busy Beaver function (BBλ) is introduced, which measures the maximum beta normal form size of any closed lambda term of size n, with known values up to BBλ(36).
- BBλ is compared to the traditional Busy Beaver function (BB), showing that BBλ achieves comparable growth with fewer bits due to better programmability.
- A universal Busy Beaver function (BBλ2) is proposed, which includes self-delimiting BLC programs and achieves universality by allowing lambda terms access to pure binary data.
- The largest number currently known to be representable in 64 bits is w218, which lower bounds both BBλ(61) and BBλ2(63).