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

Warp wrote:
>   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).

How about reading and writing memory that isn't an "immediate" value? 
(I.e., random data memory, instead of inline literals in the code?)

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

Depends in part, I expect, on the size of your values. :-) Seriously, if 
you have unbounded integers for values, that's a different question.

I *will* say that when I implemented FORTH a few times, getting things 
like "access 6 deep and copy it to the top of the stack" made things 
about 23,845 times easier to write programs.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Warp wrote:
>   My question is: Is this kind of programming language turing-complete?

BTW, the way you would prove this is to implement an interpreter for 
turing machines in the language. Since a TM has an arbitrarily large 
state table, you need to be able to access unbounded state. Without 
being able to access main RAM (i.e., the representation of the state 
table) without losing your current position (i.e., without popping 
everything else off the stack), I'd guess not.

Having a "load the word whose address is on top of the stack" would be 
necessary but maybe not sufficient.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   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).

> How about reading and writing memory that isn't an "immediate" value? 
> (I.e., random data memory, instead of inline literals in the code?)

  Well, that would effectively be a variable, and thus it's not so much
a stack-based language anymore.

  In this specific case, there's no such support. (Well, technically
speaking it could be possible to construct support for it, but it's way
too cumbersome and complicated to be feasible.)

> I *will* say that when I implemented FORTH a few times, getting things 
> like "access 6 deep and copy it to the top of the stack" made things 
> about 23,845 times easier to write programs.

  I know, but no such luck in this case...

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Well, that would effectively be a variable, and thus it's not so much
> a stack-based language anymore.

Technically, it's still stack based, since the memory access is going 
thru the stack.

Are you saying the only operations to put data *on* the stack are DUP 
and PUSH IMMEDIATE?  Seems like it would be difficult to do much, yah.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Are you saying the only operations to put data *on* the stack are DUP 
> and PUSH IMMEDIATE?  Seems like it would be difficult to do much, yah.

  It supports pushing characters (as their ascii values) in a string too,
but that isn't much of a help in this case.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Are you saying the only operations to put data *on* the stack are DUP 
>> and PUSH IMMEDIATE?  Seems like it would be difficult to do much, yah.
> 
>   It supports pushing characters (as their ascii values) in a string too,
> but that isn't much of a help in this case.

I take it you mean in the same way you could just code a series of "push 
this integer literal" instruction?

I don't see how you can do it, then.  Imagine a 10,000 state turing 
machine. You wouldn't be able to access state 5000's instruction without 
wiping out at least instructions 5003-10000.

Maybe there's something exceptionally clever you could do, but with 
limited-width registers (i.e., top-of-stack) it would be hard to know what.

Out of curiousity, what kind of language or machine is this?  Or is this 
like some contest/homework style problem?

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Out of curiousity, what kind of language or machine is this?

  Befunge.

  I tried to create a mandelbrot generator with it. Failed.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Darren New <dne### [at] sanrrcom> wrote:
> > Out of curiousity, what kind of language or machine is this?
>
>   Befunge.
>
>   I tried to create a mandelbrot generator with it. Failed.
>
> --
>                                                           - Warp

What about

http://catseye.tc/projects/befunge93/eg/mandel.bf

linked to from

http://catseye.tc/projects/befunge93/eg/INDEX.html

?

Tom

Post a reply to this message

Tom York <alp### [at] zubenelgenubi34spcom> wrote:
> What about

> http://catseye.tc/projects/befunge93/eg/mandel.bf

  Not much of a help trying to know how to implement it, as you can see...

-- 
                                                          - Warp

Post a reply to this message