Por que essa linguagem é reconhecível e não é reconhecível

Question

Eu li que a seguinte língua é r.e. mas não não tentando reconhecível

$ l $ : na entrada $ m $ (onde $ m $ é uma máquina de Turing), $ m $ aceita pelo menos 20 entradas

Não tenho certeza porque não é reconhecível., Desde que talvez fosse a seguinte redução da $ \ overline {a_} $ para $ l $ Dado este procedimento $ R $ nomeadamente:

.

$ R $ : na entrada $ $ :

.

.
1. construir tm $ m_1 $ , onde na entrada $ x $ , se $ x= 1 $ , aceitar
2. se a entrada $ x $ não é igual a $ 1 $ , executado $ m $ na entrada $ W $ para $ | x | $ degraus. Se após $ | x | $ etapas, $ m $ não aceita $ W $ e, em seguida, aceitar $ x $

desta redução, se $ m $ não aceita $ W $ , ou seja, $ \ in \ overline {a_ {tm}} $ , então $ m_1 $ aceita qualquer entrada palavra, ou seja $ m_1 \ em l $ .

Estou perdendo alguma coisa aqui?

Answer 1

O que você está faltando é que, se $ \ langer m, w \ rangle \ notin \ spany {a _ {\ mathrm {tm}}} $ , ou seja, se $ m $ pára na entrada $ W $ , você não sabe se ou $ m_1 \ notin l $ .Se $ m $ pare na $ W $ , mas isso leva mais tempo do que $ 20 $ etapas, também manteria aquela $ m_1 \ em l $ .Assim, você não tem uma redução aqui.

Que a linguagem $ l $ não pode ser co-re é uma conseqüência imediata do teorema do arroz.