Filtering effects

Vamos começar esta seção falando de uma característica da MTU que criamos antes. O que acontece se a entrada <X,w> descrever uma situação em que a máquina X entra em loop infinito? A MTU vai aceitar ou rejeitar? Como, nesse caso, a MTU apenas simula o comportamento de X (ao receber a cadeia w), vai acontecer com ela exatamente o que aconteceria com X: a MTU vai entrar em loop infinito!

Portanto, podemos descrever de maneira informal o comportamento da MTU assim:

Falar que ela pode entrar em loop...

Explicar o problema da parada (da aceitação?)...

A situação em que a MTU entra em loop não é exatamente um “resultado” que ela retorna, mas é um caso em que ela fica processando indefinidamente e não retorna nenhum resultado (como explicamos na seção 2.2 deste volume). Na verdade, os únicos resultados que desejamos obter da MTU (ou de qualquer MT) são apenas um dos dois: ACEITA ou REJEITA.

A grande questão que queremos discutir nessa seção é se é possível construir alguma MTU que sempre retorne um desses resultados e que nunca entre em loop. Construída da maneira que explicamos na seção anterior, realmente a MTU pode entrar em loop infinito, mas talvez exista outra maneira de construir uma MTU melhorada em que isso não aconteça.

Ao receber uma entrada <<X>,w>, a MTU:

• Aceita, se X aceita w

• Rejeita, se X rejeita w

Para construir essa MTU melhorada, seria preciso lidar com o chamado Problema da Parada:

“Dada uma máquina de Turing X e uma cadeia w, identificar se X vai parar (ou se vai entrar em loop infinito) ao receber a cadeia w”.

Se existir algum algoritmo (ou uma MT) para resolver esse problema, então podemos construir a MTU melhorada usando esse algoritmo como parte dela. A idéia para fazer essa nova MTU seria a seguinte: primeiro, ela testaria se a entrada <X,w> vai parar. Se a resposta for “sim”, ela simularia normalmente a entrada (seguindo a idéia que ensinamos na seção anterior). Se for “não”, ela rejeitaria diretamente essa entrada, sem simular nada.

Veja, que, na verdade, estamos mostrando que as duas questões abaixo estão interligadas:

• Será que temos como construir uma MTU melhorada que nunca entra em loop?

• Será que temos como prever que uma MT vai entrar em loop antes mesmo de simulá-la? (O problema da parada tem solução?)

Se encontrarmos a resposta de uma das duas questões, automaticamente estaremos encontrando a resposta da outra. Se existir uma máquina que decide o problema da parada, então existe uma MTU melhorada que nunca entra em loop e vice-versa. E se não existir uma máquina que decide o problema da parada, também não existe a MTU melhorada!

Infelizmente, não existe solução para o problema da parada e, portanto, a resposta para ambas as perguntas acima é NÃO. O restante desta seção será dedicado a provar isso. Mas como ambas as perguntas são interligadas, vamos provar apenas a primeira delas: vamos provar que não existe a tal “MTU melhorada” que nunca entra em loop!

A demonstração que apresentaremos é o que, na Matemática, se chamada de prova por contradição. Uma prova matemática apresenta argumentos

verdadeira. Na prova por contradição, no entanto, nós começamos assumindo hipoteticamente que a proposição P é falsa. A partir daí, desenvolvemos um raciocínio até chegar em algo matematicamente contraditório. Chegar nesse ponto contraditório significa que assumimos errado no início – ou seja, P só pode ser verdadeira!

No nosso caso, a proposição será que “não existe uma MTU que nunca

entra em loop”. Mas, para provar por contradição, vamos começar assumindo o

contrário:

“Existe uma MTU que nunca entra em loop”

A partir de agora, nosso objetivo nessa demonstração matemática é mostrar que, se a afirmação acima for verdade, então algumas coisas “sem sentido” também teriam que ser verdade. Chegando nesse ponto, poderemos concluir que a proposição acima é falsa. Por enquanto, vamos prosseguir assumindo que a proposição é verdadeira.

Bem, a afirmação acima nos garante que existe a “MTU melhorada” de que falamos antes. Não sabemos como construí-la, mas, por enquanto, estamos assumindo que ela pode ser construída de alguma maneira. Vamos chamar essa MTU melhorada de M e o seu comportamento seria assim:

Podemos simplificar a descrição dos dois casos de rejeição descrevendo o comportamento da máquina assim:

Ao receber uma entrada <<X>,w>, a máquina M:

• Aceita, se X aceita w

• Rejeita, se X rejeita w

Assim como a MTU, essa máquina M recebe duas entradas codificadas em uma só cadeia: uma máquina de Turing X e uma cadeia w. Como a máquina X também está codificada como cadeia, poderíamos passar ela no lugar da entrada w, assim: <X,<X>>. Nesse caso, estaríamos testando se a máquina X aceita a sua própria descrição <X>. Isso não é nenhum problema, pois <X> é uma cadeia qualquer e pode ser dada como entrada até mesmo para a própria máquina X. O detalhe aqui é que ao invés de fazer isso diretamente, estaríamos simulando essa situação usando M.

Bem, para a nossa prova, será melhor considerar uma máquina à parte que simula essa situação em que X recebe <X>. Essa nova máquina será chamada de Z e queremos que ela receba apenas a descrição <X> de uma MT. Ao receber essa entrada, ela irá operar de maneira similar a M quando recebe <X,<X>>, mas vamos considerar que Z irá retornar o contrário do que M retornaria. Assim, podemos descrever o comportamento de Z da seguinte maneira:

Não dar detalhes maiores da construção de Z, mas, ela pode ser construída a partir M com pequenas alterações. Quer dizer, o que importa para nós é que, se M existe, então Z também existe.

Agora, queremos que você pense na seguinte situação: o que aconteceria Ao receber uma entrada <X,w>, a máquina M:

• Aceita, se X aceita w

• Rejeita, se X não aceita w

Ao receber uma entrada <X>, a máquina Z:

• Rejeita, se X aceita <X>

cadeia <Z>? Qual seria a resposta da máquina? É importante que você reflita por alguns instantes sobre se cada resposta que Z poderia retornar. Pense em se faz sentido dizer que Z retornaria ACEITA e, depois, pense se faz sentido dizer que Z retornaria REJEITA, nesse caso. Se achar necessário, releia a descrição de Z para chegar a alguma conclusão. (Porém, não se demore demais nessa questão porque a resposta, dada abaixo, deve surpreendê-lo).

Se você se esforçou um pouco, deve ter percebido que não é fácil chegar a uma conclusão sobre a resposta que Z retornaria ao receber Z. Na verdade, essa resposta é impossível de ser dada porque cada possível resposta seria contraditória, considerando o propósito da máquina Z. Com base na descrição dada antes, vamos analisar separadamente cada uma das possíveis respostas para você perceber as contradições existentes.

Lembramos que a questão é: o que aconteceria se Z recebesse a entrada <Z>? Podemos substitui a entrada <X> por <Z> na descrição para ver as condições necessárias para a máquina Z dar cada resposta.

Veja que, pela descrição, a resposta seria REJEITA somente “se Z aceita Z”. Quer dizer, a máquina Z rejeitaria <Z>, se ela aceitasse <Z>! Essa é uma condição claramente contraditória do ponto de vista lógico e matemático. A outra possibilidade também levaria a uma contradição: a máquina daria a resposta ACEITA somente “se Z não aceita <Z>”. Mais uma vez temos uma contradição. Resumindo as duas contradições:

• Quando Z recebe <Z>, ela retornaria REJEITA, se Z aceita <Z>.

• Quando Z recebe <Z>, ela retornaria ACEITA, se Z não aceita <Z>.

Quer dizer, a condição para Z dar uma resposta é que ela dê a resposta oposta, o que é uma contradição. O que concluímos é que não pode existir a máquina de Turing Z. Mas nós só imaginamos a máquina Z porque havíamos assumido que havia uma MTU melhorada M que nunca entra em loop. Se Z não existe, somos obrigados a concluir que M não existe e que assumimos uma proposição errada no início. Ou seja, a verdade é que:

Isso significa que o problema da parada (testar se uma máquina X vai parar ao receber uma cadeia w) não tem uma solução. Ou seja, ele é um problema indecidível. Esse é um resultado curioso que mostra uma limitação do modelo Máquinas de Turing. Se na seção anterior, mostramos que esse modelo é poderoso o suficiente para permitir a ele simular a si próprio, nessa seção mostramos que ele não é poderoso o suficiente para decidir todos os problemas imagináveis.

Devido à Tese de Church-Turing, essa limitação das MTs é uma limitação que vale também para qualquer máquina real construída pelo homem, inclusive os computadores mais modernos que existem hoje – nenhum deles é capaz de resolver o problema da parada. Assim como o problema da parada, existem diversos problemas matemáticos que são podem ser decididos por nenhum computador. Outros exemplos desses chamados problemas indecidíveis são:

• Testar se um programa de computador vai entrar em loop infinito. (Similar ao problema da parada).

• Testar se uma linguagem decidida por uma MT pode ser decidida por um AFD.

• Testar se um polinômio de múltiplas variáveis (como: 5x2y3 + 3x2 + y3 - 10) tem raízes inteiras.

É importante não só que você saiba que existem problemas indecidíveis como também que conheça alguns deles. Assim, quando você se deparar com um deles, você não irá perder tempo tentando criar um programa para resolvê- los (afinal de contas, você não conseguiria). Até onde se sabe hoje em dia, esses problemas representam um limite teórico intransponível para a Computação.

Abaixo apresentamos alguns exercícios para ajudar você, aluno, a fixar o assunto.

Questão 1: Não demos detalhes muito profundos da definição da MTU,