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.