Uma máquina de empilhamento com um iterador de leitura direta Turing está concluída?

7

É sabido que uma máquina com uma única pilha, como apenas armazenamento ilimitado, não está completa com Turing, se puder apenas ler a partir da parte superior da pilha. Eu quero uma máquina que seja (ligeiramente) mais poderosa que uma máquina de empilhar, mas que ainda não esteja completa com Turing. (Gostaria de saber se existe uma máquina completa não-Turing, que possa simular deterministicamente qualquer autômato não-determinístico de pushdown com uma única desaceleração polinomial.) A extensão mais benigna (direta) que me veio à mente foi uma (única) frente leia o iterador.

Deixe-me elaborar os detalhes da implementação, para deixar claro o que quero dizer com um iterador de leitura direta. Uma lista vinculada única pode ser usada para implementar uma pilha. Deixe a lista ser implementada por um ponteiro pTop, que é zero ou aponta para um SListnó. Um SListnó consiste em um campo de carga útil valuee um campo de ponteiro pNext, onde pNexté zero ou aponta para um SListnó. Deixe o iterador de leitura direta ser implementado por um ponteiro pRead, que é zero ou aponta para um SListnó. Os ponteiros pTope pReadnão podem ser acessados ​​diretamente, mas só podem ser usados ​​pelos seguintes métodos:

  • Push(val)cria um novo SListncom n.value = vale n.pNext = pTop, e define pTop = &n.
  • Pop()aborta se pTop == 0ou pRead == pTop. Caso contrário, ele lê val = pTop->valuee pTopNext = pTop->pNextlibera o SListnó apontado por pTop, define pTop = pTopNexte retorna val.
  • ReadBegin()conjuntos pRead = pTop.
  • ReadNext()aborta se pRead == 0. Caso contrário, ele lê val = pRead->value, define pRead = pRead->pNexte retorna val.
  • ReadFinished()retorna truese pRead == 0e de falseoutra forma.
Thomas Klimpel
fonte
Eu deveria esclarecer isso inicialmente pTop == 0e pRead == 0. Um método ReadCancel()que define pRead = 0também pode ser uma boa ideia, porque, caso contrário, o abortar de Pop()for pRead == pToppode ser irritante.
Thomas Klimpel
3
Entre o autômato de empilhamento e as máquinas de Turing na hierarquia de Chomsky, está a máquina de Turing não determinística de limite linear, correspondente à linguagem sensível ao contexto .
Pål GD
11
Existem autômatos com uma pilha de pilhas, mas eu esqueci o nome. Além disso, lembro de nossos autômatos de pilha "homebrew" .
Raphael
@ThomasKlimpel apenas um aviso de que houve um erro na minha resposta, mas não um erro catastrófico, você ainda está livre da perfeição de Turing, mas seu modelo é um pouco mais poderoso do que eu pensava (eu interpretei mal a propriedade que não apagava , de uma maneira realmente idiota em retrospectiva).
Luke Mathieson
11
@ThomasKlimpel, um segundo alerta, user23013 está correto (veja a resposta), seu modelo está completo de Turing - o argumento decisivo é que você tem dois ponteiros na pilha, enquanto o Stack Automata possui apenas um (para que possa se mover pela pilha, mas só pode aparecer / empurrar na parte superior).
Luke Mathieson

Respostas:

5

Infelizmente, o seu modelo é completo em Turing.

Você pode simular uma fila na sua estrutura de dados usando o seguinte algoritmo. Introduziu 3 novos símbolos de pilha:d,x,y.

Enqueue(val)é justo Push(val).

Para Dequeue():

  1. ReadBegin().
  2. Conte o número de qualquer outra coisa - número de dna pilha inteira (que deve ser sempre não-negativa). Empurrary ou pop x para cada de empurre x ou pop ypara qualquer outra coisa. Sempre prefira pop para empurrar. Finalmente, não haveráy na pilha e o resultado será o número de x no topo da pilha.
  3. ReadBegin().
  4. Enquanto pTopé umx:
    1. Repita ReadNext()até retornar algo diferente dex e d.
    2. Pop().
  5. Empurre um d.
  6. O último resultado de ReadNext()é retornado como resultado de Dequeue.

A prova é direta. Verifique o histórico de revisões para obter uma versão mais complicada, primeiro reduzindo-a para uma versão bidirecional.

user23013
fonte
Encontrou a diferença, você está correto, o modelo do OP é Turing completo. Um autômato de pilha não possui um segundo cabeçote de leitura para digitalizar a pilha; ele pode simplesmente mover seu cabeçote normal para cima e para baixo, mas pode apenas empurrar para cima.
Luke Mathieson
5

Seu modelo é Turing completo (ao contrário do que eu pensava anteriormente), consulte a resposta do usuário21313, um esboço da prova (a essência é que você pode simular uma fila e os autômatos de filas estão completos Turing).

Existem várias maneiras de enfraquecer o modelo para cair na equivalência com autômatos vinculados lineares ou inferiores.

Ginsburg, Greibach & Harrison [1] fornecem uma máquina chamada "Stack Automaton", que é um PDA com dois recursos adicionais: 1. O cabeçote de entrada pode se mover para a esquerda e para a direita (para digitalizar partes da entrada vistas anteriormente). 2. A cabeça de leitura / gravação na pilha pode digitalizar através da pilha no modo somente leitura, mas pressionar e saltar ainda ocorre apenas na parte superior. Observe a principal diferença aqui com o seu modelo, que me confundiu anteriormente: a pilha possui apenas uma cabeça / ponteiro que pode mover para cima e para baixo na pilha, enquanto a sua possui duas, o que é suficiente para tornar seu modelo Turing completo. Eles também fornecem outro modelo [2], onde a entrada só pode ser lida da esquerda para a direita, mas a digitalização de pilha somente leitura adicional ainda está disponível.

Na Figura 2 de [1], eles fornecem a contenção (comprovada na Seção 5 da mesma, talvez com algumas partes em [2]) e as linguagens de autômatos de pilha não determinísticos bidirecionais estão estritamente contidas em R. No entanto, eles são equivalentes a autômatos vinculados lineares não determinísticos, portanto reconhecem linguagens sensíveis ao contexto.

Autômatos de pilha bidirecional e não determinístico e autômatos de pilha bidirecional parecem equivalentes, no entanto, alterar a cabeça de entrada para unidirecional faz uma diferença significativa. O conjunto de linguagens de autômatos de pilha não determinística unidirecionais é um subconjunto estrito de linguagens sensíveis ao contexto (ainda não sei exatamente onde ainda) e o conjunto de autômatos de pilha determinística de mão única (que são equivalentes ao seu modelo ) languages ​​é um subconjunto estrito do conjunto de idiomas unideterministas não-determinísticos de pilha de autômatos.

Um tipo mais fraco novamente, que fica abaixo desses, é o autômato da pilha que não apaga, que só pode gravar na pilha.

Hopcroft & Ullman mostram que os idiomas reconhecidos pelos autómatos de pilha determinísticos que não apagam correspondem a DSPUMACE(nregistron) autómatos não determinísticos de pilha não apagáveis ​​correspondem a DSPUMACE(n2).

Termo aditivo

Depois de mais algumas escavações, esses slides de aula sugerem que os autômatos determinísticos de pilha unidirecional e sem apagamento são estritamente mais fracos que a versão bidirecional; portanto, reconheça algo menos queDSPUMACE(nregistron).

Também encontrei outros artigos de Hopcroft e Ullman [4,5], que podem fornecer mais algumas pistas, mas parece ser tangencial neste momento. [5] pelo menos prova algumas equivalências de alguns Stack Automata com LBAs.

Referências

  1. Seymour Ginsburg, Sheila A. Greibach e Michael A. Harrison, "Stack Automata and Compiling". Journal of the ACM, 14 (1): 172–201, 1967.
  2. Seymour Ginsburg, Sheila A. Greibach e Michael A. Harrison, "Autômato de pilha unidirecional". Journal of the ACM, 14 (2): 389–418, 1967.
  3. John E. Hopcroft, Jeffrey D. Ullman, "Automatismos de pilha não-visualizáveis" . JCSS, 1 (2): 166-186, 1967.
  4. John E. Hopcroft, Jeffrey D. Ullman, "Autômatos determinísticos da pilha e o operador do quociente" , JCSS, 2: 1-12, 1968.
  5. John E. Hopcroft, Jeffrey D. Ullman, "Dois resultados em autômatos de pilha unidirecional" , Simpósio sobre Switching e teoria de autômatos (SWAT - mas não aquele SWAT), 1967.
Luke Mathieson
fonte
Mas o modelo nesta pergunta não é apagável, o que deve ser equivalente à sua versão bidirecional (gravando e contando as operações push / pop / up / down na pilha).
user23013
@ user23013 correto, interpretei mal a parte que não foi apagada.
Luke Mathieson
Apenas tentei entender por que minha conclusão não concorda com a sua e estou convencido de que esse modelo está de fato Turing completo agora. Para confirmar: onde diz que o autômato de pilha bidirecional não pode usar a pilha como uma fila (coloque o ponteiro extra na parte inferior e nunca se mova para baixo)? Se for proibido de alguma forma, acho que não está especificado nesta pergunta.
user23013
@ user23013 o segundo ponteiro é somente leitura, não há nenhuma operação para adicionar qualquer coisa onde pReadestiver. (como eu o entendo)
Luke Mathieson
Mas pTope pReadsão dois ponteiros separados. Você pode enfileirar pTope desenfileirar (movendo-se para cima e ignorar qualquer coisa abaixo) em pRead? (Se for bidirecional.)
user23013 12/04