Problema indecidible

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 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 parada es un ejemplo: se puede demostrar que no existe ningún algoritmo que determine correctamente si un programa arbitrario finalmente se detiene al ejecutarse. ^{[ 1 ]}

Un problema de decisión es una pregunta que, para cada entrada en un conjunto infinito de entradas, requiere una respuesta de "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 . Para problemas de decisión sobre números naturales, el conjunto está formado por aquellos números a los que el problema responde afirmativamente. Por ejemplo, el problema de decisión "¿es par la entrada?" se formaliza como el conjunto de los números pares. Un problema de decisión cuya entrada consiste en cadenas de caracteres 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 resoluble si el conjunto formalizado de A es un conjunto recursivo . En caso contrario, A se denomina indecidible. Un problema se denomina parcialmente decidible, semidecidible, resoluble o demostrable si A es un conjunto recursivamente enumerable . ^{[ nb 1 ]}

En la teoría de la computabilidad , el problema de la parada es un problema de decisión que se puede enunciar de la siguiente manera:

Dada la descripción de un programa arbitrario y una entrada finita, decida si el programa termina de ejecutarse o se ejecutará indefinidamente.

En 1936, Alan Turing demostró que un algoritmo general que se ejecute en una máquina de Turing y que resuelva el problema de la parada para todos los pares posibles de programa-entrada no puede existir necesariamente. Por lo tanto, el problema de la parada es indecidible para las máquinas de Turing.

Los conceptos planteados por los teoremas de incompletitud de Gödel son muy similares a los del problema de la parada, y las demostraciones son bastante parecidas. De hecho, una forma más débil del Primer Teorema de Incompletitud es una consecuencia directa de la indecidibilidad del problema de la parada. Esta forma más débil se diferencia del enunciado estándar del teorema de incompletitud al afirmar que es imposible una axiomatización efectiva de los números naturales que sea a la vez completa y sólida . La parte de "sólida" es el debilitamiento: implica que exigimos que el sistema axiomático en cuestión demuestre únicamente enunciados verdaderos sobre los números naturales. Dado que la solidez implica consistencia , esta forma más débil puede considerarse 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 únicamente por la posibilidad de hallarlo 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 parada de la siguiente manera. ^{[ 3 ]} Supongamos que tenemos una axiomatización efectiva sólida (y por lo tanto consistente) y completa de todas las afirmaciones lógicas de primer orden verdaderas sobre los números naturales . Entonces podemos construir un algoritmo que enumere todas estas afirmaciones. Esto significa que hay un algoritmo N ( n ) que, dado un número natural n , calcula una afirmación lógica de primer orden verdadera sobre los números naturales, y que para todas las afirmaciones verdaderas, hay 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 esta afirmación se puede expresar con una afirmación lógica de primer orden, digamos H ( a , i ). Dado que la axiomatización es completa, se deduce que o bien existe un n tal que N ( n ) = H ( a , i ) o bien existe un n ′ tal que N ( n ′ ) = ¬H ( a , i ). Por lo tanto, si iteramos sobre todos los n hasta encontrar H ( a , i ) o su negación, siempre nos detendremos, y además, la respuesta que nos dé será verdadera (por corrección). Esto significa que esto nos proporciona un algoritmo para resolver el problema de la parada. Dado que sabemos que no puede existir tal algoritmo, se deduce que la suposición de que existe una axiomatización efectiva, completa y correcta de todas las proposiciones verdaderas de lógica de primer orden sobre 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 el uso contemporáneo, el término "indecidible" tiene dos significados distintos. El primero se refiere a una afirmación que no puede ser demostrada ni refutada en un sistema deductivo específico, en relación con los teoremas de Gödel . El segundo significado se relaciona con la teoría de la computabilidad y se aplica no a afirmaciones, sino a problemas de decisión , que son conjuntos infinitos numerables de preguntas, cada una con una respuesta de sí o no. Se dice que un problema es indecidible si no existe una función computable que responda correctamente a todas las preguntas. La conexión entre ambos significados radica en que, si un problema de decisión es indecidible (en el sentido de la teoría de la recursión), entonces no existe un sistema formal consistente y efectivo que demuestre, para cada pregunta A del problema, si "la respuesta a A es sí" o "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 referirse a algo que «ni es demostrable ni refutable». Sin embargo, el uso de «independiente» también es ambiguo. Puede significar simplemente «no demostrable», dejando abierta la posibilidad de que una afirmación independiente pueda ser refutada.

La indecidibilidad de una proposición en un sistema deductivo particular no resuelve, por sí sola, la cuestión de si el valor de verdad de la proposición está bien definido o si puede determinarse por otros medios. La indecidibilidad solo implica que el sistema deductivo en cuestión no prueba la verdad o falsedad de la proposición. La existencia de proposiciones denominadas "absolutamente indecidibles", cuyo valor de verdad nunca puede conocerse o está mal especificado, es un punto controvertido entre diversas escuelas filosóficas .

Uno de los primeros problemas que se sospechaba que eran indecidibles, 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 finitamente presentado para el cual no exista un algoritmo que determine si dos palabras son equivalentes. Esto fue demostrado en 1955 por Sergei Novikov . ^{[ 4 ]}

El trabajo conjunto de Gödel y Paul Cohen ha proporcionado dos ejemplos concretos de enunciados indecidibles (en el primer sentido del término): la hipótesis del continuo no puede probarse ni refutarse en ZFC (la axiomatización estándar de la teoría de conjuntos ), y el axioma de elección no puede probarse ni refutarse en ZF (que incluye todos los axiomas de ZFC excepto el axioma de elección). Estos resultados no requieren el teorema de incompletitud. En 1940, Gödel demostró que ninguno de estos enunciados podía refutarse en la teoría de conjuntos ZF o ZFC. En la década de 1960, Cohen demostró que ninguno de ellos es demostrable a partir de ZF, y que la hipótesis del continuo no puede demostrarse a partir de ZFC.

El Décimo Problema de Hilbert , planteado en 1900 como un desafío para los matemáticos del siglo siguiente, fue demostrado indecidible por Yuri Matiyasevich en 1970. 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 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 a valores enteros de las variables. Matiyasevich demostró que este problema era irresoluble mapeando una ecuación diofántica a un conjunto recursivamente enumerable e invocando el Teorema de Incompletitud de Gödel. ^{[ 5 ]}

En 1936, Alan Turing demostró que el problema de la parada —la cuestión de si una máquina de Turing se detiene o no en un programa dado— es indecidible, en el segundo sentido del término. Este resultado fue generalizado posteriormente por 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 se puede demostrar 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 fuerte 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 formuló 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 una cota superior c tal que 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 de 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 ]}

• Decidibilidad (lógica)
• Problema de decisión
• Prueba de imposibilidad
• Incognoscibilidad
• Problema perverso