En Chaitin's Meta Math! The Quest For Omega , habla brevemente del décimo problema de Hilbert. Luego dice que cualquier ecuación de diofantina se puede cambiar en dos polinomios iguales con coeficientes enteros positivos: .p = 0
Luego dice que podemos pensar en estas ecuaciones como una "computadora":
Computadora de ecuación diofantina : Programa: , Salida: , Tiempo:
Con el lado izquierdo , lado derecho . Él dice que es el programa de esta computadora, que genera . También dice que las incógnitas son una variable de tiempo multidimensional .R k n
Lo que me confunde es que luego dice que el décimo problema de Hilbert claramente no se puede resolver cuando se ve de esta manera. Básicamente dice "debido al problema de detención de Turing". Pero no veo la conexión (apenas estoy empezando a aprender la teoría). Esperaba que alguien pudiera explicar más claramente cuál es el punto de Chaitin aquí.
Sé que el problema de detención de Turing básicamente establece que no se puede predecir cuándo se detendrá un programa antes de que realmente se detenga (dado un tiempo finito). ¿Cuál es la aplicación para el 10º problema de Hilbert, usando la notación presentada por Chaitin?
fuente