Une machine de pile avec un itérateur de lecture en avant est-elle complète?

Question

Il est bien connu qu'une machine avec une seule pile car seul le stockage illimité n'est pas complet, s'il ne peut lire que dans le haut de la pile. Je veux une machine qui est (légèrement) plus puissante qu'une machine à pile, mais toujours pas complète. (Je me demande s'il existe une machine complète non touchante, qui peut simuler de manière déterministe n'importe quel automate non déterministe avec un seul ralentissement polynomial.) L'extension la plus bénigne (simple) qui me venait à l'esprit était une (simple) avant Lisez itérateur.

Permettez-moi d'élaborer les détails de la mise en œuvre, pour indiquer clairement ce que je veux dire par un itérateur de lecture avant. UN Liste liée individuellement Peut être utilisé pour implémenter une pile. Que la liste soit implémentée par un pointeur pTop, qui est soit zéro, ou pointe vers un SList nœud. Un SList Le nœud se compose d'un champ de charge utile value et un champ de pointeur pNext, où pNext est soit zéro, soit indique un SList nœud. Laissez l'itérateur de lire vers l'avant être implémenté par un pointeur pRead, qui est soit zéro, ou pointe vers un SListnœud. Les pointeurs pTop et pRead ne peut être accessible directement, mais ne peut être utilisé que via les méthodes suivantes:

• Push(val) crée un nouveau SList nœud n avec n.value = val et n.pNext = pTop, et ensembles pTop = &n.
• Pop() abandonne si pTop == 0 ou pRead == pTop. Sinon, il lit val = pTop->value et pTopNext = pTop->pNext, libère le SList nœud pointé par pTop, sets pTop = pTopNext et revient val.
• ReadBegin() sets pRead = pTop.
• ReadNext() abandonne si pRead == 0. Sinon, il lit val = pRead->value, sets pRead = pRead->pNext et revient val.
• ReadFinished() Retour true si pRead == 0, et false Par ailleurs.