[Solved]: Is a stack machine with a forward read iterator Turing complete?

ignougroup
Problem Detail: 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.
Asked By : Thomas Klimpel

Answered By : user23013

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41246