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 ${\displaystyle 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 ${\displaystyle M}$ e a entrada completa. Uma transição de uma configuração ${\displaystyle (S,I)}$ para uma configuração ${\displaystyle (T,J)}$ é permitida se ${\displaystyle I=aJ}$ para algum símbolo de entrada ${\displaystyle a}$ e se ${\displaystyle M}$ tem uma transição de ${\displaystyle S}$ para ${\displaystyle T}$ sob uma entrada ${\displaystyle a}$. A configuração final deve ser a cadeia vazia ${\displaystyle \epsilon }$ como o restante da entrada; o fato de ${\displaystyle 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

${\displaystyle ...0011010101q00110101010...}$

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

Considere uma Máquina de Turing ${\displaystyle M}$ rodando sobre uma entrada ${\displaystyle w}$. A primeira configuração deve ser ${\displaystyle q_{0}w_{0}w_{1}...}$, onde ${\displaystyle q_{0}}$ é o estado inicial da máquina de Turing. O estado da maquina na configuração final deve ser ou ${\displaystyle q_{a}}$ (o estado de aceitação) ou ${\displaystyle q_{r}}$ (o estado de rejeição). Uma configuração ${\displaystyle c_{i+1}}$ é uma sucessão válida da configuração ${\displaystyle c_{i}}$ se há uma transição de estado em ${\displaystyle c_{i}}$ para o estado em ${\displaystyle c_{i+1}}$ que manipula a fita e move a cabeça de leitura/esquita de um modo que produza o resultado em ${\displaystyle 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 ${\displaystyle M}$ sob entrada ${\displaystyle 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 ${\displaystyle c_{0},c_{1},...,c_{n}}$ como a cadeia ${\displaystyle C_{0}\#C_{1}^{r}\#C_{2}\#C_{3}^{r}\#...\#C_{n}}$, onde ${\displaystyle C_{i}}$ é a codificação da configuração ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle ALL_{PDA}}$, a linguagem composta pelos autômatos com pilha que aceitam todas as entradas, é indecidível. Suponhamos que exista um decisor ${\displaystyle D}$ para isso. Para qualquer Máquina de Turing ${\displaystyle M}$ e entrada ${\displaystyle w}$, podemos formar o autômato ${\displaystyle P}$ que aceita históricos de computação de não-aceitação para aquela máquina. ${\displaystyle D(P)}$ aceitará se e somente se não há históricos de computação de aceitação para ${\displaystyle M}$ em ${\displaystyle w}$; isso nos permite decidir ${\displaystyle A_{TM}}$ -- o problema da aceitação em máquinas de Turing--, que já sabemos ser indecidível.

Referências