problema indecidível

Na teoria da computação e na teoria da complexidade computacional, um problema indecidível é um problema de decisão em que é impossível construir um algoritmo que sempre responde corretamente sim ou não. Um problema de decisão é qualquer questão arbitrária de sim-ou-não sobre um conjunto infinito de entradas. Por causa disto, é comum definir o problema de decisão de maneira equivalente como: o conjunto de entradas para o qual o problema retorna sim. Estas entradas podem ser números naturais, mas também podem ser outros valores de outros tipos, como cadeias de uma linguagem formal. Usando alguma codificação, tal como uma numeração de Gödel, as cadeias podem ser codificadas como números naturais. Para manter a definição de formalidade simples, ela é colocada em termos de subconjuntos dos números naturais. Formalmente, um problema de decisão é um subconjunto dos números naturais. O problema correspondente de maneira informal é o de se decidir se um dado número está no conjunto. Um problema de decisão A é chamado decidível ou efetivamente solúvel se A é um conjunto recursivo. Um problema é chamado parcialmente decidível, semidecidível, solúvel, ou provável se A é um conjunto recursivamente enumerável. Problemas parcialmente decidíveis e outros problemas que não são decidíveis são chamados indecidíveis.