A finite deterministic state machine can not perform more transitions than it has states without returning to a state it has been in before, and once that happe

A finite deterministic state machine can not perform more transitions than it has states without returning to a state it has been in before, and once that happens, because it is deterministic, it will repeat the sequence of transactions, that occurred between the first and second occurrence of that state, indefinitely. All programs that halt, therefore, must do so in less than #states steps, and the rest certainly never will, so we could show, in finite time, whether any given program on that machine will halt. We know, therefore, that the halting problem on this machine is decidable, even if we could not, in practice, demonstrate it. The halting problem was not posed because we want to know if a given program will halt; it was posed as a means of attacking a much deeper problem. Note also that any NFA can be converted to an equivalent DFA by powerset construction. https://en.wikipedia.org/wiki/Powerset_construction https://en.wikipedia.org/wiki/Powerset_construction