Problema indecidible

En teoría de la computabilidad y en teoría de la complejidad computacional, un problema indecidible es un problema de decisión para el cual es imposible construir un algoritmo que siempre conduzca a una respuesta de sí o no correcta. El problema de la parada es un ejemplo: no existe algoritmo que determine de manera correcta si un programa arbitrario se detendrá, una vez sea ejecutado...

Un problema de decisión es cualquier pregunta arbitraria de sí o no en un conjunto infinito de entradas. Por ello es tradicional definir el problema de decisión como equivalente al conjunto de entradas para las que el problema retorna sí. Estas entradas pueden ser números naturales, o bien valores de otro tipo, tales como cadenas de un lenguaje formal.

Mediante alguna codificación, tal como una numeración de Gödel, las cadenas se pueden codificar como números naturales. Así, un problema de decisión informalmente expresado en términos de un lenguaje formal es también equivalente a un conjunto de números naturales. Para mantener simple la definición formal, se expresa en términos de subconjuntos de los números naturales.

Formalmente, un problema de decisión es un subconjunto de los números naturales. El problema informal correspondiente consiste en decidir si un número dado está en el conjunto. A un problema de decisión A, si A es un conjunto recursivo, se le denomina decidible, o efectivamente solucionable. Si A es un conjunto recursivamente enumerable, el problema es parcialmente decidible, semidecidible, solucionable, o demostrable. A problemas parcialmente decidibles y a los no decidibles se les califica de indecidibles.

Para demostrar que un problema es indecidible, generalmente se toma un problema que ya se ha demostrado que lo es y se construye una transformación que lo reduce a una instancia del nuevo problema. Se concluye que no puede existir un algoritmo para decidir sobre el nuevo problema dado que ese algoritmo serviría también para decidir sobre un problema conocido como indecidible.

Ejemplos de problemas indecidibles

Existe una infinidad de problemas indecidibles, por lo que cualquier lista de problemas indecidibles es necesariamente incompleta.

En lógica

• Inferencia y verificación de tipos en lógica de segundo orden.
• El Entscheidungsproblem de Hilbert.

Máquinas abstractas

• Problema de parada (determinar si una máquina de Turing se detiene en una entrada dada) y el problema de mortalidad (determinando si se detiene para cada configuración de partida).
• Determinar si una máquina de Turing es campeón del juego del castor ocupado (es decir, es el más largo entre las máquinas de Turing de detención con el mismo número de estados).
• El Teorema de Rice afirma que, para todas las propiedades no triviales de las funciones parciales, es indecidible si una máquina determinada calcula una función parcial con esa propiedad.

Matrices

• Problema de la matriz mortal: determinar, dado un conjunto finito de n × n matrices con entradas enteras, si se pueden multiplicar en algún orden, posiblemente con repetición, para obtener la matriz cero. Esto se sabe que es indecidible para un conjunto de seis o más matrices 3 × 3, o un conjunto de dos matrices 15 × 15..
• Determinar si un conjunto finito de matrices 3 × 3 triangulares superiores con entradas enteras no negativas genera un semigrupo libre.

Física cuántica

• La existencia de una brecha espectral de un material cuántico​

Teoría combinatoria de grupos

• El problema de la conjugación.
• El problema del isomorfismo grupal.
• Problemas de topología
• Determinar si dos complejos simpliciales finitos son homeomorfos.
• Determinar si un complejo simplicial finito es (homeomorfo a) un colector.
• Determinar si el grupo fundamental de un complejo simplicial finito es trivial.

Otros problemas

• El problema de Correspondencia de Post.
• El problema de determinar si un conjunto dado de azulejos de Wang puede alicatar el plano.
• El problema de si un sistema de etiquetas se detiene.
• El problema de determinar la complejidad de Kolmogorov de una cadena.
• El décimo problema de David Hilbert: el problema de decidir si una ecuación diofántica (ecuación polinomial multivariable) tiene una solución en números enteros.
• Determinar si una gramática sin contexto genera todas las cadenas posibles, o si es ambigua.
• Dadas dos gramáticas sin contexto, determinar si generan el mismo conjunto de cadenas, o si se genera un subconjunto de las cadenas generadas por el otro, o si hay alguna cadena en absoluto que ambos generan.

Véase también

• Entscheidungsproblem

Bibliografía

• Rajeev Motwani y Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación. 
• Elisa Viso. Introducción a la Teoría de la Computación. 

Enlaces externos

• Datos: Q3502995