Is a stack machine with a forward read iterator Turing complete?
-
02-11-2019 - |
Pergunta
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 SList
node. The pointers pTop
and pRead
cannot be accessed directly, but can only be used via the following methods:
Push(val)
creates a newSList
noden
withn.value = val
andn.pNext = pTop
, and setspTop = &n
.Pop()
aborts ifpTop == 0
orpRead == pTop
. Otherwise it readsval = pTop->value
andpTopNext = pTop->pNext
, frees theSList
node pointed to bypTop
, setspTop = pTopNext
and returnsval
.ReadBegin()
setspRead = pTop
.ReadNext()
aborts ifpRead == 0
. Otherwise it readsval = pRead->value
, setspRead = pRead->pNext
and returnsval
.ReadFinished()
returnstrue
ifpRead == 0
, andfalse
otherwise.
Nenhuma solução correta