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?


  • 2
    $\begingroup$ This is an interesting counter-factual, but let's just agree that the BB function is not computable. $\endgroup$ – Pål GD Nov 23 '20 at 8:15
  • $\begingroup$ Isn't that pretty much how we can know BB is not computable? $\endgroup$ – kutschkem Nov 23 '20 at 8:59
  • $\begingroup$ "Does this proof work?" Which proof do you mean? You don’t present any. $\endgroup$ – idmean Nov 23 '20 at 9:37
  • $\begingroup$ Let me simplify @PålGD eloquent comment: BB is not computable. $\endgroup$ – Andrej Bauer Nov 23 '20 at 9:46
  • $\begingroup$ @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. $\endgroup$ – user1792389 Nov 23 '20 at 16:08

Since the question has yet to receive an answer, I'll add this comment as an answer for future visitors.

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)
  2. is guaranteed to halt provided that the tape is clean when it starts
  3. produces the maximum number of 1s on the tape of all halting $n$-state Turing machines.

Now, as you correctly guessed,

Determining whether an arbitrary Turing machine is a busy beaver is undecidable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.