# Is a stack machine with a forward read iterator Turing complete?

It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful than a stack machine, but still not Turing complete. (I wonder whether there exists a non-Turing complete machine, which can deterministically simulate any non-deterministic pushdown automata with an only polynomial slow-down.) The most benign (straightforward) extension that came to my mind was a (single) forward read iterator.

Let me elaborate the implementation details, to make it clear what I mean by a forward read iterator. A singly linked list can be used for implementing a stack. Let the list be implemented by a pointer pTop, which is either zero, or points to an SList node. An SList node consists of a payload field value and a pointer field pNext, where pNext is either zero, or points to an SList node. Let the forward read iterator be implemented by a pointer pRead, which is either zero, or points to an SListnode. The pointers pTop and pRead cannot be accessed directly, but can only be used via the following methods:

• Push(val) creates a new SList node n with n.value = val and n.pNext = pTop, and sets pTop = &n.
• Pop() aborts if pTop == 0 or pRead == pTop. Otherwise it reads val = pTop->value and pTopNext = pTop->pNext, frees the SList node pointed to by pTop, sets pTop = pTopNext and returns val.
• ReadBegin() sets pRead = pTop.
• ReadNext() aborts if pRead == 0. Otherwise it reads val = pRead->value, sets pRead = pRead->pNext and returns val.
• ReadFinished() returns true if pRead == 0, and false otherwise.
• I should clarify that initially pTop == 0 and pRead == 0. A method ReadCancel() which sets pRead = 0 might also be a good idea, because otherwise the abort of Pop() for pRead == pTop might be annoying. Apr 11 '15 at 13:19
• Between the pushdown automata and the Turing machines in the Chomsky hierarchy sits the Linear-bounded non-deterministic Turing machine, corresponding to context-sensitive language. Apr 11 '15 at 14:06
• There are automata with a stack of stacks, but I forgot the name. Also, I remember our "homebrew" heap automata.
– Raphael
Apr 11 '15 at 14:38
• @ThomasKlimpel just a heads up that there was a mistake in my answer, but not a catastrophic one, you're still clear from Turing completeness, but your model is a little more powerful than I first thought (I misinterpreted the non-erasing property, in a really dumb way in hindsight). Apr 12 '15 at 1:07
• @ThomasKlimpel, a second heads up, user23013 is correct (see his answer), your model is Turing complete - the clincher is that you have two pointers into the stack, whereas Stack Automata only have one (so it can move around the stack, but can only pop/push at the top). Apr 12 '15 at 9:37

Your model is Turing-complete, unfortunately.

You can simulate a queue in your data structure using the following algorithm. It introduced 3 new stack symbols: $d, x, y$.

Enqueue(val) is just Push(val).

For Dequeue():

1. ReadBegin().
2. Count the number of anything else - number of $d$ in the whole stack (which should be always non-negative). Push $y$ or pop $x$ for every $d$, and push $x$ or pop $y$ for anything else. Always prefer pop to push. Finally there won't be any $y$ in the stack and the result will be the number of $x$ on the top of the stack.
3. ReadBegin().
4. While pTop is a $x$:
1. Repeat ReadNext() until it returned something other than $x$ and $d$.
2. Pop().
5. Push a $d$.
6. The last result of ReadNext() is returned as the result of Dequeue.

The proof is straightforward. Check the revision history for a more complicated version firstly reducing it to a two-way version.

• Found the difference, you are correct, the OP's model is Turing complete. A Stack Automaton doesn't have a second read head to scan the stack, it can just move its normal head up and down, but can only push at the top. Apr 12 '15 at 9:25

Your model is Turing complete (unlike what I previously thought), see user23013's answer a sketch of the proof (the essence is you can simulate a queue, and queue automata are Turing complete).

There are several ways to weaken you model to drop to equivalence with linear bound automata or lower.

In Figure 2 of [1] they give the containment (proved in Section 5 of the same, perhaps with some parts in [2]) and two-way nondeterministic stack automata languages are strictly contained in $\mathrm{R}$. However they are equivalent to nondeterministic linear bound automata, so they recognise context sensitive-languages.

Two-way and nondeterministic stack automata and two-way deterministic stack automata seem to be equivalent, however changing the input head to one-way makes a significant difference. The set of one-way nondeterministic stack automata languages is a strict subset of context-sensitive languages (I can't put my finger on exactly where yet), and the set of one-way deterministic stack automata (which are equivalent to your model) languages is a strict subset of the set of one-way nondeterministic stack automata languages.

A weaker type again, which falls below these are non-erasing stack automata, which can only write to the stack.

Hopcroft & Ullman show that the languages recognised by non-erasing deterministic stack automata corresponds to $\mathrm{DSPACE}(n\log n)$ and non-erasing nondeterministic stack automata corresponds to $\mathrm{DSPACE}(n^{2})$.

After some more digging, these lecture slides suggest that one-way non-erasing deterministic stack automata are strictly weaker than the two-way version, so recognise something less than $\mathrm{DSPACE}(n\log n)$.

I also found further Hopcroft & Ullman [4,5] papers, which may provide a few more clues, but it seems to be tangential at this point. [5] at least proves some equivalences of some Stack Automata with LBAs.

References

1. Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison, "Stack Automata and Compiling". Journal of the ACM, 14(1):172–201, 1967.
2. Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison, "One-Way Stack Automata". Journal of the ACM, 14(2):389–418, 1967.
3. John E. Hopcroft, Jeffrey D. Ullman, "Nonerasing Stack Automata". JCSS, 1(2):166–186, 1967.
4. John E. Hopcroft, Jeffrey D. Ullman, "Deterministic Stack Automata and the Quotient Operator", JCSS, 2:1-12, 1968.
5. John E. Hopcroft, Jeffrey D. Ullman, "Two results on one-way stack automata", Symposium on Switching and Automata Theory (SWAT - but not that SWAT), 1967.
• But the model in this question isn't non-erasing, which should be equivalent to its two-way version (by recording and counting push/pop/up/down operations in the stack). Apr 11 '15 at 23:20
• @user23013 correct, I misinterpreted the non-erasing part. Apr 12 '15 at 0:53
• Just tried to see why my conclusion doesn't agree with yours, and I'm convinced that this model is in fact Turing complete now. To confirm: where does it say the two-way stack automaton cannot use the stack as a queue (set the extra pointer at the bottom and never moving down)? If it is forbidden somehow, I think that isn't specified in this question. Apr 12 '15 at 2:03
• @user23013 the second pointer is read only, there's no operation to add anything where pRead is. (as I understand it) Apr 12 '15 at 2:12
• But pTop and pRead are two separate pointers. You can enqueue at pTop and dequeue (by moving up and ignore anything below) at pRead? (If it is two-way.) Apr 12 '15 at 2:16