Perché questa lingua è riconoscibile e non rilevabile riconoscibile

Question

Ho letto che la seguente lingua è R.E. Ma non not-turing riconoscibile

$ l $ : su input $ m $ (dove $ m $ è una macchina di Turing), $ m $ accetta almeno 20 ingressi

Non sono sicuro del motivo per cui non si trova riconoscibile., Dal momento che potrei forse fare la seguente riduzione da $ \ overline {a_ {tm}} $ a $ L $ Dato questa procedura $ r $ vale a dire:

.

$ R $ : su ingresso $ $ :

.

.
1. Costruisci TM $ m_1 $ , dove su ingresso $ x $ , se $ x= 1 $ , accettare
2. se input $ x $ non è uguale a $ 1 $ , eseguire $ m $ su ingresso $ w $ per $ | x | $ passi. Se dopo $ | x | $ passaggi, $ m $ non accetta $ W $ , quindi accettare $ x $

Da questa riduzione, se $ m $ non accetta $ W $ , cioè $ \ in \ overline {a_ {tm}} $ , quindi $ m_1 $ Accetta qualsiasi input Word, IE $ m_1 \ in l $ .

Mi manca qualcosa qui?

Answer 1

Cosa ti manca è che se $ \ Langle m, w \ rangle \ notin \ overline {a _ {\ mathrm {tm}}} $ , cioè se $ m $ halts on input $ w $ , non sai se o $ M_1 \ Notin L $ .Se $ m $ si ferisce su $ W $ , ma questo richiede più tempo di $ 20 $ Passi, tenerebbe anche quella $ m_1 \ in l $ .Quindi, non hai una riduzione qui.

che la lingua $ l $ non può essere co-re è una conseguenza immediata del teorema del riso.