Propiedades de indecidibilidad

Se dice que un lenguaje es indecidible si sus miembros no pueden ser identificados por un algoritmo que restrinja todas las entradas en un número de pasos finito. Otra de sus propiedades es que no puede ser reconocido como una entrada válida en una máquina de Turing.

Asociados a este tipo de lenguaje existen, de la misma manera, problemas indecidibles que son aquellos que no pueden ser resueltos, con todas sus variantes, por un algoritmo.

En contraposición con el lenguaje indecidible y los problemas asociados a este tipo de lenguajes existen los problemas decidibles, que están relacionados con lenguajes del mismo tipo y que tienen las características opuestas.

Este tipo de lenguajes se conoce, también, como lenguajes recursivos o lenguajes totalmente decidibles.

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