Histórico de computação

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na ciência da computação, um histórico de computação é um conjunto de passos tomados por um Autômato enquanto computa seu resultado. Históricos de computação são frequentemente usados em provas sobre as capacidades de determinadas máquinas, e particularmente sobre a indecidibilidade de várias linguagens formais.

Formalmente, um histórico de computação é uma sequência (normalmente finita) de configurações de um autômato formal. Cada configuração descreve completamente o estado da máquina em um ponto específico. Para ser considerado válido, certas condições devem ser preenchidas:

  • a primeira configuração deve ser uma configuração inicial válida do autômato e
  • cada transição entre configurações adjacentes deve ser válida de acordo com as regras de transição do autômato.

Adicionalmente, para ser considerado completo, um histórico de computação deve ser finito e

  • a última configuração deve ser uma configuração final (i.e aceitação ou rejeição) válida do autômato.

As definições de "configuração inicial válida", "transição válida" e "configuração final válida" variam de acordo com o tipo de autômato formal.

Um autômato determinístico tem exatamente um histórico de computação para uma dada configuração inicial, muito embora o histórico possa ser infinito e portanto incompleto.

Máquinas de estados finitos[editar | editar código-fonte]

Para uma máquina de estados finitos M, uma configuração é simplesmente o estado atual da máquina, juntamente com o restante da entrada. A primeira configuração deve ser o estado inicial de M e a entrada completa. Uma transição de uma configuração (S,I) para uma configuração (T,J) é permitida se I=aJ para algum símbolo de entrada a e se M tem uma transição de S para T sob uma entrada a. A configuração final deve ser a cadeia vazia \epsilon como o restante da entrada; o fato de M aceitar ou rejeitar a entrada depende do fato de o estado final ser um estado de aceitação.

Máquinas de Turing[editar | editar código-fonte]

Históricos de computação são mais comumente usados em referência a máquinas de turing. A configuração de uma Máquina de Turing de uma única fita consiste no conteúdo da fita, a posição da cabeça de leitura/escrita e o estado atual da máquina de estados associada; isso geralmente é escrito na forma

...0011010101q00110101010...

onde q é o estado atual da máquina, representado de uma forma de possível distinção da linguagem da fita, e onde q é posicionado imediatamente antes da posição da cabeça de leitura/escrita.

Considere uma Máquina de Turing M rodando sobre uma entrada w. A primeira configuração deve ser q_0 w_0 w_1 ..., onde q_0 é o estado inicial da máquina de Turing. O estado da maquina na configuração final deve ser ou q_a (o estado de aceitação) ou q_r (o estado de rejeição). Uma configuração c_{i+1} é uma sucessão válida da configuração c_i se há uma transição de estado em c_i para o estado em c_{i+1} que manipula a fita e move a cabeça de leitura/esquita de um modo que produza o resultado em c_{i+1}.

Resultados em decidibilidade[editar | editar código-fonte]

Históricos de computação podem ser usados para mostrar que certos problemas para autômatos com pilha são indecidíveis. Isso se dá porque a linguagem de históricos de computação de não-aceitação de uma máquina de Turing M sob entrada w é uma linguagem livre de contexto reconhecível por um autômato com pilha não-determinístico.


Codifica-se um histórico de computação c_0,c_1,...,c_n como a cadeia C_0 \# C^r_1 \# C_2 \# C^r_3 \# ... \# C_n, onde C_i é a codificação da configuração c_i, como discutido anteriormente, e onde cada outra configuração é escrita ao contrário. Antes de ler uma determinada configuração, o autômato faz uma escolha não-determinística a respeito de ou ignorar a configuração ou então lê-la completamente para a pilha.

  • Se o autômato com pilha decide ignorar a configuração, ele simplesmente a lê e a descarta completamente e então escolhe novamente para a próxima.
  • Se, ao contrário, decide processar a configuração, ele a coloca completamente na pilha, depois verifica se a próxima configuração é uma sucessora válida de acordo com as regras de transição de M. Já que configurações sucessivas são sempre escritas em ordens opostas, isso pode ser feito desempilhando um símbolo da pilha, para cada símbolo da fita na nova configuração, e verificando se eles são equivalentes. Trechos diferentes devem corresponder a uma transição válida de M. Se, em qualquer ponto, o autômato decide que a transição é inválida, ele imediatamente entra em um estado de aceitação especial que ignora todo o resto da entrada e por fim aceita.

Adicionalmente, o autômato verifica se a primeira configuração é a configuração inicial correta (se não, ele aceita) e se a configuração final do histórico de computação é o estado de aceitação (se não, ele aceita). Já que um autômato não-determinístico aceita se há alguma configuração válida de aceitação em qualquer um dos ramos de computação, o autômato descrito aqui irá descobrir se o histórico de computação é ou não um histórico válido de aceitação, e irá aceitá-lo ou rejeitá-lo de acordo.

A mesma técnica não pode ser utilizada para reconhecer históricos de computação de aceitação com um autômato com pilha não-determinístico, uma vez que não-determinismo poderia ser utilizado para pular um teste que poderia resultar em falha. Uma máquina de Turing linearmente limitada é suficiente para reconhecer históricos de computação de aceitação.

O resultado nos permite provar que ALL_{PDA}, a linguagem composta pelos autômatos com pilha que aceitam todas as entradas, é indecidível. Suponhamos que exista um decisor D para isso. Para qualquer Máquina de Turing M e entrada w, podemos formar o autômato P que aceita históricos de computação de não-aceitação para aquela máquina. D(P) aceitará se e somente se não há históricos de computação de aceitação para M em w; isso nos permite decidir A_{TM} -- o problema da aceitação em máquinas de Turing--, que já sabemos ser indecidível.

Referências[editar | editar código-fonte]

  • Michael Sipser. Introdução à Teoria da Computação. Tradução brasileira de "Introduction to the Theory of Computation" (PWS Publishing Company, 2nd edition, 2005), por Ruy de Queiroz, revisão Newton Vieira, Cengarle Learning, 2007 ISBN 978-85-221-0499-4.
  • Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111-174.