Computabilidade

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (922 palavras )
  • Download(s) : 0
  • Publicado : 17 de junho de 2012
Ler documento completo
Amostra do texto
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.
* Investigaros 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, Hilbertformulou 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 sertal 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 é quea 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 àsrespostas 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 talque:

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

* A classe das Linguagens Recursivas representa todas as linguagens que podem serreconhecidas 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 umprograma 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 daParada.
* 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...
tracking img