3 ms·
If a Turing machine with finite memory is equivalent in power to a FSM, why are non-deterministic linear bounded Turing machine considered so much more powerful
by theseoafs 12y ago
If a Turing machine with finite memory is equivalent in power to a FSM, why are non-deterministic linear bounded Turing machine considered so much more powerful than FSM's?
- mikeash 12y agoThe amount of memory that can be used by an LBA is specified by the input, not by the machine, and there's no limit to how big it can be, only that there has to be some limit. In short, it still has infinite memory, you just have to pick how much of it to use when you run it. This differs from an FSM or a Turing machine with finite memory in that you choose the quantity of memory when specifying the machine rather than the input.