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)?

Improve this question
$\endgroup$
6
  • $\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
    Commented Nov 27, 2017 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
    Commented Nov 27, 2017 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
    Commented Nov 27, 2017 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
    Commented Nov 28, 2017 at 1:37
  • $\begingroup$ You should probably update your post with this information. $\endgroup$
    – Yuval Filmus
    Commented Nov 28, 2017 at 6:41

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
$\begingroup$

Suppose you have a computable function that dominates the busy beaver function. Then you immediately get that the busy beaver function is computable: given a machine of n states, simply run the machine for f(n) cycles, where f is your dominating computable function. If it quits note that number of cycles. If it does not stop in f(n) cycles then it never will. Take the max over all n state machines. You have computed B(n).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I was thinking that the Busy Beaver function was the maximum number of cycles for a halting machine of n states $\endgroup$
    – George R Blanton Jr
    Commented May 13, 2023 at 22:49
  • $\begingroup$ I have a related question: The busy beaver function has been computed for some small numbers of states n. The whole function is not computable. Does that mean there is some n such that just that one B(n) is not computable? $\endgroup$
    – George R Blanton Jr
    Commented May 13, 2023 at 23:03

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.