1
$\begingroup$

Despite the endless hours of googling, pretty much all of them used an alternative definition of Busy Beaver function. The definition BB(k) I'm interested in is the maximum number of 1's that can be written by k-state before it halts, but the other definition they used was the maximum number of steps, and they're not equivalent.

And one of the techniques they used is by reduction from halting problem, that if there was any computable function f(x) bounding above the function BB(k), you can solve halting problem in a finite amount of time using the alternative definition, but this argument doesn't work for the definition of BB(k) I am interested in. How do we show that BB(k) is asymptotically larger than any computable function f(x)?

$\endgroup$
  • $\begingroup$ To be clear, showing that BB is asymptotically faster growing than any computable function is different than showing that it isn't computable. The proof that you mention for the maximum steps function, as far as I can glean, doesn't show that it is faster growing than any computable function. It does show that it's not computable, however. Do you want to show that BB is faster growing than any computable function or do you want to show that it is not computable? $\endgroup$ – Jake Nov 27 '17 at 5:01
  • $\begingroup$ Sorry if it wasn't clear. I have already sketched a proof that it is not computable, but I want to show that BB is asymptotically faster than any computable function. Also, the argument they used made sense because if f(k) is computable function bounding above BB(k), then to solve the halting problem on input <M,w>, you can run k-state M for f(k) steps, and if it's still running, it's obvious that it's not going to halt, by the alternative definition of BB(k), which contradicts that halting problem is undecidable $\endgroup$ – Ted Nov 27 '17 at 5:07
  • 2
    $\begingroup$ What does "maximum number of 1's that can be written" mean? This seems to depend a lot on the exact model of TMs that you are using. Perhaps you mean some version of "the largest output that a halting TM with $k$ steps can have"? Say with a write-only output tape? $\endgroup$ – Yuval Filmus Nov 27 '17 at 21:26
  • $\begingroup$ @Yuval Filmus The instruction from the textbook says "For each value of k, , consider all k-state TMs that halt when started with a blank tape. Let BB(k) be the maximum number of 1's that remain on the tape among all of these machines" $\endgroup$ – Ted Nov 28 '17 at 1:37
  • $\begingroup$ You should probably update your post with this information. $\endgroup$ – Yuval Filmus Nov 28 '17 at 6:41
1
$\begingroup$

I think a sketch of the proof could be as follows.

First prove BB(k) is uncomputable. Assume it is computable, then it means there is some machine with some number of states m that can compute this value. Show that there exist a larger machine with some number of states M that calls this function on BB(M) and outputs BB(M)+1 1s, and then halts. Therefore there is a contradiction since it outputed more 1s than predicted by BB(M). It's easy to see M = m + C for some constant.

Now regarding the growth.

Assume G(k+1) >= BB(k+1) - BB(k) is computable for k >= K0.

Now, if the above is true then there must exist a machine with m states that computes G(k).

And there must also exist a machine, with a larger number of states M, that guesses BB(K0) and then computes UBB(M) = sum(K0..M)G(k) + BB(k0) and output UBB(M)+1 1s.

So this machine outputs more 1s than our assumed computable upper bound.

Therefore G(k) can not be computed for any K0.

$\endgroup$

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.