História de computação

Em ciência da computação, uma história de computação é uma seqüência de passos dados por uma máquina abstrata no processo de computar seu resultado para uma dada entrada. Histórias de computação são freqüentemente usadas em provas matemáticas sobre as capacidades de certas máquinas, e principalmente sobre a indecibilidade de várias linguagens formais.

A história de computação para uma máquina $M$ sobre uma entrada $w$ é simplesmente uma sequência de configurações, $C_{0}C_{1}C_{2}C_{3}...C_{f}$ pelas quais a máquina passa à medida que processa a entrada, onde $C_{0}$ é a configuração inicial de $M$ sobre $w$, $C_{1}$ é a configuração posterior, e assim sucessivamente até chegar na configuração final $C_{f}$.

Cada configuração descreve completamente o estado da máquina em um ponto particular. Ou seja, um histórico de computação é um registro completo da computação dessa máquina. Para ser válido, certas condições precisam ser satisfeitas:

• a primeira configuração,$C_{0}$, precisa ser uma configuração inicial válida da máquina e
• cada transição entre configurações adjacentes precisa ser válida de acordo com as regras de transição da máquina.

Adicionalmente, para ser completa, uma história de computação precisa ser finita e

• a configuração final,$C_{f}$, precisa ser uma configuração final válida da máquina.

As definições de "configuração inicial válida", "transição válida", e "configuração final válida" variam para diferentes tipos de máquinas formais.

Máquinas de estados finitas

Para uma máquina de estados finita $M$, uma configuração é simplesmente o estado atual da máquina, junto com a entrada restante. 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$ com a entrada $a$. A configuração final deve ter a cadeia vazia ε como sua entrada restante. A entrada ser aceita ou não por $M$, depende de se o estado final é um estado de aceitação.

Máquinas de Turing

História de computação são mais comumente usadas em referência a Máquinas de Turing. A configuração de uma Máquina de Turing de fita única consiste do conteúdo da fita, a posição da cabeça de leitura/escrita da fita, e do estado atual da máquina de estados associada; isto é usualmente representado como:

$1011q7011110$, onde para esse exemplo:

• $q7$ é o estado atual,
• $1011011110$ é o conteúdo atual da fita e
• A cabeça de leitura/escrita está sobre o segundo $0$.

Seja $M$ uma máquina de Turing e $w$ uma cadeia de entrada:

• Uma história de computação de aceitação para M sobre w é uma sequência de configurações $C_{0}C_{1}C_{2}C_{3}...C_{f}$, onde $C_{0}$ é a configuração inicial de $M$ sobre $w$, $C_{f}$ é uma configuração de aceitação de $M$, e cada $C_{i}+1$ segue legitimamente de $C_{i}$ conforme as regras de $M$.

• Uma história de computação de rejeição para $M$ sobre $w$ é definida similarmente, exceto que $C_{f}$ é uma configuração de rejeição.

As histórias de computação são sequências finitas. Se $M$ não pára sobre w, nenhuma história de computação de aceitação ou de rejeição existe para M sobre w. As máquinas determinísticas tem no máximo uma história de computação sobre qualquer dada entrada. E as não-determinísticas podem ter muitas histórias de computação sobre uma única entrada, correspondendo aos vários ramos da computação.

Exemplos de histórias de computação

Seja a definição formal de uma máquina de Turing $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{a},q_{r})$, onde:

• $Q$ é um conjunto finito de estados,
• $\Sigma$ é o alfabeto de entrada,
• $\Gamma$ é o alfabeto da fita,
• $\delta :Q\times \Gamma$ ⇒ $Q\times \Gamma \times$ {E,D} a função de transição,
• $q_{0}\in Q$ é o estado inicial,
• $q_{a}\in Q$ é o estado de aceitação,
• $q_{r}\in Q$ é o estado de rejeição.

Agora, vamos simular dois exemplos simples de uma máquina de Turing $M$ sobre duas cadeias $w$ diferentes. Suponha que $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{a},q_{r})$, onde:

• $Q=$ {$q_{0}$, $q_{1}$, $q_{a}$, $q_{r}$}
• $\Sigma$ = {0,1}
• $\Gamma$ = {0,1,b}, onde b representa o símbolo em branco
• $\delta$ representada por:

$\delta$($q_{0}$,0) ⇒ ($q_{1}$, 0, D),

$\delta$($q_{0}$,1) ⇒ ($q_{0}$, b, D),

$\delta$($q_{1}$,1) ⇒ ($q_{r}$, b, D),

$\delta$($q_{1}$,0) ⇒ ($q_{a}$, 0, D).

Para $w$ = 1100, a história de computação dessa máquina seria:
$q_{0}$1100
b$q_{0}$100
bb$q_{0}$00
bb0$q_{1}$0
bb00$q_{a}$
O que consistiria numa história de computação de aceitação.

Para $w$ = 101, a história de computação dessa máquina seria:
$q_{0}$101
b$q_{0}$01
b0$q_{1}$1
b0b$q_{r}$
O que consistiria numa história de computação de rejeição.

Resultados para decibilidade

Histórias de computação podem ser usadas para mostrar que certos problemas para autômatos com pilha são indecidíveis. Isso acontece porque a linguagem que não aceita histórias de computação de uma máquina de Turing $M$ sobre uma entrada $w$ é uma linguagem livre do contexto reconhecida por um autômato com pilha não determinístico.

Nós codificamos a história de computação de uma máquina de Turing $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 foi discutido acima, e onde qualquer outra configuração é escrita ao contrário. Antes de ler uma configuração particular, o autômato com pilha faz uma escolha não-determinística para ou ignorar a configuração ou 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 faz a mesma escolha para a próxima.
• Se ele decide processar a configuração, ele a empurra completamente na pilha, e então verifica se a próxima configuração é uma sucessora válida de acordo com as regras de $M$. Como configurações válidas são sempre escritas em ordem oposta, isso pode ser feito, para cada símbolo novo da fita na nova configuração, retirando o topo da pilha e checando se eles são iguais. Quando eles diferem, deve ser de acordo com uma transição válida de $M$. Se, em eu qualquer ponto, o autômato decide que a transição é inválida, ele imediatamente entra em um estado especial de aceitação

que ignora o resto da entrada e aceita no fim.

Além disso, o autômato verifica se a primeira configuração é a configuração inicial certa (caso não seja, ele aceita) e se o estado da configuração final da história é o estado de aceitação (caso não seja, ele aceita). Como um autômato não-determinístico aceita se existe uma maneira válida para que ele aceite, o autômato descrito aqui descobrirá se a história não é uma história válida de aceitação e aceitará caso não seja, e rejeitará caso contrário.

O mesmo truque não pode ser usado para reconhecer histórias de computação de aceitação para um autômato com pilha não determinístico, pois como o determinismo pode ser usado para pular um teste passado que iria falar caso contrário. Uma máquina de Turing de limite linear, é suficiente para aceitar histórias de computação de aceitação.

Esse resultado permite provar que $ALL_{APD}$, a linguagem de autômatos com pilha que aceitam todas as entradas, é indecidível. Suponha que exista um decisor $D$ para este problema.
Para qualquer máquina de Turing $M$ e entrada $w$, nós podemos formar o autômato com pilha $P$ o qual aceita todas as cadeias que não sejam história de computação para essa máquina.
$D(P)$ aceitará se e somente se não há nenhuma história de computação para essa máquina.
Se esse decisor $D$ realmente existisse, $A_{TM}$ seria decidível. Como $A_{TM}$ é indecidível, $D$ deve ser indecidível.