3 ms·
My first instinct is that you're right- at least, I don't think it can be any more powerful than an LBA: if there's a finite number of state transitions it can
by roywiggins 13y ago
My first instinct is that you're right- at least, I don't think it can be any more powerful than an LBA: if there's a finite number of state transitions it can make, then it can only actually "get to" a certain distance along the tape, and you can just chop the tape at that point.
- lisper 13y agoNope, a cpp-machine is strictly less powerful than an LBA, or even an FSA. An LBA (and an FSA) can enter an infinite loop. A cpp-machine can't.