En términos de programación informática, Hilbert solicitaba a sus colegas del futuro un algoritmo capaz de admitir como entrada (input) una ecuación diofántica cualquiera, y de devolver SÍ como resultado (output) si la ecuación procesada tenía soluciones en números enteros o NO si la ecuación procesada carecía de soluciones en números enteros.
El problema no se resolvió hasta 70 años después, y en sentido negativo.
[1] Por tanto, Hilbert estaba pidiendo un algoritmo general que decidiera si un polinomio dado de coeficientes enteros —una ecuación diofántica— tenía solución en el dominio de los enteros.
Hoy sabemos que la respuesta es negativa: no existe tal algoritmo general.
[3] Los trabajos de solución del problema casi siempre se han planteado en términos de enteros no negativos o números naturales,
Resulta evidente que los conjuntos diofánticos son, por definición, recursivamente enumerables.
Luego la propia ecuación o sistema que define el conjunto diofántico define el algoritmo que avala la enumerabilidad recursiva del conjunto.
Este resultado se conoce de dos formas: como Teorema de Matiyasevich, porque fue Yuri Matiyasévich el que consiguió el desarrollo final que permitió demostrar el teorema, y como Teorema MRDP, nombre que agrupa a los matemáticos que consiguieron el desarrollo completo, empezando por el citado Matiyasevich, para continuar por Julia Robinson, Martin Davis y Hilary Putnam.
para el que la ecuación tiene soluciones en los números naturales no es computable.
Así pues, no solo no existe un algoritmo general para detectar la resolubilidad de las ecuaciones diofánticas, sino que también puede demostrarse que ni siquiera existe un algoritmo particular para la familia de ecuaciones con un único parámetro.
Formalmente, solo el cuantificador universal estorba para que se considere esto como una definición diofántica de conjuntos.
Dado que los conjuntos recursivamente enumerables tampoco son cerrados para el complemento, Davis conjeturó la identidad de ambas clases.
No tuvo éxito, lo que la condujo a su hipótesis (luego llamada
Quizás la más sorprendente sea la existencia de una ecuación diofántica universal.
Hilary Putnam ha hecho notar que para cada conjunto diofántico
Esto puede verse como sigue: si proporciona una definición diofántica de
, entonces ello basta para fijar Así, por ejemplo, hay un polinomio para el cual la parte positiva de este intervalo son exactamente los números primos (por otro lado, sin embargo, no existe ningún polinomio que devuelva solo números primos).
Además, la afirmación de que algunos sistemas formales, tales como la aritmética de Peano o el sistema ZFC son consistentes puede expresarse como sentencias
Así, si en uno de estos sistemas formales no pueden probarse ni la proposición
tal que la ecuación correspondiente carece de soluciones en los números naturales.
a ese conjunto no-computable, haciendo correr simultáneamente el algoritmo
cada vez que se genere una proposición de la forma Entonces el teorema nos dice que o bien una proposición falsa del sistema será demostrada de esta forma, o bien una verdadera quedará sin demostrar en el sistema en cuestión, lo que demuestra la incompletitud del sistema.
Determinar estos valores máximos ha despertado mucho interés en los matemáticos.
Ya en los años 1920, Thoralf Skolem mostró que cualquier ecuación diofántica es equivalente a una de grado 4 o inferior.
Después, Matiyasevich refinó el método para demostrar que bastaba con 9 incógnitas.
Aunque nadie imagina que este sorprendente resultado sea el mejor posible, no ha habido progresos posteriores[10] Así pues, en particular, no existe ningún algoritmo que pueda probar la resolubilidad en los enteros positivos de ecuaciones diofánticas de 9 incógnitas o menos.
es resoluble en los números racionales negativos si y solo si es resoluble en los números naturales (si se tiene un algoritmo para determinar la resolubilidad en racionales no negativos, podrá usarse fácilmente para determinar la resolubilidad en los racionales).
Sin embargo, el conocimiento de que no existe el algoritmo que reclamaba Hilbert no nos aporta ninguna información sobre otras estructuras.
Shlapentokh y Thanases Pheidas (trabajando independientemente) obtuvieron el mismo resultado para cuerpos algebraicos de números que admitan exactamente un par de encajes complejos conjugados.
Asimismo, y pese a despertar mucho interés, el problema sigue también abierto para las ecuaciones sobre los racionales.