Cette langue est-elle décidable?

Question

comme le dit le titre; est cette langue tremblement et comment le prouvez-vous?

$$ l=\ \ \ \ \ \ \ u \ m \ m \ m \ text {est une machine de Turing et il y a une entrée que} m \ text {s'arrête sur} \}$$

Answer 1

Votre langue n'est pas décritable. Pour montrer qu'il suffit de remarquer que l'existence d'une machine à tanging $ t $ qui a décidé $ l $ implique l'existence d'une machine de Turning qui résout le problème d'arrêt.

En effet, étant donné n'importe quelle machine de Turing $ M $ avec entrée $ x $ Vous pouvez construire un Turing machine $ m '$ qui ignore son entrée, écrit $ x $ sur la bande, puis simule < SPAN CLASSE="MATH-CONTENEUR"> $ M $ . Clairement $ M '$ s'arrête (indépendamment de son entrée) si et uniquement si $ M $ s'arrête en entrée $ x $ . Nous pouvons décider si $ m '$ s'arrête en vérifiant si $ m' \ in l $ en utilisant $ T $ avec entrée $ M '$ .

.