¿Por qué este lenguaje es reconocible y no turing reconocible?
-
29-09-2020 - |
Pregunta
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 $
$ :
- construir TM $ m_1 $ , donde en la entrada $ x $ , si $ x= 1 $ , aceptar
- 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, $
¿Estoy perdiendo algo aquí?
Solución
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.