Problema de la decisión

Un problema de decisión es aquél cuya respuesta puede mapearse al conjunto de valores {0,1}, esto es, que tiene sólo dos posibles soluciones: sí o no. La representación de este tipo de problemas se puede hacer a través de una función cuyo dominio sea el conjunto citado.

Se dice que un problema es decidible cuando puede resolverse en un número finito de pasos por un algoritmo que recibe todas las entradas posibles para dicho problema. El lenguaje con el que se implementa dicho algoritmo se denomina lenguaje decidible o recursivo.

Por el contrario, un problema no decidible es aquel que no puede resolverse por un algoritmo en todos sus casos. Asimismo, su lenguaje asociado no puede ser reconocido por una Máquina de Turing.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM