3 ms·
Wouldn't it simply be a linear bounded automaton (LBA)? I understand you can implement recursion via some tricks but only as many steps as you predefine (see e.
by sonnyOrullivan 13y ago
Wouldn't it simply be a linear bounded automaton (LBA)? I understand you can implement recursion via some tricks but only as many steps as you predefine (see e.g. https://stackoverflow.com/questions/7508475/is-c-preprocessor-metaprogramming-turing-complete https://stackoverflow.com/questions/7508475/is-c-preprocesso...)
This reeks like an LBA to me.
- roywiggins 13y agoMy 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.