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[1]. 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 auxiliar. 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 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. 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 existente 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 subconjunto 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.
Máquina de Post-2
Alfabeto: {a,b,c,H}
Regras de produção:
a =-> ccbaH
b =-> cca
c =-> cc
Computação
Palavra inicial: baa
acca
caccbaH
ccbaHcc
baHcccc
Hcccccca
Exemplo: Computação de sequências Collatz
Esta simples Máquina de Post-2 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 é n/2 (para n par) ou 3n + 1 (para n ímpar). O valor 3n + 1 é claramente par 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.
Máquina de Post-2
Alfabeto: {a,b,c}
Regras de produção:
a =-> bc
b =-> a
c =-> aaa
Computação
Palavra inicial: aaa <=-> n=3
abc
cbc
caaa
aaaaa <=-> 5
aaabc
abcbc
cbcbc
cbcaaa
caaaaaa
aaaaaaaa <=-> 8
aaaaaabc
aaaabcbc
aabcbcbc
bcbcbcbc
bcbcbca
bcbcaa
bcaaa
aaaa <=-> 4
aabc
bcbc
bca
aa <=-> 2
bc
a <=-> 1
Turing-completude de Máquinas de Post-#
Para cada # > 1, o conjunto de Máquinas de Post-# é Turing-completude. 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, em 1963 e por Cocke e Minsky, em 1964.
Uma Máquina de Turing pode ser universal provando-se que ela pode simular uma classe de Turing-completo de Máquina de Post-#. Por exemplo, Rogozhin, em 1996, provou a universalidade da classe das Máquinas de Post-2 com o alfabeto {a1, ..., an, H} e as correspondentes produções {ananW1, ..., ananWn-1, anan, H}, onde as Wk são palavras não vazias. Ele então provou a universalidade de uma Máquina de Turing muito pequena (4 estados e 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 de decisão:
Dado um inteiro positivo arbitrário n e uma lista de n+1 palavras arbitrárias P1,P2,...,Pn,Q sob o alfabeto {1,2,...,n}, pergunta-se: A aplicação repetida da operação t: ijX → XPi converterá eventualmente Q em uma palavra de tamanho menor que 2? Isto é, a sequência Q, t1(Q), t2(Q), t3(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 onde a palavra se torna vazia.
Exemplo
Máquinas de Post Cíclicas
Produções: (010, 000, 1111)
Computação
Palavra inicial: 11001
Produção Palavra
---------- --------------
010 11001
000 1001010
1111 001010000
010 01010000
000 1010000
1111 010000000
010 10000000
. .
. .
Máquinas de Post cíclicas foram criadas por Matthew Cook e foram usadas em sua demonstração, a qual 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 {a1, ..., an} e as respectivas produções {D1, ..., Dn} é simulada por uma Máquina de Post cíclica com n produções (Q1, ..., Qn, -, -, ..., -), onde todas, além das primeiras n produções, são a palavra vazia (denotada por '-'). As Qk são codificações da respectiva Qk, obtidas 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 uma máquina de Post):
a1 = 100...00 a2 = 010...00 . . . an = 000...01
Isto é, ak é codificado como a cadeia binária com um 1 na posição k a partir da esquerda e 0 nos outros lugares. Sucessivas linhas de computação de máquinas de Post ocorrerão codificadas em cada 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.
Máquina de Post-2
Regras de produção: (a =-> bb, b =-> abH, H =-> H) Codificações do alfabeto: a = 100, b = 010, H = 001 Codificações da produção: (bb = 010 010, abH = 100 010 001, H = 001)
Máquina de Post Cíclica
Produções: (010 010, 100 010 001, 001, -, -, -)
Computação por Máquina de Post
Palavra inicial: ba
abH
Hbb
Computação por Máquina de Post Cíclica
Palavra inicial: 010 100 (=ba)
Produção Palavra ---------- ------------------------------- * 010 010 010 100 (=ba) 100 010 001 10 100 001 0 100 100 010 001 - 100 100 010 001 - 00 100 010 001 - 0 100 010 001 * 010 010 100 010 001 (=abH) 100 010 001 00 010 001 010 010 001 0 010 001 010 010 - 010 001 010 010 - 10 001 010 010 - 0 001 010 010 * 010 010 parada simulada=-> 001 010 010 (=Hbb) 100 010 001 01 010 010 001 1 010 010 - 010 010 001 ... ...
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.
Ver também
Referências
- ↑ DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth; ERLANG, Rodrigo (2000). Teoria da Computação. Máquinas Universais e Computabilidade 2ª ed. Porto Alegre: Sagra Luzzatto. p. 67;103-105. 205 páginas. ISBN 85-241-0593-3
- Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15-20, 1964.
- De Mol, L.: "Tag systems and Collatz-like functions", Theoretical Computer Science , 390:1, 92-101, January 2008. (Preprint Nr. 314.)
- Marvin Minsky 1961, Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines", the Annals of Mathematics, 2nd ser., Vol. 74, No. 3. (Nov., 1961), pp. 437–455. Stable URL: http://links.jstor.org/sici?sici=0003-486X%2819611%292%3A74%3A3%3C437%3ARUOPPO%3E2.0.CO%3B2-N.
- Marvin Minsky, 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewoord Cliffs, N.J., no ISBN, Library of Congress Card Catalog # 67-12342.
- In a chapter 14 titled "Very Simple Bases for Computability", Minsky presents a very readable (and exampled) subsection 14.6 The Problem of "Tag" and Monogenic Canonical Systems (pp. 267-273) (this sub-section is indexed as "tag system"). Minsky relates his frustrating experiences with the general problem: "Post found this (00, 1101) problem "intractable," and so did I, even with the help of a computer." He comments that an "effective way to decide, for any string S, whether this process will ever repeat when started with S" is unknown although a few specific cases have been proven unsolvable. In particular he mentions Cocke's Theorem and Corollary 1964.
- Post, E.: "Formal reductions of the combinatorial decision problem", American Journal of Mathematics, 65 (2), 197-215 (1943). (Tag systems are introduced on p. 203ff.)
- Rogozhin, Yu.: "Small Universal Turing Machines", Theoret. Comput. Sci. 168, 215-240, 1996.
- Wang, H.: "Tag Systems and Lag Systems", Math. Annalen 152, 65-74, 1963.
Ligações externas
- http://mathworld.wolfram.com/TagSystem.html
- http://mathworld.wolfram.com/CyclicTagSystem.html
- http://www.wolframscience.com/nksonline/page-95 (máquinas de Post cíclicas)
- http://www.wolframscience.com/nksonline/page-669 (simulação de máquinas de Post)