4 ms·

In "Story" website section: "This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting

by avmich 4y ago

In "Story" website section: "This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting from all-0 memory tape)." So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture.

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 ago
  Yeah, 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 ago
    I 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 ago
      I 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)."
rrss 4y ago
> So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture No, you do not refute the conjecture if you run up to this number and a machine does not stop. Finding a machine that runs for more than 47,176,870 steps is easy - there are plenty of machines that run forever. The trick is that it needs to stop.

by avmich 4y ago

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 ago
Yeah, 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 ago
  I 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 ago
    I 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)."

rrss 4y ago

> So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture No, you do not refute the conjecture if you run up to this number and a machine does not stop. Finding a machine that runs for more than 47,176,870 steps is easy - there are plenty of machines that run forever. The trick is that it needs to stop.