Vamos descrever agora uma demonstração
de um dos mais famosos teoremas em ciência da computação. Mostraremos que há um
problema que não pode ser resolvido usando-se qualquer procedimento. Ou seja,
mostraremos que há problemas que não podem ser resolvidos. O problema que
estudaremos é o problema de parada. Ele pergunta se há um procedimento que faça
isto: Ele toma como uma entrada um programa de computação e determina se ele
irá parar eventualmente quando essa entrada estiver sendo executada. Seria
conveniente ter tal procedimento, se ele existisse. Certamente, seríamos
capazes de testar, ao escrever, se um problema entra em um laço infinito e
acabaríamos com tais defeitos dos programas. Entretanto em 1936, Alan Turing
mostrou que não existe procedimento que cumpra tal objetivo.
Antes de apresentarmos uma
demonstração de que o problema da parada não pode ser resolvido, note que não
podemos simplesmente executar um programa e observar o que ele faz para
determinar se finalizará quando executa com a entrada dada. Se o programa
parar, nós temos nossa resposta, mas se ele continuar rodando ainda depois de
fixado qualquer espaço de tempo, não sabemos se nunca irá parar ou se apenas
não esperou o tempo suficiente para finalizar. Afinal, não é difícil criar um
programa que irá parar apenas depois de bilhões de anos.
Vamos descrever a demonstração de
Turing de que o problema da parada não pode ser resolvido; é um demonstração
por contradição.
Demonstração: Suponha que haja uma
solução para o problema da parada, um procedimento chamado de H(P,I). Esse procedimento tem duas
entradas, uma, um programa P e a
outra, I, uma entrada para o programa
P.H(P,I) constrói a sequencia “pára”
como a saída se H determinar que P deve parar quando for dada I como entrada. Caso contrário, H(P,I) constrói a sequencia “laço
infinito” como saída. Vamos derivar uma contradição.
Quando um procedimento é codificado,
é expresso como uma sequência de caracteres; esta sequência pode ser
interpretada como uma sequência de bits. Isto significa que um programa pode
ser usado como dado. Então, ele pode ser pensado como uma entrada para outro
programa, ou mesmo para ele próprio. Assim, H
pode ser considerado como um programa
P como suas entradas, que são um programa e a entrada para este programa. H deveria ser capaz de determinar se P irá parar quando for dada uma cópia
dele mesmo como entrada.
Para mostrar que não existe o
procedimento H que resolva o problema
de parada, construímos um procedimento simples K(P), que funciona fazendo uso da saída H(P,P). Se a saída de H(P,P)
é um “laço infinito”, o que significa que P
entra em laço eternamente quando é dada uma cópia dele mesmo como entrada,
então K(P) pára. Se a saída de H(P,P) é “pára”, o que significa que Ppára quando é dada uma cópia dele mesmo
como entrada, então K(P) entra em
laço infinito. Ou seja, K(P) faz o
oposto do que especifica a saída de H(P,P).
Agora suponha que nós fornecemos K como entrada para K. Notamos que se a saída de H(K,K)
é o “laço infinito”, então, pela definição de K, vemos que K(K) pára.
Por outro lado, se a saída de H(K,K) é
“pára”, então, pela definição de K,
vemos que K(K)continua em laço
infinito, ao contrário do que H nos
diz. Nos dois casos temos uma contradição.
Então, H não pode dar as respostas corretas
sempre. Consequentemente, não há procedimento que resolva o problema de parada.
Figura 1:
Mostra que o Problema da Parada não tem solução
Problema de Parada