Máquina de Post

Maquina de Post
Assim como Turing, Emil Leon Post propôs em 1936 um modelo de Máquina
Universal denominado Máquina de Post. A principal característica da Máquina de Post é que usa uma estrutura de dados do tipo fila para entrada, saída e memória de trabalho. Uma maquina de Post consiste em duas partes: uma variável X e um programa:


Variável X: o Trata-se de uma variável do tipo fila e é utilizada como entrada, saída e memória de trabalho. o A variável X não possui tamanho nem limite fixos. o Seu comprimento é igual ao comprimento da palavra corrente armazenada. o Os símbolos podem pertencer ao alfabeto de entrada ou a { # } , único símbolo auxiliar. o Inicialmente, o valor de X é a palavra de entrada. Caso X não contenha símbolos, a entrada é vazia, representada por ε.



Programa: o É uma sequência finita de instruções, representado como um diagrama de fluxos (espécie de fluxograma), no qual cada vértice é uma instrução. o As instruções podem ser de quatro tipos: partida, parada, desvio
(leitura com teste) e atribuição.

A máquina de Post é dada por uma tripla:
M = (Ʃ,D,#)
Onde:
Ʃ = Alfabeto de símbolos de entrada;
D = Programa ou diagrama de fluxos, construídos a partir de componentes elementares denominados partida, parada, desvio e atribuição.
# = Símbolo auxiliar

Os seus componentes de diagrama de fluxo são:


Partida: Existe somente uma instrução de início (partida) em um programa 

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



Desvio ou Teste: o Determina o fluxo do programa de acordo com o símbolo mais à esquerda da palavra armazenada na variável X (início da fila). o Também deve ser prevista a possibilidade de X conter a palavra vazia. o Portanto, é um desvio condicional, e trata-se de uma função total, ou seja, definida para todos os valores do domínio. o Assim, se o cardinal de Σ é n, então existem n+2 arestas de