###

Question:

My programming language has no arrays, no lists, no pointers, no eval and no variable variables. All it has:

Ordinary variables like you know them from most programming languages: They all have an exact name and a value.

**One**stack. Functions provided are: push (add element to top), pop (remove element from top, get value) and empty (check if stack is empty)

My language is turing-complete. (Basic arithmetics, conditional jumps, etc implemented) That means, it must be possible to implement some sort of list or array, right?

**But I have no idea how...**

What I want to achieve: Create a function which can retrieve and/or change an element x of the stack.

I could easily add this function in the implementation of my language, in the interpreter, but I want to do it *in* my programming language.

- "Solution" one (Accessing an element x, counting from the stack top)

Create a loop. Pop off the element from the stack top `x`

times. The last element popped of is element number `x`

. I end up with a destroyed stack.

- Solution two:

Do the same as above, but store all popped off values in a **second** stack. Then you could move all elements back after you are done. But you know what? I don't have a second stack!

###

Solution:1

Sounds like a homework question, as it flexing random bits of Computer Science...

I think you would want to use recursion to do this. Say I have something like this..

`Queue globalQueue = new Queue(); `

Then I could have code that got element X like this

`public Object findElement(stepsToTake s) { if (queue.empty()) { throw new EmptyQueueYouFailException(); } Object o = queue.pop(); if (s == 0) { queue.push(o); return o; } Object actualResult = findElement( s - 1 ); //restore this element to the stack queue.push(o); //return actual result return actualResult; } `

So more likely than not I made some bug... have not thought through it super well. Especially worried that I will reorder the stack because of the order of my calls..

Hopefully this can get you thinking along the right lines to get a solution?

###

Solution:2

Do you have procedure calls and recursion? Then you do have a second stack, the call stack. If not, are you sure it's Turing complete, and not just a PDA?

###

Solution:3

If you have only one stack, this is equivalent to a pushdown automaton, which can recognize context-free languages, and is not Turing-complete. Your proof of Turing completeness should inform how you can implement freeform memory access.

In general, to prove Turing-completeness, you must be able to show how your language can move left to right over a tape (or indirectly simulate this process), which corresponds roughly to a single higher-level array.

**Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com**

EmoticonEmoticon