How to argue that if we could solve the halting problem, then we could solve busy beaver?

Question

This is one of the tasks of my assignment. I have a Turing machine simulation which can simulate a busy beaver function. I have done some research about proving this problem, but still don't get it so I guess maybe you can help me here. A good source for me to go to or example of how to argue this would be good.

Answer 1

The BB function is defined to be the maximum number of steps a Turing machine of a particular size can carry out and still halt. (Another way of putting it is that all Turing machines of size x will either halt in less than BB(x) steps, or run forever).

Assuming you have a Turing machine of complexity x, then you could determine whether it would halt or not by letting it run for BB(x) time-steps - if it hadn't halted by then, then by definition it never will.

Equally, if you could solve the halting problem, you could evaluate all possible Turing machines of size x, eliminate those that don't halt, and take BB(x) to be the maximum of the run times of the remainders.

Of course, BB(x) is non-computable - and in fact grows faster than any possible computable function you could name - hence it cannot even be approximated.

Answer 2

You can find the proof you seek here, below the proof that the Busy Beaver problem is uncomputable.