I learned that the busy beaver function grows very rapidely indeed.
The first 4 values are known.
I would like to know if there is any UPPER bound known for
$$\Sigma(n)$$
for some $n\ge 5$.
Additionally, how likely is it that $\Sigma(5) = 4098$ ?
And how big is $\Sigma(6)$ believed to be ?
On
There is an uncomputable upper bound for Σ(n), namely Σ(n+1). Σ(n) grows faster than any computable function - if it didn't, we could compute it as many other answers have noted. That is equivalent to saying that Σ(n) is not bounded by a computable function.
Interestingly, is there any uncomputable upper bound f(n) for Σ(n) such that f(n) < Σ(n+1) for all n? Trivially: f(n) = Σ(n+1)-1 works. What about f'(n) = Σ(n+1) - g(n) where is g(n) is any computable function? Note that f'(n) still grows faster than any computable function: Suppose f'(n) is bounded by a computable function h(n) (to show a contradiction). Then Σ(n+1) is bounded by j(n) = h(n)+g(n), which is computable by supposition. Σ(n) is bounded by Σ(n+1). Therefore Σ(n) is bounded by a computable function, a contradiction: the supposition is false.
This does not prove that f'(n) bounds Σ(n). That question reformulated intuitively is to ask: Σ(n) grows so fast, could I stick the output of any computable function between Σ(n) and Σ(n+1) from some large n going up? Or is the difference Σ(n+1)-Σ(n) bounded by a computable function? Well, suppose k is a computable function such that k(n) > Σ(n+1)-Σ(n) for sufficiently large n (to show that k is not computable). (Also suppose that k is an increasing function, which can be done without loss of generality because there is always a computable, increasing function that bounds a computable function).
Consider the function z(n) = k(n)+k(n-1)+k(n-2)+...+k(n-n), which is computable if k is computable. Show that z(n) bounds Σ(n), by induction. Base: z(0) = k(0). k(0) > Σ(1)-Σ(0) or k(0)> 1. 1>Σ(0), so z(0)>Σ(0).
Therefore by induction z(n)>Σ(n). But Σ(n) cannot have a computable upper bound. Therefore our supposition that there is a computable function k that bounds the difference of consecutive busy beaver function outputs is false. Therefore, Σ(n+1)-g(n) for any computable functions g(n), is an upper bound to Σ(n).
Now what about a bound on Σ(n) from some point on? In other words, what if the base of induction does not hold, but for all n>m>0 k(n)>Σ(n+1)-Σ(n)? In that case, define l(n) = {k(n) for n>m; k(m) otherwise}. l(n) is computable if k(n) is, and the induction holds, implying that l(n) would bound Σ(n+1)-Σ(n) for all n. Therefore, no such k can be computable.
Let's get philosophical. What is an upper bound on the busy beaver function? It would essentially amount to determining the relationship between the number of states of the Turing machine and the minimum finite tape required to execute every machine that halts. Obviously that would solve the halting problem. Even machines that never halt but only visit a finite amount of tape could be solved by extending such machines so that they concatenate the pieces of tape visited by the smaller version of the machine. This machine then would never halt and would blow through any finite amount of tape, and when they exceed the bound placed on the amount of tape for the larger machine, the smaller machine would be known to never halt. This is not dependent on Turing's thesis because such a Turing machine exists.
As result, if we assume Turing's thesis, there is no meaningful way to describe the rate at which the busy beaver function grows. That is because for any computable function, one could describe a computable function that grows faster than it by composition: g(n) = f(f(n)) always grows faster than f, when f is an increasing function. h(n) = g(g(n)), and so on. So even if you say that Σ grows faster than f, that doesn't mean much because (infinitely) many computable functions grow faster than f, but not as fast as Σ. In that sense, f does not tell me anything meaningful about Σ.
Interestingly with computable growth rates of functions, if you graph the function with a scale on the x axis such that the space between natural numbers increases at the same rate as the function, the graph of that function will appear linear. This cannot be done with Σ. If you write out any scale for the x axis, at some point on that graph, Σ(n) (on the y-axis) will be rising faster than any computable function. Now that’s fast! Is that infinitely fast? Even if you compress the scale on the y-axis by some computable function, and expand the scale of the x-axis by some computable function, at some point on that graph Σ will be (almost) vertical.
There is no computable upper bound on the busy beaver function, so don't expect there to be any nice form for an upper bound to it. In particular, if there were a computable an upper bound, then we could solve the Halting problem - if we run a machine for a number of steps until it passes the relevant upper bound, we know it does not halt. Therefore, such a number cannot be computed - and it should be noted that this implies, in theory (but so far from practice!) that knowing an upper bound allows us to calculate the actual value, since we can weed out, in finite time, the machines that do not halt.
There is this page seems to have a list of all the difficult cases in finding that value of $\Sigma(5)$ - I would presume that someone, sometime tried running them all for a long period of time, and they did not halt, which might suggest that they do not halt, but speculation might not be wise since, "Well, I doubt the busy beaver is that big" is not a good heuristic. According to Wikipedia, $\Sigma(6)$ is known to be at least $3.5\times 10^{18267}$, which is already a lot, and not necessarily close to the actual value.