Problema indecidible

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 o no correcta.

Un problema de decisión es cualquier pregunta arbitraria de 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 . 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[editar]

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

En lógica
Máquinas abstractas
Matrices
  • Problema de la matriz mortal: Dado un número finito de matrices cuadradas, determinar si multiplicando estas matrices en un cierto orden, posiblemente repitiendo algunas, se puede obtener la matriz cero.
Física cuántica
  • La existencia de un gap espectral de un material cuántico[1]

Véase también[editar]

Referencias[editar]

  1. ABC.ES, ed. (10 de diciembre de 2015). «El problema de la Física que no se puede resolver». Consultado el 16 de diciembre de 2015. 

Bibliografía[editar]

  • 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.