Teorema de Rice para propriedades não-semânticas

30

O teorema de Rice nos diz que as únicas propriedades semânticas das Máquinas de Turing (ou seja, as propriedades da função computada pela máquina) que podemos decidir são as duas propriedades triviais (ou seja, sempre verdade e sempre falsas).

Mas existem outras propriedades das máquinas de Turing que não são decidíveis. Por exemplo, a propriedade de que há um estado inacessível em uma determinada máquina de Turing é indecidível .†

Existe um teorema semelhante ao teorema de Rice que categoriza a decidibilidade de propriedades semelhantes? Eu não tenho uma definição precisa. Qualquer teorema conhecido que cubra o exemplo que eu dei seria interessante para mim.

† é fácil provar que este conjunto é indecidível usando / teoremas de ponto fixo de recursão de Kleene .

computability undecidability Kaveh
fonte
O problema da parada é essencialmente a questão de saber se o estado de parada é alcançável; portanto, a questão geral de quais estados são alcançáveis ​​certamente será insolúvel.
Carl Mummert
@ Carl, sim, eu sei disso, mas isso é diferente do meu exemplo. Meu exemplo é: dado <M>, existe um estado inacessível (removê-lo não afetará a máquina em nenhuma entrada). É semelhante a uma pergunta em Métodos formais: existe uma linha de código desnecessária? (o que geralmente significa que o programa não está realmente funcionando como o esperado).
Kaveh
@Kaveh: Em geral, o problema de parada é -equivalente ao problema de parada para máquinas que ignoram completamente sua entrada e, para essa classe especial de máquinas, o problema de parada '' é '' o problema de saber se o estado de parada é acessível em seu computador. sentido. 1
Carl Mummert
@ Carl, sim, eu conheço a redução direta (temos que garantir que todos os outros estados sejam alcançáveis). Mas minha pergunta não é sobre o problema em si, foi um exemplo fácil de linguagem não-semântica indecidível. Então, você sabe se existe algo semelhante ao teorema de Rice que cubra propriedades não-semânticas? Ou você acha que é improvável que esse teorema exista?
Kaveh

Respostas:

14

Um teorema geral que cobre parcialmente o exemplo dado é que qualquer propriedade -hard da máquina será indecidível. O problema de parada é redutível ao problema de alcançabilidade do estado, de modo que mostra que o problema de redutibilidade do estado é -hard.Σ10mΣ10

No entanto, esse não é um teorema de "se e somente se", como o teorema de Rice. Se todas as propriedades do índice da máquina de Turing como uma propriedade da máquina, não haverá uma boa caracterização, porque não existe uma boa caracterização sobre a qual os reconfigurações sejam decidíveis em termos de índice do redefinido.Σ10

Carl Mummert
fonte