– Diz-se que um problema de decisão P é semi-decidível (ou seja, tem um semi-algoritmo) se a linguagem L de todas as instâncias sim para P for r.e. – (Problema de equivalência para DFA) Dados dois DFAs, eles aceitam o mesmo idioma? Prova: Lembre-se do argumento de Cantor da Primeira Aula.
Quando se diz que um problema é semi-decidível?
Problemas semi-decidíveis são aqueles para que uma máquina de Turing para na entrada aceita por ela, mas pode parar ou fazer um loop indefinidamente na entrada que é rejeitada pela Máquina de Turing. Tais problemas são chamados de problemas Reconhecíveis de Turing.
O que é problema parcialmente decidível?
Definição: Um cujo idioma associado é um idioma recursivamente enumerável. De forma equivalente, existe um algoritmo que interrompe e gera 1 para cada instância com uma resposta "sim", mas para instâncias com uma resposta "não" é permitido não parar ou parar e produzir 0.
O problema da parada é parcialmente decidível?
Alan Turing provou em 1936 que um algoritmo geral executado em uma máquina de Turing que resolve o problema da parada para todos os pares de entrada de programa possíveis necessariamente não pode existir. Portanto, o problema da parada é indecidível para máquinas de Turing.
Por que o problema da parada é semi-decidível?
Uma linguagem é semi-decidível se existe uma máquina de Turing que para se uma palavra pertence à linguagem (casos SIM) e pode rejeitar ou entrar no infinito loop se a palavra não pertencer ao idioma (NENHUM caso).
