Línguas Indecidíveis
Para uma linguagem indecidível, não há Máquina de Turing que aceita a linguagem e toma uma decisão para cada string de entrada w(TM pode tomar decisões para alguma string de entrada). Um problema de decisãoP é chamado de "indecidível" se o idioma L de todas as instâncias sim para Pnão é decidível. As linguagens indecidíveis não são linguagens recursivas, mas às vezes, podem ser linguagens enumeráveis recursivamente.
Exemplo
- O problema de parada da máquina de Turing
- O problema da mortalidade
- O problema da matriz mortal
- O problema de correspondência do Post, etc.