Il linguaggio di TM è indecidibile
-
05-11-2019 - |
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