semidecidíveis

Semidecidíveis, ou recursivamente enumeráveis (RE), são conjuntos de palavras sobre um alfabeto que podem ser enumerados por uma máquina de Turing. Existem duas formas equivalentes de definição: (1) existe uma máquina de Turing que, dada qualquer entrada w, para e aceita se w pertence ao conjunto; se w não pertence, a máquina pode não parar. (2) existe uma máquina de Turing que imprime, em algum momento, todas as palavras de L, possivelmente com repetições, isto é, L é enumerable.

Em termos de decidibilidade, todo conjunto decidível (recursivo) é semidecidível, pois há uma máquina que sempre para com resposta correta, aceitando ou rejeitando. Entretanto, nem todo conjunto semidecidível é decidível: a semidecidibilidade não implica poder decidir para todas as entradas. Assim, semidecidibilidade é uma propriedade mais fraca que a decidibilidade.

Exemplos típicos incluem o problema da parada. O conjunto H = {descrições de programas que param em alguma entrada} é semidecidível: existe uma máquina de Turing que aceita exatamente quando o programa para. No entanto, H não é decidível, e seu complemento não é semidecidível.

Propriedades e limites: as linguagens semidecidíveis são fechadas sob união, concatenacão e estrela de Kleene; não, em geral, sob complemento nem sob interseção. Uma forma útil de caracterizar semidecidibilidade é pela existência de uma função parcial computável cuja domain é exatamente o conjunto em questão.

Aplicações: semidecidibilidade é central em teoria da computação para entender problemas indecidíveis, critérios de completude de algoritmos e limites da automação de provas e verificação.