4 ms·

"If you find me nth Busy Beaver program for any n>10, I'll give you $n"

• MaxBarraclough 6y ago
  I could be wrong, but that isn't known to be undecidable, is it? Merely extremely difficult? I was thinking If you give me a program that solves the halting problem, I'll give you $1. 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.
  • gnulinux 6y ago
    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!