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.
Exemplo editar
Definição editar
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 sejaproduzida 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 editar
Isto é meremente 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 (para).
Exemplo: Computação de sequências Collatz editar
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áquna 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
(para)
Turing-completude de Máquinas de Post-# editar
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ásquina de Post-#. Por exemplo, Rogozhin 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, 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 editar
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 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 editar
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 editar
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 sequênciais, 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 editar
Máquinas de Post Cíclicas
Produções: (010, 000, 1111)
Computação
Palavra inicial: 11001
Producã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 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 editar
Uma Máquina de Post-#com o alfabeto {a1, ..., an} e as respectivas produções {D1, ..., Dn} é simulada por uma Máquinas 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, 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):
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, 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 editar
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 (para)
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 editar
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 editar
- 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)