Is the busy beaver function in computer science a provably total function? That is, can it be proven that for all natural numbers n, Σ(n) is a natural number?
Basically, you are dealing with Turing machines with n states (where n is a natural number), so there is only a finite number of them. No problem to define the function, though it is uncomputable, it’s impossible to obtain its values, and so on.
ETA I mean Σ(12345) will be a number, but you might not be able to prove it equals a given value.
(A formula like that may be true, but it will be impossible to prove it, meaning formally, not just because your computer is too slow. Unless set theory is inconsistent or something.)
I don’t quite follow. The set of natural numbers is infinite…how do you get to a finite number of states when they map to an infinite set?
The Busy Beaver Function I know, and that is described in the OP’s link, takes as an argument the number of states. Say it is n. Then you can specify a Turing machine with a finite amount of data: for each state and input symbol you specify the next state (or halt), the symbol to write (0 or 1), and the direction to move. So there are only a finite number of possibilities, for each n.
Therefore there is a function defined as the maximum number of 1’s on the tape after halting. So there are infinitely many values: BB(1), BB(2), BB(3),… but each one is a finite number.
The interesting part is that this number quickly gets so big you can’t compute it or prove an upper bound for it. So it’s not like f(n) = n[sup]2[/sup] which grows ever larger, even though both are functions from the natural numbers to the natural numbers.
No.
In that case I’m sure you will have no trouble demonstrating how to find n, and a sequence of halting Turing machines with n states that produce ever larger and larger amounts of 1’s
Basically this. Total, and (in my eyes) easily seen to be.
Look at all Tms with n states running on an empty tape. Some halt, some don’t. Ignore the latter. Of the ones that halt, take the one that runs the longest. Its time gives you BB(n).
Clearly, for all n there is at least one Tm with n states that halts. For example, one that just halts immediately. (Even the case of n=1 has this.) So BB(n) is a finite value of at least one.
So, it’s well defined, total, etc. Just not computable.
Note that just because we don’t know the value of a function everywhere, doesn’t mean it can’t be total. E.g., for all natural numbers, let
G(n) = 0 if n is 2, odd, or the sum of two primes. Else it equals 1.
G(n) is total. We just don’t know if it’s 0 everywhere.
Glitch
A quick web search finds this page linking to explicit Turing machines that halt if and only if Goldbach’s conjecture is false; if and only if Riemann’s hypothesis is false; if and only if ZFC is inconsistent.
For those who, like me, wonder how a Hypothesis involving infinite sum of continuous functions can be solved with integer programming, the first formula at this webpage, i.e.
\forall n > 0 \ . \ \left(\sum_{k \leq \delta(n)}\frac{1}{k} - \frac{n^2}{2} \right)^2 < 36 n^3
is allegedly equivalent to RH! (Proofs of this equivalence are mostly behind login-walls — not that I would understand the proof anyway. :eek: )