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:

  1. Prouver que la langue $ a_ {tm} = {u003CM,w> | M mbox {est une machine Turing qui accepte} w } $ est indécidable.
  2. 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
scroll top