The largest number representable in 64 bits
How large a number can truly be represented with just 64 bits depends less on hardware limits than on how those bits are interpreted. Commenters contrast fixed numeric formats like integers and IEEE 754 floats with schemes that encode entire lambda-calculus programs or Turing machines, allowing 64 bits to denote unimaginably huge values (e.g., via Busy Beaver–style constructions) but at the cost of arbitrariness, uncomputability, and unusable arithmetic. Much of the debate centers on what constraints are needed to avoid “cheating” encodings and whether models like lambda calculus provide a sufficiently natural, non-trivial basis for defining such maximal numbers.
Arbitrariness of 64‑bit Encodings
- Several comments argue that any 64‑bit string can denote any chosen set of 2⁶⁴ values; without constraints, “largest representable number” is ill-posed.
- Others counter that this is pedantic: the interesting version asks for the largest non‑trivial number under a fixed, pre‑existing interpretation.
Lambda Calculus, Busy Beaver, and Kolmogorov Complexity
- The thread agrees the article effectively uses lambda calculus as a compact, “natural” description language and then asks for the largest number describable in 64 bits of that language.
- This is tied to Busy Beaver–style growth: encoding a program (e.g., a lambda term) whose output number grows faster than standard large-number notations.
- Some note this connects to Kolmogorov complexity / shortest descriptions, where different universal formalisms differ only by constant factors.
How “Arbitrary” is Binary Lambda Calculus?
- One side: lambda calculus is among the least arbitrary computation formalisms; its encodings are thus meaningful baselines.
- Other side: specific binary encodings (de Bruijn indices, unary coding, self‑delimiting format) still involve design choices, so are not uniquely canonical.
- Supporters respond that these choices are minimal, bit-efficient, and closely aligned with the language’s semantics.
Computable vs Uncomputable Numbers
- Clarifications: every finite integer is computable; most real numbers are not.
- Discussion centers on Busy Beaver values (integers, but the function is uncomputable) and Chaitin’s constant (a canonical uncomputable real).
- There is back-and-forth on whether “knowing” a value via an oracle would make it computable; consensus: no, uncomputability is about the existence of an algorithm, not hypothetical oracular knowledge.
“Cheating” with Custom Number Systems
- Some propose trivial 64‑bit schemes where, for example, the bit pattern “1” means “an enormous named number” or “run the algorithm from the article.”
- Others label this “cheating”: you’re effectively baking the answer into the interpreter rather than deriving it from a fixed, general formalism.
- A recurring suggested constraint: the representation scheme must predate the specific contest, and the interpreter must not contain hard‑coded knowledge of the huge number.
Other Numeric Systems and Infinity
- IEEE754 doubles, infinity, posits, and unums are mentioned, but their ranges are noted as tiny compared to lambda‑calculus‑encoded Busy Beaver–style numbers.
- Some suggest counting infinite cardinals (alephs), but the original focus is clarified to be finite numbers only.