Other people have mentioned this already, but halting for Turing machines is essentially exactly the same for undecidability as busy beaver numbers. Here is a

Other people have mentioned this already, but halting for Turing machines is essentially exactly the same for undecidability as busy beaver numbers. Here is a quick sketch of a proof: Assume we have a machine (or algorithm) which we input a description of a Turing machine and it tells us whether or not it halts. Then to find the nth busy beaver you 1. Enumerate all n state Turing machines 2. In a "for loop" ask your machine whether each n-state Turing machine halts 3. For the ones that halt, run each of them until they halt and write down how many steps it took 4. The largest of these numbers is the busy beaver number BB(n) Similarly lets say you have a machine (or algorithm) which tells you BB(n), you can solve the Halting problem like this 1. Run the Turing machine until it has completed BB(n) steps 2. Remember that if an n-state Turing machine hasn't halted in BB(n) steps then it will never halt 3. If it hasn't halted after BB(n) steps then it won't ever halt so you've solved the halting problem Busy beaver and Halting are (from the point of view of decidability) exactly the same thing.