The Largest Computable Number: From Busy Beavers to Loader's Number

Introduction to Large Numbers

The quest for the largest computable number has been a fascinating journey in the world of mathematics and computer science. Since the last exploration of the biggest number that can fit in a text message, even larger numbers have been discovered. This article delves into the intricacies of these massive numbers, addressing common questions and misconceptions along the way.

Busy Beavers and Uncomputable Functions

Many readers have inquired about Busy Beavers and similar functions like Rayo's number. The Busy Beaver function defines a number based on the largest value obtainable using a limited number of symbols or states. There's even a Lambda Busy Beaver function for binary Lambda calculus.

However, these functions are uncomputable. They declare that a number exists, but there's no way to know its exact size or how to produce it. This makes it challenging to consider them as actual numbers; they're more like placeholders for numbers yet to be discovered.

Proving a number is a Busy Beaver is extremely difficult. For instance, the five-state Turing machine Busy Beaver was only proven in 2024, and it's unlikely that a six-state Busy Beaver will be proven in our lifetime.

Understanding Number Classes

A common suggestion is to take the largest known number and add one or square it. While this technically makes the number larger, it doesn't create a larger number class. For example, using only up-arrow notations, no matter how you arrange or repeat them, you won't reach a number from a higher number class.

When discussing the "biggest number," we're referring to the biggest class of number. This concept can be confusing as it's not a scale we're accustomed to thinking in.

Nuclear Array Notation and the Hydra Game

The Buck Hole's ordinal function, which we explored previously, compresses well due to a simple and elegant algorithm using nuclear array notation. This algorithm plays out like a Hydra game.

Imagine you're Hercules, tasked with defeating a Hydra. This Hydra is restricted to binary trees, where each node is either a head or a two-way split. There are two rules for cutting heads:

1. If the left branch is a single head, you can chop it, causing the right side to become the new root.
2. If the left branch is a tree, you recursively play the Hydra game on the left node. When you get the result, you search for instances of the right branch and replace them all with a copy of the entire tree.

Surprisingly, any Hydra formed this way can always be defeated in a finite number of steps. A Hydra that's n heads tall grows at the rate of the Buck Hole's ordinal function, which is significantly faster than the tree function.

Bashu Matrix System (BMS)

The newest largest number comes from the Bashu Matrix System (BMS). This powerful notation is more complex to explain and program due to its additional reduction rules. Pat Kale managed to fit it in under 52 bytes of Binary Lambda Calculus (BLC), which is even smaller than the previously discussed Buck Hole's ordinal function.

The growth rate of BMS varies based on the number of rows:

• A single row (Primitive Sequence System) has a growth rate of Epsilon knot.
• Two rows (Pair Sequence System) has a growth rate equivalent to the Buck Hole's ordinal.
• Three or more rows require a different system to represent larger ordinals, called Proof Theoretic Ordinals (PTOs).

Proof Theoretic Ordinals (PTOs)

Proof Theoretic Ordinals represent the strength of different proof systems. Each proof system, based on its starting axioms and deduction rules, corresponds to a specific ordinal. The PTO can be thought of as the limit for the largest level of recursion you can use to prove statements in that system.

For example:

• Peano arithmetic (first-order arithmetic) has the PTO of Epsilon knot.
• The Buck Hole's ordinal is the PTO for a strong subset of second-order arithmetic.
• Diagonalizing BMS is proven to be larger than the Buck Hole's ordinal but less than or equal to full second-order arithmetic.

Loader's Number

An even larger number that was recently ported to Lambda calculus is Loader's number. To understand this, we need to look at different proof systems:

1. Second-order arithmetic has the same PTO as System F (typed Lambda calculus).
2. Beyond that is System F Omega, where types can have types recursively.
3. Further still is the Calculus of Constructions, which has the property of being strongly normalizing.

The Calculus of Constructions guarantees that all programs terminate, allowing us to iterate over all possible programs of a given length and sum their run times. This results in a truly massive number, which isn't possible in regular Lambda calculus due to the halting problem.

The Current Largest Computable Number

John Tromp optimized Loader's number and created a number that exceeds it in just 233 bytes. While this doesn't fit into a text message, it does fit into a tweet using Unicode characters.

As of now, this represents the largest computable number class proven so far. While there are larger proof-theoretic ordinals for systems like ZFC and some fast-growing functions like greedy click sequences that claim to reach that growth, none of these have been rigorously proven yet.

Conclusion

The journey to find the largest computable number has led us through fascinating mathematical concepts, from Busy Beavers to Proof Theoretic Ordinals and beyond. While we've reached the current limit of proven large number classes, the field remains open for new breakthroughs and discoveries.

As we continue to push the boundaries of mathematics and computation, who knows what new frontiers of large numbers we might uncover in the future? The quest for the largest computable number serves not only as an intellectual challenge but also as a testament to the boundless nature of human curiosity and the ever-expanding horizons of mathematical knowledge.

Further Exploration

For those interested in delving deeper into the world of large numbers and mathematical thinking, there are numerous resources available. Online platforms like Brilliant offer comprehensive courses on topics such as infinities, which can help build a stronger foundation in mathematical reasoning.

Remember, the journey to understand these concepts is ongoing, and even experts in the field are continually learning and discovering new aspects of these mathematical marvels. Whether you're a seasoned mathematician or a curious beginner, the world of large numbers offers endless fascination and opportunities for intellectual growth.

Article created from: https://youtu.be/kQLcoSuMKHg?si=CulsHrPxjrdaz2De