Assume you have a stack-based programming language where the stack is
the only place where you can store and handle numerical values. The
language supports pushing and popping values from the stack, as well
as all the basic mathematical operations which operate on the top value
on the stack (for one-operand operations, for example a not operation pops
the top value and pushes its logical not value) or the two top values on the
stack (for example a plus operetion pops two values from the stack and
pushes their sum). Swapping the two top values on the stack is also
supported. Looping is supported, but the loop counter must obviously be
a value on the top of the stack (when the loop condition is evaluated,
like eg. "if the value on top of the stack is not zero, loop").

  What is *not* supported is accessing any value in the stack deeper
than the two top values (which can be accessed eg. using the swap
command).

  My question is: Is this kind of programming language turing-complete?
Can every possible algorithm be implemented with it?

  A more concrete question: Could for example the mandelbrot set be
calculated with such a programming language? (Let's assume there exists
a command like "output the value on the top of the stack as an ascii
character", for example.)

  I just can't figure out a way of doing this.

  For example postscript is stack-based, but it has commands which give
you access to any value in the stack, like "copy the nth value in the
stack to the top of the stack", which is enough to implement the mandelbrot
set calculation. However, without such free access I just can't figure out
a way.

-- 
                                                          - Warp

Post a reply to this message