Domanda

Permettere $ L = { langle m rangle mid m text {ferme su} langle m rangle } $essere una lingua dove $ langle m rangle $ è il codice del TM $ M $. $ L $ è indecidibile.

Ho sentito che non posso usare il teorema di Rice per provare la sua indecidibilità.

Ma perché? Posso costruire un set $ S = {f_m mid f_m ( langle m rangle) in {0,1 } } $.

È chiaro che $ S $ non è vuoto e $ S $ contiene non tutti i TM.

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top