Problema indecidible

En teoria de la computabilidad y en teoria de la complejidad computacional, un problema indecidible es un problema de decision para el cual es imposible construir un algoritmo que siempre conduzca a una respuesta de si o no correcta. El problema de la parada es un ejemplo: no existe algoritmo que determine de manera correcta si un programa arbitrario se detendra, una vez sea ejecutado...

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

Mediante alguna codificacion, tal como una numeracion de Godel, las cadenas se pueden codificar como numeros naturales. Asi, un problema de decision informalmente expresado en terminos de un lenguaje formal es tambien equivalente a un conjunto de numeros naturales. Para mantener simple la definicion formal, se expresa en terminos de subconjuntos de los numeros naturales.

Formalmente, un problema de decision es un subconjunto de los numeros naturales. El problema informal correspondiente consiste en decidir si un numero dado esta en el conjunto. A un problema de decision 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 transformacion 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 serviria tambien para decidir sobre un problema conocido como indecidible.

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

En logica

• Inferencia y verificacion de tipos en logica de segundo orden.
• El Entscheidungsproblem de Hilbert.

Maquinas abstractas

• Problema de parada (determinar si una maquina de Turing se detiene en una entrada dada) y el problema de mortalidad (determinando si se detiene para cada configuracion de partida).
• Determinar si una maquina de Turing es campeon del juego del castor ocupado (es decir, es el mas largo entre las maquinas de Turing de detencion con el mismo numero de estados).
• El Teorema de Rice afirma que, para todas las propiedades no triviales de las funciones parciales, es indecidible si una maquina determinada calcula una funcion parcial con esa propiedad.

Matrices

• Problema de la matriz mortal: determinar, dado un conjunto finito de n x n matrices con entradas enteras, si se pueden multiplicar en algun orden, posiblemente con repeticion, para obtener la matriz cero. Esto se sabe que es indecidible para un conjunto de seis o mas matrices 3 x 3, o un conjunto de dos matrices 15 x 15..
• Determinar si un conjunto finito de matrices 3 x 3 triangulares superiores con entradas enteras no negativas genera un semigrupo libre.

Fisica cuantica

• La existencia de una brecha espectral de un material cuantico^[1]

Teoria combinatoria de grupos

• El problema de la conjugacion.
• El problema del isomorfismo grupal.
• Problemas de topologia
• 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 decimo problema de David Hilbert: el problema de decidir si una ecuacion diofantica (ecuacion polinomial multivariable) tiene una solucion en numeros enteros.
• Determinar si una gramatica sin contexto genera todas las cadenas posibles, o si es ambigua.
• Dadas dos gramaticas 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.

• Entscheidungsproblem

• Rajeev Motwani y Jeffrey D. Ullman. Introduccion a la teoria de automatas, lenguajes y computacion.
• Elisa Viso. Introduccion a la Teoria de la Computacion.

• Esta obra contiene una traduccion derivada de <<Undecidable problems>> de Wikipedia en ingles, concretamente de esta version, publicada por sus editores bajo la Licencia de documentacion libre de GNU y la Licencia Creative Commons Atribucion-CompartirIgual 4.0 Internacional.

• Informatica teorica
• Logica matematica
• Teoria de la demostracion
• Teoria de modelos

• Wikipedia:Articulos que necesitan referencias adicionales
• Wikipedia:Referenciar (aun sin clasificar)
• Wikipedia:Paginas con traducciones del ingles