Problemas de decisión en computabilidad: definición y decidibilidad

Explora problemas de decisión en computabilidad: definición, criterios de decidibilidad, métodos y ejemplos de problemas indecidibles. Comprende los límites de lo computable.

En la teoría de la computabilidad y la teoría de la complejidad computacional, un problema de decisión es una pregunta en algún sistema formal con una respuesta de sí o no. La respuesta depende de los valores de los parámetros de entrada. Los problemas de decisión suelen aparecer en cuestiones matemáticas de decidibilidad, es decir, la cuestión de la existencia de un método eficaz para determinar la existencia de algún objeto o su pertenencia a un conjunto. Algunos de los problemas más importantes de las matemáticas son indecidibles.

Definición formal y representación

Formalmente, un problema de decisión puede verse como un conjunto de cadenas (un lenguaje) sobre algún alfabeto: la cadena representa la instancia del problema y pertenece al conjunto si la respuesta es "sí". Desde el punto de vista de la computabilidad, hablamos de:

• Lenguaje decidible (o recursivo): existe una máquina de Turing que, dada cualquier entrada, se detiene y acepta si la entrada pertenece al lenguaje, y se detiene y rechaza si no pertenece.
• Lenguaje recursivamente enumerable (RE o semi-decidible): existe una máquina de Turing que acepta exactamente las cadenas del lenguaje, pero para las cadenas fuera del lenguaje puede no detenerse (es decir, puede quedar en bucle).
• Co-RE: el complemento del lenguaje es RE. Si un lenguaje es tanto RE como co-RE, entonces es decidible.

Ejemplos típicos

• Problemas decidibles: pertenencia a un lenguaje regular (autómatas finitos), pertenencia a un lenguaje libre de contexto (algoritmos tipo CYK), conectividad en grafos finitos, primalidad de un número (algoritmos deterministas polinomiales modernos).
• Problemas semi-decidibles pero no decidibles: el problema de la parada (halting problem): dado un programa y su entrada, decidir si el programa se detendrá. El conjunto de pares que sí paran es RE, pero no decidible.
• Problemas indecidibles importantes: el problema de parada, el problema de pertenencia para ciertas clases de funciones computables, el problema de existencia de soluciones enteras para ecuaciones diofánticas generales (Relacionado con el teorema de Matiyasevich sobre el problema de Hilbert X).

Decidibilidad y técnicas para demostrar (in)decidibilidad

Las demostraciones de decidibilidad suelen consistir en construir un algoritmo o una máquina de Turing que halle la respuesta en tiempo finito para cualquier entrada. Para mostrar indecidibilidad se utilizan técnicas de reducción:

• Reducción many-one (m-reducibilidad): transformar instancias de un problema A en instancias de un problema B mediante una función computable f tal que x ∈ A ⇔ f(x) ∈ B. Si A es indecidible y A ≤m B, entonces B también es indecidible.
• Reducciones de Turing: permitir llamadas a un "oracle" para B; más potente que many-one y útil para clasificar problemas según su dificultad relativa.
• Teoremas generales: por ejemplo, el teorema de Rice establece que cualquier propiedad no trivial de las funciones computables (propiedad sobre el comportamiento computacional, no meramente sintáctica) es indecidible. Esto se usa para demostrar indecidibilidad de muchas propiedades de programas.

Relación con la complejidad computacional

En teoría de la complejidad se estudian principalmente versiones de decisión de problemas de cómputo porque permiten clasificar la dificultad en clases como P (problemas decidibles en tiempo polinómico por máquinas deterministas) y NP (problemas cuya respuesta "sí" puede verificarse en tiempo polinómico dada una prueba). Las nociones de completitud (NP-completo, co-NP, etc.) se definen sobre problemas de decisión mediante reducciones polinomiales.

Propiedades y observaciones útiles

• Un problema de decisión es la forma más simple de problema computacional y muchas tareas más generales (problemas de optimización, problemas de búsqueda) pueden formularse como familias de problemas de decisión.
• La clase de problemas decidibles es cerrada bajo operaciones típicas de conjuntos: unión, intersección y complemento (pues se puede combinar o invertir la máquina de decisión).
• Para problemas semi-decidibles, la cerradura bajo complemento no se cumple en general: RE no es igual a co-RE salvo en casos decidibles.
• Probar que un problema es indecidible no sólo muestra la imposibilidad de un algoritmo general que siempre termine, sino que orienta la búsqueda hacia soluciones aproximadas, semidecisivas, heurísticas o restricciones de la entrada donde sí sea decidible.

Importancia y consecuencias

El estudio de problemas de decisión y su decidibilidad es central para comprender los límites de la computación. Saber que un problema es indecidible explica por qué no existe un algoritmo general para él y justifica el desarrollo de técnicas alternativas (restricciones, heurísticas, pruebas asistidas por humanos, semidecidibilidad). Además, la formulación en términos de problemas de decisión permite conectar la computabilidad con la complejidad, dando un marco unificado para medir tanto la posibilidad de resolver un problema como el coste computacional de hacerlo.

En resumen, los problemas de decisión constituyen una piedra angular en teoría de la computación: proporcionan una forma formal y manejable de preguntar "¿sí o no?" sobre instancias finitas, y a partir de ellos se desarrollan herramientas para clasificar, reducir y entender lo que las máquinas pueden o no pueden decidir.

Preguntas y respuestas

P: ¿Qué es un problema de decisión?

P: ¿En qué campos de estudio aparecen los problemas de decisión?

P: ¿Qué significa decidibilidad?

P: ¿Son decidibles todos los problemas matemáticos?

P: ¿Qué es un problema indecidible?

P: ¿La respuesta a un problema de decisión es siempre sí o no?

P: ¿De qué depende la respuesta a un problema de decisión?

Búsqueda por letra