> the halting problem of Turing machines with state space of N bits That's an oxymoron, because Turing machines have a state space of infinite bits by definiti

> the halting problem of Turing machines with state space of N bits That's an oxymoron, because Turing machines have a state space of infinite bits by definition. I understand you mean "deterministic finite-state machines" rather than "Turing machines". > It seems incredibly likely that this question has a complexity of O(exp(N)) which very quickly makes the halting problem infeasible to solve for modern computers. I mean, I agree that it's likely, but again, is this proven? I'm not aware that it is and therefore I think this is actually missing many of the points I mentioned. It could be false for all we know.