En la teoría de la computabilidad y la teoría de la complejidad computacional , un problema indecidible es un problema de decisión para el que se ha demostrado que es imposible construir un algoritmo que siempre conduzca a una respuesta correcta de sí o no. El problema de la detención es un ejemplo: se puede demostrar que no existe ningún algoritmo que determine correctamente si un programa arbitrario se detiene eventualmente cuando se ejecuta. [1]
Un problema de decisión es una pregunta que, para cada entrada en un conjunto infinito de entradas, responde "sí" o "no". [2] Esas entradas pueden ser números (por ejemplo, el problema de decisión "¿es la entrada un número primo ?") o valores de algún otro tipo, como cadenas de un lenguaje formal .
La representación formal de un problema de decisión es un subconjunto de los números naturales . En el caso de los problemas de decisión sobre números naturales, el conjunto está formado por aquellos números a los que el problema de decisión responde "sí". Por ejemplo, el problema de decisión "¿la entrada es par?" se formaliza como el conjunto de números pares. Un problema de decisión cuya entrada consiste en cadenas o valores más complejos se formaliza como el conjunto de números que, a través de una numeración de Gödel específica , corresponden a entradas que satisfacen los criterios del problema de decisión.
Un problema de decisión A se denomina decidible o efectivamente solucionable si el conjunto formalizado de A es un conjunto recursivo . De lo contrario, A se denomina indecidible. Un problema se denomina parcialmente decidible, semidecidible, solucionable o demostrable si A es un conjunto recursivamente enumerable . [nb 1]
En la teoría de la computabilidad , el problema de detención es un problema de decisión que puede enunciarse de la siguiente manera:
En 1936, Alan Turing demostró que no puede existir necesariamente un algoritmo general que funcione en una máquina de Turing y que resuelva el problema de la detención para todos los pares programa-entrada posibles. Por lo tanto, el problema de la detención es indecidible para las máquinas de Turing.
Los conceptos planteados por los teoremas de incompletitud de Gödel son muy similares a los planteados por el problema de la detención, y las demostraciones son bastante similares. De hecho, una forma más débil del Primer Teorema de Incompletitud es una consecuencia fácil de la indecidibilidad del problema de la detención. Esta forma más débil difiere del enunciado estándar del teorema de incompletitud al afirmar que una axiomatización de los números naturales que sea completa y sólida es imposible. La parte "sólida" es el debilitamiento: significa que requerimos que el sistema axiomático en cuestión demuestre solo afirmaciones verdaderas sobre los números naturales. Dado que la solidez implica consistencia , esta forma más débil puede verse como un corolario de la forma fuerte. Es importante observar que el enunciado de la forma estándar del Primer Teorema de Incompletitud de Gödel no se preocupa en absoluto por el valor de verdad de un enunciado, sino que solo se ocupa de la cuestión de si es posible encontrarlo mediante una demostración matemática .
La forma más débil del teorema puede demostrarse a partir de la indecidibilidad del problema de detención de la siguiente manera. [3] Supongamos que tenemos una axiomatización sólida (y, por lo tanto, consistente) y completa de todos los enunciados lógicos de primer orden verdaderos sobre los números naturales . Entonces podemos construir un algoritmo que enumere todos estos enunciados. Esto significa que hay un algoritmo N ( n ) que, dado un número natural n , calcula un enunciado lógico de primer orden verdadero sobre los números naturales, y que para todos los enunciados verdaderos, hay al menos un n tal que N ( n ) produce ese enunciado. Ahora supongamos que queremos decidir si el algoritmo con representación a se detiene en la entrada i . Sabemos que este enunciado puede expresarse con un enunciado lógico de primer orden, digamos H ( a , i ). Como la axiomatización es completa, se deduce que o bien hay un n tal que N ( n ) = H ( a , i ) o bien hay un n ′ tal que N ( n ′ ) = ¬ H ( a , i ). Así que si iteramos sobre todos los n hasta que encontremos H ( a , i ) o su negación, siempre nos detendremos y, además, la respuesta que nos dé será verdadera (por solidez). Esto significa que nos da un algoritmo para decidir el problema de la detención. Como sabemos que no puede haber tal algoritmo, se deduce que la suposición de que hay una axiomatización consistente y completa de todas las afirmaciones lógicas de primer orden verdaderas sobre los números naturales debe ser falsa.
Los problemas indecidibles pueden estar relacionados con diferentes temas, como la lógica , las máquinas abstractas o la topología . Dado que hay una cantidad incontable de problemas indecidibles, [nb 2] cualquier lista, incluso una de longitud infinita , es necesariamente incompleta.
En la actualidad, la palabra "indecidible" tiene dos sentidos distintos. El primero de ellos es el que se utiliza en relación con los teoremas de Gödel, es decir, que un enunciado no es ni demostrable ni refutable en un sistema deductivo específico . El segundo sentido se utiliza en relación con la teoría de la computabilidad y no se aplica a enunciados sino a problemas de decisión , que son conjuntos infinitos de preguntas que requieren una respuesta de sí o no. Se dice que un problema de este tipo es indecidible si no existe una función computable que responda correctamente a todas las preguntas del conjunto de problemas. La conexión entre estos dos sentidos es que, si un problema de decisión es indecidible (en el sentido teórico de la recursión), entonces no existe un sistema formal consistente y eficaz que demuestre para cada pregunta A del problema que "la respuesta a A es sí" o que "la respuesta a A es no".
Debido a los dos significados de la palabra indecidible, a veces se utiliza el término independiente en lugar de indecidible para el sentido de "ni demostrable ni refutable". Sin embargo, el uso de "independiente" también es ambiguo. Puede significar simplemente "no demostrable", lo que deja abierta la posibilidad de que una afirmación independiente pueda ser refutada.
La indecidibilidad de un enunciado en un sistema deductivo particular no resuelve por sí misma la cuestión de si el valor de verdad del enunciado está bien definido o si puede determinarse por otros medios. La indecidibilidad sólo implica que el sistema deductivo particular que se esté considerando no prueba la verdad o falsedad del enunciado. La existencia de los llamados enunciados "absolutamente indecidibles", cuyo valor de verdad nunca puede conocerse o está mal especificado, es un punto controvertido entre varias escuelas filosóficas .
Uno de los primeros problemas que se sospechó que era indecidible, en el segundo sentido del término, fue el problema de las palabras para grupos , planteado por primera vez por Max Dehn en 1911, que pregunta si existe un grupo finito para el cual no existe un algoritmo para determinar si dos palabras son equivalentes. Esto se demostró en 1955. [4]
El trabajo combinado de Gödel y Paul Cohen ha dado dos ejemplos concretos de enunciados indecidibles (en el primer sentido del término): la hipótesis del continuo no puede ser probada ni refutada en ZFC (la axiomatización estándar de la teoría de conjuntos ), y el axioma de elección no puede ser probado ni refutado en ZF (que son todos los axiomas de ZFC excepto el axioma de elección). Estos resultados no requieren el teorema de incompletitud. Gödel demostró en 1940 que ninguno de estos enunciados podía ser refutado en ZF o en la teoría de conjuntos ZFC. En la década de 1960, Cohen demostró que ninguno es demostrable a partir de ZF, y la hipótesis del continuo no puede ser demostrada a partir de ZFC.
En 1970, el matemático ruso Yuri Matiyasevich demostró que el Décimo Problema de Hilbert , planteado en 1900 como un desafío al próximo siglo de matemáticos, no puede resolverse. El desafío de Hilbert buscaba un algoritmo que encontrara todas las soluciones de una ecuación diofántica . Una ecuación diofántica es un caso más general del Último Teorema de Fermat ; buscamos las raíces enteras de un polinomio en cualquier número de variables con coeficientes enteros. Dado que solo tenemos una ecuación pero n variables, existen infinitas soluciones (y son fáciles de encontrar) en el plano complejo ; sin embargo, el problema se vuelve imposible si las soluciones están restringidas solo a valores enteros. Matiyasevich demostró que este problema era irresoluble al mapear una ecuación diofántica a un conjunto recursivamente enumerable e invocar el Teorema de Incompletitud de Gödel. [5]
En 1936, Alan Turing demostró que el problema de la detención (la cuestión de si una máquina de Turing se detiene o no en un programa determinado) es indecidible, en el segundo sentido del término. Este resultado fue generalizado posteriormente mediante el teorema de Rice .
En 1973, Saharon Shelah demostró que el problema de Whitehead en la teoría de grupos es indecidible, en el primer sentido del término, en la teoría de conjuntos estándar. [6]
En 1977, Paris y Harrington demostraron que el principio de Paris-Harrington , una versión del teorema de Ramsey , es indecidible en la axiomatización de la aritmética dada por los axiomas de Peano , pero puede demostrarse que es verdadero en el sistema más amplio de aritmética de segundo orden .
El teorema del árbol de Kruskal , que tiene aplicaciones en informática, también es indecidible a partir de los axiomas de Peano, pero demostrable en la teoría de conjuntos. De hecho, el teorema del árbol de Kruskal (o su forma finita) es indecidible en un sistema mucho más sólido que codifica los principios aceptables sobre la base de una filosofía de las matemáticas llamada predicativismo.
El teorema de Goodstein es una afirmación sobre la teoría de Ramsey de los números naturales que Kirby y Paris demostraron que es indecidible en la aritmética de Peano.
Gregory Chaitin produjo enunciados indecidibles en la teoría de la información algorítmica y demostró otro teorema de incompletitud en ese contexto. El teorema de Chaitin establece que para cualquier teoría que pueda representar suficiente aritmética, existe un límite superior c tal que no se puede demostrar que ningún número específico en esa teoría tenga una complejidad de Kolmogorov mayor que c . Mientras que el teorema de Gödel está relacionado con la paradoja del mentiroso , el resultado de Chaitin está relacionado con la paradoja de Berry .
En 2007, los investigadores Kurtz y Simon, basándose en trabajos anteriores de JH Conway en la década de 1970, demostraron que una generalización natural del problema de Collatz es indecidible. [7]
En 2019, Ben-David y sus colegas construyeron un ejemplo de un modelo de aprendizaje (llamado EMX) y mostraron una familia de funciones cuya capacidad de aprendizaje en EMX es indecidible en la teoría de conjuntos estándar. [8] [9]
