A Máquina de Post

Introdução

Há quase 80 anos o matemático Emil L. Post publicou o artigo "Processos Combinatórios Finitos - Formulação 1" (Emil L. Post "Finite Combinatory Processes - Formulation 1") na "Revista da Lógica Simbólica" (The Journal of Symbolic Logic), que formaliza (assim como Turing) o conceito de algoritmo, e de forma implícita (sem usar uma única vez o termo máquina) ele descreve uma máquina abstrata (mais precisamente um modelo de máquina universal) mais tarde chamada de Máquina de Post.

Por ser uma máquina abstrata, sempre é bom lembrar que a Máquina de Post não é um dispositivo que existe na realidade, porém, da mesma forma que podemos fazer qualquer cálculo sem o uso de uma calculadora também podemos supor que a máquina realmente existe e criar programas para ela, bastando para isso saber a sua descrição.

Definição

A Máquina de Post é uma tripla: M = ( Σ, D, # ), onde:

M = máquina de Post

Σ = alfabeto de entrada

D =  programa ou diagrama de fluxos

# = símbolo auxiliar

Em seu artigo, Post apresenta sua máquina usando o exemplo de uma pessoa que está fazendo cálculos. Esta pessoa possui à sua disposição uma fita infinita (que cresce indefinidamente para ambos os lados, apesar de geralmente nos exemplos ela crescer apenas para a direita), cada célula da fita pode estar vazia ou marcada. A estrutura de dados utilizada é do tipo fila (o primeiro a entrar é o primeiro a sair) e esta é a grande diferença entre a máquina de Turing e a máquina de Post.

Para trabalhar com a máquina de Post devemos saber que a fila, que é utilizada como entrada, saída e memória de trabalho é a variável X, e que o programa é uma sequência de instruções, com ele que a máquina sabe o que fazer em cada estado da máquina.

Variável X: não possui tamanho nem limites fixos. Os símbolos podem pertencer ou ao alfabeto de entrada ou ao único símbolo auxiliar {#}. Geralmente, representamos a palavra vazia pelo símbolo ε.

Programa:

Cada instrução pode ser de:

PARTIDA - existe somente uma instrução de início do programa:

PARADA - existem duas alternativas de instruções de parada: aceita e rejeita. Com a parada aceita ocorre uma parada com resultado, ao contrário da parada com rejeita. O programa ainda pode ficar em loop (execução sem parada):

DESVIO ou TESTE - determina o fluxo do programa de acordo com o símbolo mais a esquerda da palavra armazenada (seguindo as regras da estrutura tipo fila). A leitura é destrutiva, caso queira guardar o simbolo lido ele deve ser concatenado ao fim da palavra X armazenada:

ATRIBUIÇÃO - concatena o símbolo indicado (do alfabeto de entrada ou símbolo auxiliar) no fim da palavra X (fim da fila). Na imagem abaixo, está sendo colocado no fim da fila o símbolo auxiliar:

Funcionamento

Consiste no deslocamento ao longo da fila e na impressão ou eliminação das marcas.

Novos Posts!

Usando o Simulador da Máquina de Post

Executando um programa no Simulador de Máquina de Post