Thank you, but I am aware of all that, and I asked for arrays above in part to be able to emulate a stack (or a tape, if going the turing machine route). (I co

Thank you, but I am aware of all that, and I asked for arrays above in part to be able to emulate a stack (or a tape, if going the turing machine route). (I could emulate a bounded stack with a bunch of variables and conditionals choosing them, but that's pretty ugly, and brings home just how bounded the result would be) > CPU in this case could be stateless or have a limited number of states The bounded state is an issue, but it is for Pentiums as well. We have approximations of Turing equivalent machines in real life, and that's close enough. Regarding these other things: > pushdown automata are defined as finite-state machines combined with a stack I didn't say it was impossible, I said it was difficult with a nontrivial language -- because I've seen people try, and accidentally make things Turing equivalent. If you know what you're doing, like you for instance, then sure, you just leave out problematic features and make sure you don't leave the level of the Chomsky hierarchy you were aiming for. But no, people always want handy things like assignment and arithmetic expressions and loops and function calls and so on. :) A classic example is pure standard SQL (up to a few years ago), which had no loop construct, and the language was famously sub-Turing. But if the embedding language puts some SQL in a loop, it's trivial to emulate a CPU with simple SQL, which won't surprise someone classically trained like yourself, but does tend to surprise random programmers in the wild. (I hear a more recent SQL standard added loops, which I have mixed feelings about.)