3 ms·
If you get < 47M steps out of all possible 5 state machines, they you have proven the conjecture. A 5 state requires at most 47M states. I don't know if that's
by daveguy 4y ago
If you get < 47M steps out of all possible 5 state machines, they you have proven the conjecture. A 5 state requires at most 47M states. I don't know if that's an upper bound or a precise estimate, but if they all halt, it's true.
- zaarn 4y agoThe tape under the turing machine is infinite, so it's certainly not limited to 47M states. The conjecture states that all machines that halt will do so within 47M states.
- schoen 4y agoSteps rather than states.
- schoen 4y agoThe 47 million thing is based on a specific machine, which was identified as the current 5-state champion in 1990 and is known to halt. https://bbchallenge.org/story#goal https://bbchallenge.org/story#goal Since nobody has found any busier 5-state beaver than that since 1990, Scott Aaronson conjectured that this might be the actual maximum for halting 5-state machines.
- deleted 4y ago[deleted]