|
|
|
|
|
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. |
|