Hacker News new | ask | show | jobs
by bdowling 1285 days ago
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.