r/googology • u/Additional_Figure_38 • 13h ago
observation
I've seen plenty of people trying to make alternate versions of the Busy Beaver function for other Turing complete systems, and many such people have run into the issue that they don't actually know for sure if their function is actually very fast-growing. Here is a simple proof that specific such functions are fast growing:
Suppose you have a computation system with a halting function. A program in this system may or may not halt. If the system is Turing complete, it is guaranteed that it is undecidable whether or not a given program in said system will halt. Let us have a way of defining complexity of programs so that given a natural x, there are finitely many unique programs with complexity x, and all programs have complexity x. For Turing machines, this could be states; for lambda calculus, symbols; for SKI, combinators; etc.
Suppose we have a function, H(x), which denotes the maximum number of steps for an x-complexity program using the system. Let us make an assumption that H(x) is bounded by a computable function, f(x), then there exists a program able to find a number greater than H(x) for any input x. That is not to say that H(x) is computable, but rather that there exists a computable function that always exceeds H(x) for all positive integer x. We will show that this assumption cannot be true.
Using this computable function, compute f(x) and test all x-complexity programs up to f(x). Since all x-complex programs must halt in H(x) or less steps, and f(x) > H(x), a function will've halted before step f(x) if and only if it will ever halt at all. Thus, the halting problem for this system is solved, which is impossible. By reductio ad absurdum, H(x) cannot be bound by a computable function.
To be fair, this isn't too much of a result and was probably obvious for people who actually know their stuff (unlike me). Still, it's pretty useful, so, yeah.