Computabilidade

Computabilidade
Introdução:
* Objetivos do estudo da solubilidade de problemas. * Investigar a existência ou não de algoritmos que solucionem determinada classe de problema. * Investigar os limites da computabilidade e, consequentemente, os limites do que pode efetivamente ser implementado em um computador. * Evitar a pesquisa de soluções inexistentes.

* Em 1901, Hilbert formulou uma lista de problemas; * 10º problema: Há um algoritmo que determine se uma equação polinomial, com coeficientes inteiros, possui solução nos inteiros? * 1970 Matijasevic provou ser tal problema sem solução.

* Abordagem * Concentra-se nos problemas com respostas binárias do tipo sim e não (problemas sim/não ou problemas de decisão). * A vantagem de tal abordagem é que a verificação da solucionabilidade de um problema pode ser tratada como a verificação se determinada linguagem é recursiva, associando as condições de ACEITA/REJEITA de uma máquina Universal às respostas sim/não, respectivamente. * A classe dos problemas Solucionáveis é equivalente à Classe das Linguagens Recursivas. * Uma linguagem é dita recursiva se existe uma máquina de Turing tal que:

-ACEITA(M) = L -REJEITA(M) = ∑* - L -LOOP = ø

* A classe das Linguagens Recursivas representa todas as linguagens que podem ser reconhecidas mecanicamente e para as quais existe um reconhecedor que sempre pára para qualquer entrada.

* Problemas não-solucionáveis * Exemplo: Detector universal de Loops. Dados um programa e uma entrada quaisquer, não existe algoritmo genérico capaz de verificar se o programa vai parar ou não vai parar para a entrada. Este problema é universalmente conhecido como o Problema da Parada. * Alguns problemas não-solucionáveis são parcialmente solucionáveis. * Existe um algoritmo capaz de responder sim, embora eventualmente, possa ficar em loop infinito para uma resposta que