Histórico de computação

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

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

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

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_{1}^{r}\#C_{2}\#C_{3}^{r}\#...\#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.