En teoría de la computabilidad y teoría de la complejidad computacional , un problema indecidible es un problema de decisión para el cual 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 finalmente se detiene 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 "¿la entrada es un número primo?") u otros 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 . Para los problemas de decisión sobre números naturales, el conjunto consta de aquellos números a los que el problema de decisión responde "sí". Por ejemplo, el problema de decisión "¿La entrada es pareja?" se formaliza como el conjunto de los números pares. Un problema de decisión cuya entrada consta de cadenas o valores más complejos se formaliza como el conjunto de números que, mediante 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 . En caso contrario, A se llama indecidible. Un problema se denomina parcialmente decidible, semidecidible, solucionable o demostrable si A es un conjunto recursivamente enumerable . [nota 1]
En la teoría de la computabilidad , el problema de la detención es un problema de decisión que se puede plantear de la siguiente manera:
Alan Turing demostró en 1936 que no necesariamente puede existir un algoritmo general ejecutado en una máquina de Turing que resuelva el problema de detención para todos los pares posibles de programa-entrada. Por tanto, el problema de la detención es insoluble 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 sólo afirmaciones verdaderas sobre los números naturales. Dado que solidez implica coherencia , 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 sólo se refiere a la cuestión de si es posible encontrarlo mediante una demostración matemática .
La forma más débil del teorema se puede demostrar 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 verdaderos de lógica de primer orden sobre los números naturales . Luego podemos construir un algoritmo que enumere todas estas declaraciones. Esto significa que existe un algoritmo N ( n ) que, dado un número natural n , calcula un enunciado lógico verdadero de primer orden sobre números naturales, y que para todos los enunciados verdaderos, existe al menos un n tal que N ( n ) produce esa afirmación. Ahora supongamos que queremos decidir si el algoritmo con representación a se detiene en la entrada i . Sabemos que este enunciado se puede expresar con un enunciado lógico de primer orden, digamos H ( a , i ). Dado que la axiomatización es completa, se deduce que o hay un n tal que N ( n ) = H ( a , i ) o hay un n ′ tal que N ( n ′ ) = ¬ H ( a , i ). Entonces, si iteramos sobre todo n hasta encontrar 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 detención. Como sabemos que no puede existir tal algoritmo, se deduce que la suposición de que existe una axiomatización consistente y completa de todos los enunciados verdaderos de la lógica de primer orden 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 incontables problemas indecidibles, [nb 2] cualquier lista, incluso una de longitud infinita , es necesariamente incompleta.
Hay dos sentidos distintos de la palabra "indecidible" en el uso contemporáneo. El primero de ellos es el sentido utilizado en relación con los teoremas de Gödel, el de un enunciado que no es 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 contablemente infinitos de preguntas, cada una de las cuales requiere 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 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 efectivo que demuestre para cada pregunta A del problema "la respuesta a A es sí" o "la respuesta a A es sí". 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 en el sentido de "ni demostrable ni refutable". Sin embargo, el uso de "independiente" también es ambiguo. Puede significar simplemente "no demostrable", dejando abierto si una declaración independiente podría ser refutada.
La indecidibilidad de un enunciado en un sistema deductivo particular no aborda, en 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 cuestión de si existen afirmaciones llamadas "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 sospechosos de ser indecidibles, en el segundo sentido del término, fue el problema verbal para grupos , planteado por primera vez por Max Dehn en 1911, que pregunta si existe un grupo presentado finitamente para el cual no existe ningún algoritmo para determinar si dos palabras son equivalentes. Este fue el caso en 1952.
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 La elección no se puede probar ni refutar 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 ninguna de estas afirmaciones podía ser refutada en la teoría de conjuntos ZF o ZFC. En la década de 1960, Cohen demostró que ninguna de las dos cosas es demostrable a partir de ZF y que la hipótesis del continuo no puede demostrarse 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 para el 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. Como tenemos una sola 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 se limitan únicamente a valores enteros. Matiyasevich demostró que este problema no tiene solución al asignar una ecuación diofántica a un conjunto recursivamente enumerable e invocar el teorema de incompletitud de Gödel. [4]
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 posteriormente generalizado 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. [5]
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 se puede demostrar que es cierto 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 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 afirmaciones indecidibles en la teoría algorítmica de la información 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 en esa teoría no se puede demostrar que ningún número específico 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. [6]
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. [7] [8]
