Hacker News new | ask | show | jobs
by __MatrixMan__ 619 days ago
I think this is related to the https://en.wikipedia.org/wiki/Busy_beaver game. I count 5 bits on the tape, and BB(5) = 47,176,870 which seams like a tractable number of steps for a modern computer to check.

If I've understood it correctly, this means that any program for this machine which does not halt after 47,176,871 states will run indefinitely.

BB(6) is thought to be incredibly huge, so it's nice that they stopped at 5.

1 comments

This machine has 8 states, so (for actual Turing Machines with an unbounded tape) you'd be looking at BB(8). However, since the tape can only store 24 symbols, the machine only has 8 (states) * 4 (tape symbols) * 24 (tape length) = 768 different configurations. Thus, any program will either terminate in at most 768 steps, or loop indefinitely.