# Máquina de Post

Na teoria da computação, uma máquina de Post, assim denominada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados do tipo fila com um símbolo auxiliar. Post publicou este modelo computacional em 1943 como uma forma simples de sistema canônico de Post. Em poucas palavras, uma máquina de estados finita cuja fila tem um tamanho ilimitado, tal que em cada transição a máquina lê o símbolo da cabeça da fila, remove um número fixo de símbolos da cabeça, e ao fim concatena uma palavra-símbolo pré-definida ao símbolo removido.

## Definição

Uma máquina de Post é uma tripla M=(Σ,D,#)
onde
* Σ é um alfabeto finito de símbolos, um dos quais é um símbolo especial de parada. Cadeias finitas (possivelmente vazias) em Σ são chamadas de palavras.
* D é um conjunto de regras de produção, atribuindo uma palavra D(x) (chamada de produção) para cada símbolo em Σ. A produção (diga-se D(H)) atribuída ao símbolo de parada é vista abaixo e não possui influência nas computações, mas por conveniência usa-se D(H) = H
* # é um inteiro positivo auxiliar, chamado de número de deleção.
O termo Máquina de Post-# é frequentemente usado para enfatizar o símbolo auxíliar. As definições variam de certa forma na literatura(ver Referências), apresentaremos aqui a definição de Rogozhin.
* Uma Palavra de parada é uma palavra que, ou começa com o símbolo de parada ou tem o comprimento menor que m.
* Uma transformação t (chamada de operação de marcação) está definida no conjunto de palavras que não param, such that se x denota o símbolo mais a esquerda de uma palavra S, então t(S) é o resultado de deletar os m símbolos mais a esquerda de S e concatenar a palavra D(x) ao lado direito.
* Uma computação por uma máquina de post é uma sequência finita de palavras produzidas iterando a transformação t, começando com uma palavra inicialmente dada e parando quando uma palavra de parada é produzida. (Por essa definição, uma computação é considerada não existir a menos que uma palavra de parada seja produzida em muitas iterações finitas. Definições alternativas permitem computações sem parada, por exemplo usando um sub conjunto especial do alfabeto para identificar palavras que codificam uma saída.)
O uso de um símbolo de parada na definição acima permite à saída da computação ser codificada na palavra final sozinha, enquanto que por outro lado a saída seria codificada em toda a sequência de palavras produzidas pela iteração da operação de marcação.
Uma definição alternativa comum, usa o símbolo de parada e trata todas as palavras de tamanho menor que # como palavras de parada. Outra definição é a original usada por Post em 1943 ( descrito na nota histórica abaixo), em que somente a cadeia vazia é palavra de parada.

### Exemplo: Uma simples Máquina de Post-2 ilustração

Isto é meramente para ilustrar uma simples Máquina de Post-2 que usa um símbolo de parada.

### Exemplo: Computação de sequências Collatz

Esta simples Máquina de Post-2 é adaptada de [De Mol, 2008]. Ela não usa símbolos de parada, mas para em qualquer palavra de tamanho menor que 2, e computa uma versão ligeiramente modificada de Conjectura de Collatz.
Na sequência original de Collatz, o sucessor de n é ou n/2 (para n par) ou 3n+1 (para n ímpar). O valor 3n+1 é claramente ímpar para n ímpar, já que o próximo termo depois de 3n+1 é certamente (3n+1)/2. Na sequência computada pela Máquina de Post abaixo nós pulamos o passo intermediário, já que o sucessor de n é (3n+1)/2 para n ímpar.
Nesta Máquina de Post, um inteiro positivo n é representado pela palavra aa...a com um número n de a's.

## Turing-completude de Máquinas de Post-#

Para cada # > 1, o conjunto de Máquinas de Post-# é Turing completude; i.e., para cada #> 1, isto é o caso de que para qualquer Máquina de Turing T existe uma Máquina de Post-# que simula T. Em particular, uma Máquina de Post-2 pode ser construída para simular a Máquina de Turing universal , como foi feito por Wang 1963 e por Cocke & Minsky 1964.
Conversely, Uma Máquina de Turing pode ser mostrada ser Universal provando-se que ela pode simular uma classe de Turing-completa de Máquina de Post-#. Por exemplo, Rogozhin 1996 provou a universalidade da classe das Máquinas de Post-2 com o alfabeto {a$_1$, ..., a$_n$, H} e as correspondentes produções {a$_n$a$_n$W$_1$, ..., a$_n$a$_n$W$_{n-1}$, a$_n$a$_n$, H}, onde as W$_k$ são palavras não vazias; ele então provou a universalidade de uma Máquina de Turing muito pequena (4 estados, 6 símbolos) mostrando que ela pode simular a classe das Máquinas de Post.

## O problema da parada em Máquinas de Post-2

Esta versão do Problema da Parada é entre as mais simples, mais facilmente descrito Problema indecidível problema de decisão:
Dado: um inteiro positivo arbitrário n e uma lista de n+1 palavras arbitrárias P$_1$,P$_2$,...,P$_n$,Q sob o alfabeto {1,2,...,n} Pergunta-se: A aplicação repetida da operação t: ijX → XP$_i$ converterá eventualmente Q em uma palavra de tamanho menor que 2? Isto é, a sequência Q, t$^1$(Q), t$^2$(Q), t$^3$(Q), ... termina?

## Nota histórica na definição de Máquina de Post

A definição acima difere da apresentada por Post em 1943, a qual máquinas não usavam símbolos de parada, mas paravam somente na palavra vazia, e com a operação de marcação t sendo descrita como:
* Se x denota o símbolo mais a esquerda de uma palavra não vazia S, então t(S) é a operação que consiste de primeiro concatenar a palavra D(x) ao final à direita de S, e então deletar os # símbolos mais a esquerda do resultado — deletando tudo se existem menos de # símbolos.
O comentário acima sobre a Turing-completude do conjunto de Máquinas de Post-#, para qualquer # > 1, aplica-se também para as Máquinas de Post da forma como foram originalmente definidas por Post.

## Máquinas de Post cíclicas

Uma Máquina de Post cíclica é uma modificação da Máquina de Post original. O alfabeto consiste de somente dois símbolos, 0 e 1, e as regras de produção incluem uma lista de produções consideradas sequenciais, girando ao início da lista depois de considerar a "última" produção da lista. Para cada produção, o símbolo mais a esquerda é examinado—Se o símbolo é 1, a posição atual é concatenada ao final direito da palavra; Se o símbolo é 0, nenhum caractere é concatenado à palavra; em ambos os casos, o símbolo mais a esquerda é então deletado. A máquina para então se e onde a palavra se torna vazia.

### Exemplo

Máquinas de Post cíclicas foram criadas por Matthew Cook sob o emprego de Stephen Wolfram, e foram usadas na demonstração de Cook que a Regra 110 aplicada a Autómato celular é universal. A parte chave da demonstração foi que Máquinas de Post cíclicas podem emular a classe Turing-completude de Máquinas de Post.

## Simulação de Máquinas de Post por Máquinas de Post cíclicas

Uma Máquina de Post-#com o alfabeto {a$_1$, ..., a$_n$} e as respectivas produções {D$_1$, ..., D$_n$} é simulada por uma Máquinas de Post cíclica com #*n produções (Q$_1$, ..., Q$_n$, -, -, ..., -), onde todas além das primeiras n produções são a palavra vazia (denotada por '-'). As Q$_k$ são codificações da respectiva Q$_k$, obitidas na substituição de cada símbolo do alfabeto da Máquina de Post por uma palavra binária de tamanho n como a seguir (estas são aplicadas também a palavra inicial de uma computação por Máquina de Post):
Isto é, a$_k$ é codificado como a cadeia binária com um 1 na posição k a partir da esquerda, e0's nos outros lugares. Sucessivas linhas de computação de Máquinas de Post irão ocorrer codificadas em cada (m*n)-ésima linha de sua simulação pela Máquina de Post Cíclica.

### Exemplo

Este é um exemplo muito pequeno para ilustrar a técnica de simulação.
Cada sexta linha (marcada com '*') produzida pela Máquina de Post cíclica é a codificação de uma linha correspondente da computação por Máquina de Post, até que a parada simulada é alcançada.