3
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ I do not think that you need Turing completeness at all. And the equivalence of the Turing Machine and the RAM Machine is not needed either. So if you are trying to compare stack VM and RAM VM you have to optimize them, optimize the program (which is itself non-trivial task) and now if you pick several programs and compare runtimes you have proven that on given computer (maybe with background processes) those programs are better suited to one of them (if everything was perfect...). So what do you want to achieve? In current setting you can compare which one you have implemented better at best. $\endgroup$ – Evil Oct 10 '16 at 2:15
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @AlexFang No, not per se. The fact that "two stacks are Turing-complete" adheres to 2-PDA specifically; see here for a proof. You "have to" use the two stacks for simulating random access on infinite storage; your proposal does not do that. $\endgroup$ – Raphael♦ Oct 9 '16 at 20:41
  • $\begingroup$ @AlexFang That one has LOAD and GLOAD, i.e. random access to (conceptually) infinite memory. $\endgroup$ – Raphael♦ Oct 9 '16 at 22:41
  • 1
    $\begingroup$ @AlexFang It seems to me that you have not enough command on the basics to really reason about Turing-completeness. The way I see it, you have two options. 1) Learn the basics. 2) Show informally that your model can simulate some Turing-complete model (e.g. any "real" programming language) and be satisfied with that. $\endgroup$ – Raphael♦ Oct 9 '16 at 22:43
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think that you use more than just one stack, with memory tape from BF, you have more place, as Raphael and Gilles answer explains (part about fixed memory is relevant). Reiterating, if you can provide random access to any element keeping stack items elsewhere, effectively you have two stacks (or stack and a tape) which is Turing-Complete, otherwise it is Pushdown Automaton. $\endgroup$ – Evil Jul 11 '18 at 0:04
  • 1
    $\begingroup$ I'm not sure what you mean, but essentially what I am saying (not as the only answer, of course, just another alternative) is that a single stack can be made turing-complete if (and only if) elements can be moved within the stack - though it could be argued that this is no longer truly a stack (which would be totally correct). $\endgroup$ – brandonmack Jul 11 '18 at 17:08
  • $\begingroup$ The protocol of a stack is that it only be accessed from the top, which allows for exactly two operations, i.e. push and pop. A "stack" whose elements can be shifted is not a stack in the theoretical sense. But congratulations, at least you've invented and implemented another interesting data structure :) $\endgroup$ – wlnirvana Nov 24 '20 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.