I was reading about the busy beaver problem the other day and I'm confused as to why we can't keep an array of Turing machine states that the machine has been through and simply iterate through it at each new machine state to see if it exactly matches a state we've previously seen. That ought to tell us there's an infinite loop, no? Then following this, shouldn't we be able to solve the problem for any given Turing machine, instruction set and tape?
Why can't we detect infinite loops in the busy beaver problem?
algorithms;busy beaver
The state of a TM includes its tape contents. Since the tape is infinite, the number of different tape contents we may encounter is infinite as well. So a TM is not required to repeat a state in order to never halt.As a very simple example, consider the TM that will in each step write a character on the tape and move to the right. -- It will never halt but also never repeat a state.