Saltar para o conteúdo

Máquina de Post

Origem: Wikipédia, a enciclopédia livre.

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.

Uma máquina de Post simples

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

[editar | editar código-fonte]

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 (para).

Exemplo: Computação de sequências Collatz

[editar | editar código-fonte]

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.

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 | editar código-fonte]

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 {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 | editar código-fonte]

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: ijXXPi 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 | editar código-fonte]

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 | editar código-fonte]

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.

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 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 | editar código-fonte]

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.

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.

Referências

  1. 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 
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 | editar código-fonte]