indecidível

Indecidível é um adjetivo da língua portuguesa que descreve algo que não pode ser decidido ou determinado de forma firme. Pode referir-se a situações em que não existe um resultado único ou correto, ou à impossibilidade de aplicar um método geral para chegar a uma conclusão a partir de informações disponíveis. O termo também é comum em lógica e matemática para designar proposições ou problemas que não admitem uma resolução algorítmica universal.

Em computação e teoria da decisão, um problema indecidível é aquele para o qual não existe um algoritmo que determine a resposta correta para todos os casos. Exemplos clássicos incluem o problema da parada (halting problem) e o Entscheidungsproblem (problema da decisão), demonstrados por Turing e Church; nesses casos não há procedimento mecânico que resolva de forma geral se uma máquina irá parar ou se uma proposição é provável em lógica de primeira ordem. A indecidibilidade é distinta de simples dificuldade prática: pode haver soluções parciais ou verificáveis para muitos casos, mas não uma solução que funcione para todos os inputs.

Na filosofia, na linguística e na teoria da decisão, indecidibilidade também pode descrever situações em que critérios conflitantes, informações incompletas ou valores incompatíveis impedem uma decisão definitiva.

Substantivos relacionados incluem indecidibilidade; o adjetivo correspondente é indecidível.