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
Exemplos de problemas decidíveis incluem a verificação de propriedades de linguagens formais como as linguagens regulares
Problemas clássicos indecidíveis incluem o problema da parada (Halting Problem) e o problema de decisão de