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 , 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 e a entrada completa. Uma transição de uma configuração para uma configuração é permitida se para algum símbolo de entrada e se tem uma transição de para sob uma entrada . A configuração final deve ser a cadeia vazia como o restante da entrada; o fato de 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

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

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

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 sob entrada é 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 como a cadeia , onde é a codificação da configuração , 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 . 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 . 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 , a linguagem composta pelos autômatos com pilha que aceitam todas as entradas, é indecidível. Suponhamos que exista um decisor para isso. Para qualquer Máquina de Turing e entrada , podemos formar o autômato que aceita históricos de computação de não-aceitação para aquela máquina. aceitará se e somente se não há históricos de computação de aceitação para em ; isso nos permite decidir -- 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.