Idiomas indecidibles

Para un lenguaje indecidible, no existe una Máquina de Turing que acepte el lenguaje y tome una decisión para cada cadena de entrada. w(Sin embargo, TM puede tomar decisiones para alguna cadena de entrada). Un problema de decisiónP se llama "indecidible" si el idioma L de todos los casos de sí a Pno es decidible. Los lenguajes indecidibles no son lenguajes recursivos, pero a veces, pueden ser lenguajes recursivamente enumerables.

Ejemplo

• El problema de la detención de la máquina de Turing
• El problema de la mortalidad
• El problema de la matriz mortal
• El problema de la correspondencia postal, etc.