Eis 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.