Cette langue est-elle décidable?
-
29-09-2020 - |
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} \}$$
La solution
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 '$ .
.