Hacker News new | ask | show | jobs
by hakuseki 1276 days ago
This seems not quite right to me. A Turing machine may always halt, but with time depending on its input size. The input can be arbitrarily large, so there's no finite bound on the state space.
1 comments

My point, which I admit isn't very poignant, is that you can make an FSM that simulates a TM that only uses a finite portion of its tape. Yes, for some machines you will always be able to construct an input that exceeds what a particular FSM can do. When that happens, however, you can make a bigger FSM that simulates a larger (but still finite) tape.

This is analogous to putting more memory in your computer when you have a problem that doesn't fit.