decidíveis

Decidíveis, no contexto da teoria da computação, referem-se a problemas de decisão para os quais existe um algoritmo que, para qualquer entrada, sempre encerra com uma resposta correta: sim ou não. Em outras palavras, um problema é decidível se existe uma máquina de Turing (ou procedimento equivalente) que decide o problema, ou seja, que decide a linguagem associada em todas as entradas.

Essa noção distingue-se de problemas semi-decidíveis (recursivamente enumeráveis), para os quais pode haver um algoritmo que aceita as entradas que satisfazem o enunciado, mas que pode não encerrar para entradas que não satisfazem. A decidibilidade implica também que o complemento do problema é decidível, pois o algoritmo pode ser invertido para retornar a outra resposta. Em termos formais, uma linguagem é decidível se é recursiva.

Exemplos de problemas decidíveis incluem a verificação de propriedades de linguagens formais como as linguagens regulares (existem algoritmos que, dado um DFA, respondem se uma palavra pertence à linguagem), bem como a verificação de primalidade, a soma e a multiplicação de números naturais, e o problema de pertencimento para várias classes computacionais bem compreendidas (por exemplo, linguagens context-free, com algoritmos de parsing). Em geral, muitos problemas práticos de verificação e automação são decidíveis.

Problemas clássicos indecidíveis incluem o problema da parada (Halting Problem) e o problema de decisão de primeira ordem em lógica (o Entscheidungsproblem). Esses resultados destacam limites fundamentais da computação e distinguem entre o que pode e o que não pode ser decidido por algoritmos.