-1
$\begingroup$

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

$\endgroup$
5
  • 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, 2020 at 8:15
  • $\begingroup$ Isn't that pretty much how we can know BB is not computable? $\endgroup$
    – kutschkem
    Nov 23, 2020 at 8:59
  • $\begingroup$ "Does this proof work?" Which proof do you mean? You don’t present any. $\endgroup$
    – idmean
    Nov 23, 2020 at 9:37
  • $\begingroup$ Let me simplify @PålGD eloquent comment: BB is not computable. $\endgroup$ Nov 23, 2020 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$ Nov 23, 2020 at 16:08

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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