It is undecidable. If we had an algorithm to compute # of steps in Busy Beaver (n) (let's call it S(n)) then for all Turing Machines with n states run S(n) step

It is undecidable. If we had an algorithm to compute # of steps in Busy Beaver (n) (let's call it S(n)) then for all Turing Machines with n states run S(n) steps. If it doesn't halt, it will never halt. Halting problem solved! (well, blank tape halting problem, which is as hard as halting problem). https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S(n)_and_%CE%A3(n) https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomput... > On reflection though, that's not just a bargain, it's also an outright contradiction; we know no such program exists, so making this offer doesn't affect the market at all. Perhaps there's a sneakier variation on this. We do know Busy beaver 1 to 4 (via brute force). We have lower bound for 5. It's definitely possible to compute more of these values. Uncomputable does not mean not possible to compute, it means you cannot find an algorithm that solves the problem in general. So, maybe by dedicating bizarre amount of compute, you could find BB # 1M to claim your $1M from me. Get rich quick!