# How can we tell a busy beaver candidate can halt?

If the BB function is computable, does that mean we know how to compute {i | program i eventually halts when run with input 0}, which is a clear contradiction with halting problem.

Does this proof work? Am I missing anything?

Thanks

• This is an interesting counter-factual, but let's just agree that the BB function is not computable. – Pål GD Nov 23 '20 at 8:15
• Isn't that pretty much how we can know BB is not computable? – kutschkem Nov 23 '20 at 8:59
• "Does this proof work?" Which proof do you mean? You don’t present any. – idmean Nov 23 '20 at 9:37
• Let me simplify @PålGD eloquent comment: BB is not computable. – Andrej Bauer Nov 23 '20 at 9:46
• @idmean I mean if we can't even decide whether a BB candidate is going to halt, then of course BB is not computable. This seems to be a more straightforward proof than the proofs I see in other places, but I don't know if I am missing anything. – user1792389 Nov 23 '20 at 16:08

You ask "If the BB function is computable [...]", well, the Busy Beaver function is not computable, if by BB function you mean given a size $$s$$ find $$BB(s)$$.
Now, some terminology: Busy beaver is a game where you want to find, given an integer $$n$$, the Turing machine $$BB(n)$$ that has
1. $$n$$ states (plus an additional halting state)
3. produces the maximum number of 1s on the tape of all halting $$n$$-state Turing machines.