3 ms·
No, you seem to be misunderstanding the conjecture. It's about the maximum number of steps executed by a Turing machine that eventually halts. If you simulate
by teraflop 4y ago
No, you seem to be misunderstanding the conjecture. It's about the maximum number of steps executed by a Turing machine that eventually halts.
If you simulate a Turing machine up to that many steps, and find it hasn't halted yet, then the conjecture is refuted if you know the machine's execution will eventually terminate -- but famously, there's no algorithm that can reliably tell you whether or not a given TM halts.
If it was just about the maximum number of steps that could be executed by a 5-state Turing machine, it would be trivially false, because it's easy to construct a Turing machine that runs forever.
- avmich 4y agoYeah, I was surprised the statement is constructed this way. Adding condition of eventual halting - which is what makes it the busy beaver - makes the difference :) .
- penteract 4y agoI think that this wording relies on carefully interpreting "before halting". A TM which runs forever can run more than 47 million steps, but it does not run more than 47 million steps steps before halting, since it never halts.
- tcosmo 4y agoI have changed the wording on the website in order to make it hopefully more straightforward: "This conjecture says that if a 5-state Turing machine runs for more than 47,176,870 steps without halting then it will never halt (starting from all-0 memory tape)."