Máquina de Turing não determinística

Máquina de Turing
Máquina
Máquina de Turing universal Máquina de Turing alternada Máquina de Turing quântica Máquina de Turing não determinística Máquina de Turing somente de leitura Máquina de Turing movimentação à direita Máquina de Turing probabilística Máquina de Turing multifita Máquina de Turing de Várias Faixas Máquinas de Turing equivalentes Exemplos de Máquinas de Turing
Ciência
Alan Turing Categoria:Máquina de Turing

Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.

Descrição

Uma máquina de Turing comum (determinística) possui uma função de transição que, dado um estado e um símbolo na posição de execução da fita, especifica três coisas: um novo símbolo a ser escrito na posição de execução da fita, a direção para o qual a fita deve mover-se e um novo estado para o controle finito. Por exemplo, um X na fita no estado 3 pode fazer a máquina determinística escrever um Y na fita, mover a cabeça uma posição para a direita e mudar para o estado 5.

Uma máquina de Turing Não-Determinística difere-se pois um estado e um símbolo de fita não mais definem estas três coisas de forma única - mais de uma ação pode ser aplicável dado um estado e um símbolo.

Como uma máquina Não-Determinística "sabe" qual dessas ações ela deve tomar? Há duas maneiras de olhar esta questão. Uma é supor que a máquina sempre escolherá uma transição que eventualmente leve a um estado de aceitação. A outra maneira é imaginar que a máquina se ramifica em muitas cópias, cada qual leva a diferentes possíveis transições. Onde uma Máquina de Turing Determinística possui um único "caminho de computação" a ser seguido, uma Máquina de Turing Não-Determinística possui uma "árvore de computação". Se qualquer ramo da árvore pára em uma condição de aceitação, dizemos que a Máquina de Turing Não-Determinística aceita a entrada.

Definição

Mais formalmente, uma Máquina de Turing Não-Determinística é uma 6-tupla $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$, onde

• $Q$ é um conjunto finito de estados
• $\Sigma$ é um conjunto finito de símbolos (o alfabeto da fita)
• $\iota \in Q$ é o estado inicial
• $\sqcup$ é o símbolo "branco" ($\sqcup \in \Sigma$)
• $A\subseteq Q$ é o conjunto de estados de aceitação
• $\delta :Q\backslash A\times \Sigma \rightarrow \left(Q\times \Sigma \times \{L,R\}\right)$ é uma função multivalorada sobre estados e símbolos chamada função de transição, onde L é o deslocamento à esquerda e R é o deslocamento à direita. Em Máquinas de Turing convencionais a função de transição não é multivalorada.

Variações

Há um número considerável de variações nessa definição. O estado inicial pode ser substituído por um conjunto de estados iniciais, por exemplo. (Isto é equivalente, pois é trivial simular estados iniciais múltiplos adicionando um único estado inicial que escolhe não deterministicamente quais dos múltiplos estados iniciais anteriormente definidos a máquina usará para continuar.)

A variação pode também incluir um conjunto de estados de rejeição, e neste caso diz-se que a Máquina de Turing Não-Determinística rejeita a entrada se a computação leva a um dos estados de rejeição.

Equivalência com uma Máquina de Turing Determinística

É possível simular qualquer Máquina de Turing não-determinística N com uma MT determinística D. A ideia por trás é fazer com que D tente todos os ramos da computação não-determinística de N. Se em algum momento D encontra o estado de aceitação em algum desses ramos, D aceita. Caso contrário, a simulação de D não terminará.

Vemos a computação de N sobre uma entrada w como uma árvore. Cada ramo da árvore representa um dos ramos do não-determinismo. Cada nó da árvore é uma configuração de N. A raiz da árvore é a configuração inicial. A MT D busca nessa árvore uma configuração de aceitação. Projetamos D para explorar a árvore usando busca em largura. Essa estratégia explora todos os ramos na mesma profundidade antes de continuar a explorar qualquer ramo da próxima profundidade. Esse método garante que D visitará todo nó na árvore até que ela encontre uma configuração de aceitação.

Prova

A MT determinística simuladora D tem três fitas. A fita 1 sempre contém a cadeia de entrada e nunca é alterada. A fita 2 mantém uma cópia da fita de N em algum ramo de sua computação não-determinística. A fita 3 mantém o registro da posição de D na árvore de computação não-determinística de N.

Vamos primeiro considerar a representação de dados na fita 3. Todo nó na árvore pode ter no máximo b filhos, onde b é o tamanho do maior conjunto de possíveis escolhas dado pela função de transição de N. Cada nó na árvore associamos um endereço que é uma cadeia sobre o alfabeto $\Sigma$_b = {1, 2, 3, ..., b}. Associamos o endereço 231 ao nó ao qual chegamos iniciando na raiz, indo para seu segundo filho, indo para o terceiro filho desse nó, e, finalmente, para o primeiro filho desse nó. Cada símbolo na cadeia nos diz que escolha fazer a seguir quando simulamos um passo em um ramo da computação não-determinística de N. Às vezes, um símbolo pode não corresponder a nenhuma escolha (a função de transição que, do nó pai, chega ao filho em questão não existe). Nesse caso, endereço é invalido e não corresponde a nenhum nó. Exemplificando melhor a busca em largura, tendo uma configuração de terceira fita 231 e o terceiro filho do segundo filho da raiz (23) com 4 filhos, teríamos as seguintes configurações: 231, 232, 233 e 234. A cadeia vazia representa a raiz.

Agora estamos prontos para descrever D.

1. Inicialmente, a fita 1 contém a entrada w e as fitas 2 e 3 estão vazias.
2. Copie a fita 1 para a fita 2 (isto garante que cada ramo sempre teste a configuração inicial da fita).
3. Use a fita 2 para simular N com a entrada w sobre um ramo de sua computação não-determinística, Antes de cada passo de N, consulte o próximo símbolo da fita 3 para determinar qual escolha fazer entre aquelas permitidas pela função de transição de N. Se não restam mais símbolos na fita 3 ou se essa escolha não-determinística for inválida, aborte esse ramo indo para o estágio 4. Também vá para o estágio 4 se uma configuração de rejeição for encontrada. Se uma configuração de aceitação for encontrada, aceite a entrada.
4. Substitua a cadeia da fita 3 pela próxima cadeia na ordem lexicográfica. Simule o próximo ramo da computação de N indo para o estágio 2.

Bibliografia

• 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.