Máquina de Post

Uma  Máquina de Post consiste de duas partes:

Variável X.

    Trata-se de uma variável do tipo fila e é utilizada como entrada, saída e memória de trabalho.

·          A variável X não possui tamanho nem limite fixos. Seu comprimento é igual ao comprimento da palavra corrente armazenada.

·        Os símbolos podem pertencer ao alfabeto de entrada ou a {   #   }, único símbolo auxiliar.

·        Inicialmente, o valor de X é a palavra de entrada. Caso X não contenha símbolos, a entrada é vazia, representada por . 

Programa.

É uma seqüência finita de instruções, representado como um diagrama de fluxos (espécie de fluxograma), no qual cada vértice é uma instrução.

As instruções podem ser de quatro tipos: partida, parada, desvio (leitura com teste) e atribuição.

                          Definição da  Máquina de Post.

Uma Máquina de Post é uma tripla:        M = (, D, #)

onde:

          alfabeto de símbolos de entrada;

D       programa ou diagrama de fluxos construído a partir de componentes elementares denominados partida, parada, desvio e atribuição;

#        símbolo auxiliar.

Componentes elementares de um diagrama de fluxos

a)   Partida. Existe somente uma instrução de início em um programa

b)   Parada. Existem duas alternativas de instruções de parada em um programa, uma de aceitação e outra de rejeição:

a)      Desvio (ou leitura com teste). X ler (X)

denota o comando que lê o símbolo mais à esquerda da palavra armazenada em X, retirando o primeiro símbolo.

·        É uma instrução composta de uma leitura do símbolo à esquerda (início da fila), excluindo-o da fila e desviando o fluxo do programa de acordo com o símbolo lido; 

·        fluxo do programa é determinado de acordo com o símbolo mais à esquerda da palavra.

·        deve ser prevista a possibilidade de X conter a palavra vazia.

·        Portanto, é um desvio condicional, e trata-se de uma função total, estando definida para todos os valores do domínio.

·        Se o cardinal de  é n, então existem n+2 arestas de desvios condicionais, pois se deve incluir as possibilidades # e ,

b)      Atribuição. XXs 

·        É uma instrução de concatenação, gravando o símbolo indicado (pertencente a       {   #   }) à direita da palavra armazenada na variável X (fim da fila).

·        A operação de atribuição é representada a seguir, supondo que s        {   #   }.

 Máquina de Turing e Máquina de Post - Parte I.

   O formalismo Máquina de Turing pode ser simulado pelo formalismo Máquina de Post.

   Seja a Máquina de Turing M = (, Q, , q₀, F, V, ß, b).

    A simulação por uma Máquina de Post M’ =(   V   ,D, ))

pode ser definida como segue:

a)      Fita.

A fita é simulada pela variável X, e a posição corrente da cabeça da fita é representada pela primeira posição da fila (ou variável); o símbolo especial # é introduzido para indicar na variável X o que estava à esquerda da cabeça da fita, a partir do início da fita;

                                                    X = a3   a4   ...   an        a1   a2

b)      Movimento para a Esquerda.

Se o conteúdo da variável X  antes do movimento  é o  seguinte:       

      X= a3   a4   ...   an   #   a1   a2

      Simular o movimento para a esquerda da cabeça e a substituição do símbolo a3 por A3, é necessário alterar o conteúdo de X como segue:

         X = a2   A3   a4   ...   an   #   a1

    Para tal são necessários tantos testes (desvios) e atribuições quantos forem os símbolos da palavra corrente.

c)                  Movimento para a Direita.

     Conteúdo da variável X antes do movimento é

X = a₂   a₃   a₄   ...   a_n        a₁

      Para simular o movimento para a direita da cabeça é necessário alterar o conteúdo de X como segue, o que é trivial:

X = a₃   a₄   ...   a_n        a₁   A₂

Estados

A simulação dos estados é como segue:

·               Estado Inicial. Simulado pela instrução partida;

·               Estados Finais. Simulados pela instrução aceita;

·               Demais Estados. Cada estado corresponde a uma instrução desvio (leitura com teste);

d)      Condições de Rejeição.

·        As condições de rejeição da Máquina de Turing (função programa indefinida ou movimento inválido) são simuladas em Post por rejeita.

 Máquina de Post e Máquina de Turing - Parte II

O formalismo Máquina de Post pode ser simulado pelo formalismo Máquina de Turing.

Prova:

     Suponha uma Máquina de Post M = (, D, )).

     A simulação de M por uma Máquina de Turing

          M’ = (, Q, , q₀, F, {        }, ß, b) pode ser definida por:

a)      Variável X.

A variável X é simulada pela fita, e a posição mais à esquerda da fila é representada pela posição da cabeça da fita.

Para  X = a1   a2   a3   ...   am   #am+1   ...   an

b)      Desvio. X ler(X).

Se o conteúdo da variável X é:  X = a1   a2   a3   ...   am   #am+1   ...   an

A leitura e remoção do símbolo mais à esquerda resulta em:

                                               X = a2   a3   ...   am   #am+1   ...   a_n 

Isso pode ser simulado pela alteração da fita e cabeça da fita

c)                                                                                                                                                                                                                                                                                                Atribuição. XXs.

A concatenação de um símbolo s deve sempre ser à direita do conteúdo da variável X (ou seja, no fim da fila).

Para o conteúdo de X

                                                   X = a1   ...   am   #am+1   ...   an

resulta em

                                                   X = a1   ...   am   #am+1   ...   ans

o que pode ser simulado pela Máquina de Turing:

Move-se a cabeça para o fim da fita, grava-se o símbolo s e retorna-se para a posição correspondente ao primeiro símbolo da fila.

a)      Partida.

A instrução partida pode ser simulada em uma Máquina de Turing usando o estado inicial

b)      Aceita.

Uma instrução aceita pode ser simulada em uma Máquina de Turing usando um estado final

c)      Rejeita.

Uma instrução rejeita pode ser simulada em uma Máquina de Turing usando uma condição excepcional de parada (como um movimento inválido).