Equações diofantinas

Um exemplo célebre de problema indecidível:  Dada uma equação polinomial com coeficientes inteiros e um número arbitrário de variáveis  (como  x3yz + 2y4z2 − 7xy5z = 6,  por exemplo)  decidir se existem valores inteiros das variáveis que satisfazem a equação.

Este é o problema das equações diofantinas, ou 10o. problema de Hilbert.  Julia Robinson e Yuri Matiyasevich concluíram em 1970 a prova de que não existe algoritmo algum que resolva o problema em tempo finito.

Valid HTML 4.01 Strict Valid CSS!