Máquina de Post

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.

Na teoria da computação, uma máquina de Post, nomeada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados do tipo fila com um símbolo auxiliar1 . Post publicou este modelo computacional em 1943 como uma forma simples de sistema canônico de Post.

Definição[editar | editar código-fonte]

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 programa ou diagrama de fluxos contendo instruções elementares.
  • # é o símbolo auxiliar.


Exemplo[editar | editar código-fonte]

Uma máquina de Post simples


Referências

  1. DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: Máquinas Universais e Computabilidade. 2ª ed. Porto Alegre: Sagra Luzzatto, 2000. 205 p. p. 67;103-105. ISBN 85-241-0593-3