How can a stack-based VM be Turing-Complete?

Question

I was trying to implement a stack-based Virtual Machine (e.g. like JVM or some early version of Lua) for some benchmarks in order to test its performance against a Register-based VM.

I originally implemented it as having a global stack for all values and an array of instructions, where for the sake of simplicity, no functions are implemented, but only goto statements that jump occationally in between the array of instructions, in order to operate on the stack. All instructions are decoded in a linear fashion, and then loaded into an array, which in turn gets fed into the gigantic switch, looping itself while directing instructions to different operations. The values contained in the instructions are decoded seperately within the switch, and then get stored into the global stack, when needed.

Later on, I heard that in order to be Turing-equivalent, the stack machine must have at least two stacks. So the question I'm asking here, is 1) is my original design Turing-equivalent? 2) If not, how to revise the design so that it would be Turing-equivalent?

The reason for the stack VM to be Turing equivalent is that then its speed and efficiency can be compared to another Turing-equivalent custom-made Register machine. Please correct me on this if it does not :)

Thanks!

Answer 1

You are confusing stack-oriented programming languages (resp. their interpretation model) with pushdown automata. The former can be Turing-complete because they can access an (infinite) random-access memory; the latter does not have any memory but the (one) stack.

The description of your machine (model) is not very clear. I think you can decide its power on your own given the above criterion.

Answer 2

If the stack machine is only allowed to access the top of the stack, and apart from the stack it only has a finite amount of storage, then it's a pushdown automaton. Pushdown automata are not Turing-complete; non-deterministic pushdown automata can only recognize context-free languages, and deterministic ones even less.

With two stacks, such that the machine can push and pop from either stack, the machine is equivalent to a Turing machine. This is fairly easy to see: given a Turing machine, you can build an equivalent two-stack automaton by pushing the input onto one stack, and then treating forward motion on the tape as popping from the first stack and pushing onto the second stack, and vice versa for backward motion.

If the stack machine is allowed to access data from any point in the stack, which is normally the case when a stack machine is used to build a virtual machine, it's a different story. In this case the shape of the stack doesn't matter, what you have is a random-access machine. From the point of view of computability, it's the same thing as a register machine, it's just a matter of how you name the registers: by calling it “stack machine”, you're just saying that the registers are numbered in a certain way.

RAM are equivalent to Turing machines. There is a subtlety with RAM: the registers are not finite registers, they are “variable-sized” registers that can accommodate numbers that are as large as needed for the computation. In practice, most concrete machines are like that — a register or memory cell is as large as it takes to store a pointer, and if the size of a pointer exceeds the register size, it means that you've overflowed the memory of your machine and you start the computation again on a machine with more memory and bigger registers.

Answer 3

I know this is an old thread, but I feel this answer can add some to the question.

I recently implemented a virtual machine that uses only a single stack, but is Turing complete: the thing that makes this work is simply one instruction, which moves the element at the bottom of the stack to the top. This allows access to any given variable on the stack at any time, and is based on the idea that in Brainf**k, pushing to a stack is equivalent to > and incrementing to a particular value (if the stack is used as BF's tape), while moving a variable from the bottom of the stack to the top (giving access to an otherwise inaccessible variable) is equivalent to <.

Another way I have seen this done is by adding an instruction to swap the top variable with any other stack variable (again giving access to any arbitrary variable).

Both of these, with a carefully selected set of other instructions, can allow a stack-based machine to be Turing complete with only one (modified) stack.