snippetMinor
How can a stack-based VM be Turing-Complete?
Viewed 0 times
canstackcompletebasedhowturing
Problem
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!
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!
Solution
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.
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.
Context
StackExchange Computer Science Q#64410, answer score: 9
Revisions (0)
No revisions yet.