¿Por qué este lenguaje es reconocible y no turing reconocible?

Question

Leí que el siguiente idioma es R.E. pero no sin turing reconocible

$ l $ : en la entrada $ m $ (donde $ M $ es una máquina de Turing), $ m $ acepta al menos 20 entradas

No estoy seguro de por qué no es reconocible., Dado que tal vez podría hacer la siguiente reducción de $ \ endinline {a_ {tm}} $ a $ l $ dado este procedimiento $ r $ a saber:

$ r $ : en la entrada $ $ :

1. construir TM $ m_1 $ , donde en la entrada $ x $ , si $ x= 1 $ , aceptar
2. si la entrada $ x $ no es igual a $ 1 $ , ejecute $ m $ en la entrada $ w $ para $ | x pasos. Si después de $ | x | $ pasos, $ m $ no acepta $ W $ , luego acepte $ x $

De esta reducción, si $ m $ no acepta $ w $ , es decir, $ \ IN \ Overline {A_ {tm}} $ , luego $ m_1 $ acepta cualquier entrada palabra, es decir, $ m_1 \ en l $ .

¿Estoy perdiendo algo aquí?

Answer 1

Lo que falta es que si $ \ langose M, w \ rangle \ notin \ overline {a _ {\ mathrm {tm}}}} $ , es decir, si $ m $ se detiene en la entrada $ w $ , no sabes si o $ M_1 \ Notin L $ .Si $ m $ se detiene en $ w $ , pero esto lleva más tiempo que $ 20 $ pasos, también mantendría ese $ m_1 \ en l $ .Por lo tanto, no tienes una reducción aquí.

que el idioma $ l $ no puede ser co-re es una consecuencia inmediata del teorema de arroz.