Lingue indecidibili
Per una lingua indecidibile, non esiste una Turing Machine che accetti la lingua e prenda una decisione per ogni stringa di input w(Tuttavia, TM può prendere decisioni per alcune stringhe di input). Un problema decisionaleP si chiama “indecidibile” se la lingua L di tutti i casi sì Pnon è decidibile. Le lingue indecidibili non sono linguaggi ricorsivi, ma a volte possono essere linguaggi enumerabili ricorsivamente.
Esempio
- L'arresto del problema della macchina di Turing
- Il problema della mortalità
- Il problema della matrice mortale
- Il problema della corrispondenza postale, ecc.