7
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Klimpel Apr 11 '15 at 13:19
  • 3
    $\begingroup$ 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. $\endgroup$ – Pål GD Apr 11 '15 at 14:06
  • 1
    $\begingroup$ There are automata with a stack of stacks, but I forgot the name. Also, I remember our "homebrew" heap automata. $\endgroup$ – Raphael Apr 11 '15 at 14:38
  • $\begingroup$ @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). $\endgroup$ – Luke Mathieson Apr 12 '15 at 1:07
  • 1
    $\begingroup$ @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). $\endgroup$ – Luke Mathieson Apr 12 '15 at 9:37
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Apr 12 '15 at 9:25
5
$\begingroup$

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.

Ginsburg, Greibach & Harrison [1] give a machine called a "Stack Automaton" which is a PDA with two additional capabilities: 1. The input head can move left an right (so it can scan previously seen parts of the input). 2. The read/write head on the stack can scan through the stack in read-only mode, but pushing and popping still only occur at the top. Note the key difference here with your model, which confused me earlier: the stack only has one head/pointer that it can move up and down the stack, whereas yours has two, which is enough to make your model Turing complete. They also give another model [2], where the input can only be read left-to-right, but the additional read-only stack scanning is still available.

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})$.

Addendum

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.
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – user23013 Apr 11 '15 at 23:20
  • $\begingroup$ @user23013 correct, I misinterpreted the non-erasing part. $\endgroup$ – Luke Mathieson Apr 12 '15 at 0:53
  • $\begingroup$ 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. $\endgroup$ – user23013 Apr 12 '15 at 2:03
  • $\begingroup$ @user23013 the second pointer is read only, there's no operation to add anything where pRead is. (as I understand it) $\endgroup$ – Luke Mathieson Apr 12 '15 at 2:12
  • $\begingroup$ 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.) $\endgroup$ – user23013 Apr 12 '15 at 2:16

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.