The Halting Problem is undecidable only for Turing machines, but we are restricting ourselves to finite state machines - and with a finite number of states it m

The Halting Problem is undecidable only for Turing machines, but we are restricting ourselves to finite state machines - and with a finite number of states it must eventually either halt or repeat a previous configuration. https://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls https://en.wikipedia.org/wiki/Halting_problem#Common_pitfall... I'd go so far to say that this is a key advantage of FSMs - without Turing completeness you get much better options for theoretical analysis.