Pourquoi ce langage est-il reconnaissable et ne pas-il ne pas être reconnaissable

Question

J'ai lu que la langue suivante est R.E. mais pas pas-tuinging reconnaissable

$ l $ : sur entrée $ m $ (où $ M $ est une machine de Turing), $ M $ accepte au moins 20 entrées

Je ne suis pas sûr de savoir pourquoi il ne peut pas être reconnaissable., Puisque je pouvais peut-être effectuer la réduction suivante de $ \ overline {a_ {tm}} $ à $ l $ donné cette procédure $ r $ nommément:

$ R $ : sur entrée $ $ :

1. construire tm $ m_1 $ , où en entrée $ x $ , si $ x= 1 $ , accepte
2. Si entrée $ x $ n'est pas égal à $ 1 $ , exécuter $ M $ sur entrée $ w $ pour $ | $ pas. Si après $ | x | $ étapes, $ m $ n'accepte pas $ w $ , puis acceptez $ x $

à partir de cette réduction, si $ m $ n'accepte pas $ w $ , c'est-à-dire $ \ in \ in \ overline {a_ {tm}} $ , puis $ m_1 $ accepte toute entrée mot, c'est-à-dire $ m_1 \ in l $ .

Est-ce que je manque quelque chose ici?

Answer 1

Qu'est-ce que vous manquez est que si $ \ lger m, w \ rangle \ notin \ overline {a {\ mathrm {tm}}} $ , c'est-à-dire si $ m $ s'arrête sur l'entrée $ w $ , vous ne savez pas si ou $ m_1 \ notin l $ .Si $ M $ arrête sur $ w $ , mais cela prend plus de temps que 20 $ de 20 $ étapes, il tiendrait également que $ m_1 \ in l $ .Ainsi, vous n'avez pas de réduction ici.

que la langue $ l $ ne peut pas être co-re, une conséquence immédiate du théorème de Rice.