[obm-l] PROBLEMAS DE DECISÃO!

[jorgeluis@xxxxxxxxxxxxx]

Um dos primeiros problemas de decisão que foram formulados foi o décimo problema
de Hilbert, o décimo problema de uma lista que David Hilbert propôs ao Congresso
Internacional de Matemáticos em 1900. O problema consiste em determinar se
existe um algoritmo para decidir se qualquer polinômio P(X1, X2,...,XN) = 0 com
coeficientes inteiros tem ou não soluções inteiras. Quando este problema foi
proposto e por algum tempo depois, o consenso geral era que certamente existia
um algoritmo para este fim, e que o fato de ninguém ainda o ter descoberto só
indicava que ele devia ser difícil. Nos meados da década de 30, resultados como
o do problema da parada para máquinas de Turing começaram a pôr em dúvidas este
palpite. Só nos anos 70, no entanto, foi que o problema foi finalmente
demonstrado como insolúvel.

O problema da parada é determinar se existe um algoritmo para decidir, dada
quaisquer máquina de Turing T e cadeia ALFA, se T, ao ser iniciada em uma fita
contendo ALFA, em algum momento, pára sua execução.

NOTA: Turing demonstou a indecibilidade do problema da parada no fim da década
de 30.

Abraços!



______________________________________________
WebMail UNIFOR - http://www.unifor.br.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================