Domanda

Perché questo problema è$$ l = { langle m rangle mid l (m) text {è undecidabile} } $$ indecidibile?

Ho pensato se lo sappiamo $ L (m) $ Turingmaschine accetta tutto $ x in l (m) $, Così $ L (m) $ è in ogni caso decidabile e $ L = vuoto $ Soprattutto finito e decidabile.

So che non possiamo trovare un algoritmo ma ogni TM ha una lingua e noi anche se non lo facciamo, sappiamo che è decidabile.

Qualcuno può aiutarmi dove ho un malinteso?

Nessuna soluzione corretta

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