Quelle est la différence entre le langage indécidable et la langue reconnaissable de Turing?
-
05-11-2019 - |
Question
Je me demandais quelle est la différence de différence un langage indécidable et un langage reconnaissable de Turing. J'ai vu dans certains cas où ils demandent:
- Prouver que la langue $ a_ {tm} = {u003CM,w> | M mbox {est une machine Turing qui accepte} w } $ est indécidable.
- Prouver que la langue $ a_ {tm} = {u003CM,w> | M mbox {est une machine Turing qui accepte} w } $ est reconnaissable de Turing.
Sont-ils la même chose? Quelqu'un peut-il développer cette question?
Un autre, la question est-elle connue comme le problème d'arrêt? Ou est-ce différent du problème d'arrêt?
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange