3 ms·
It seems like we are effectively asking about the complexity of the halting problem of Turing machines with state space of N bits. It seems incredibly likely t
by rocqua 4y ago
It seems like we are effectively asking about the complexity of the halting problem of Turing machines with state space of N bits.
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.
- wizeman 4y ago> 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.
- rocqua 4y agoI understand you mean "deterministic finite-state machines" rather than "Turing machines". I meant "Turing machines with X states and a type limited to Y bits, with X + Y = N". You can, of course, cast those as Deterministic Finite State Machines, but that will require incredibly many states.