Aidez-moi à comprendre ce problème de Turing-Machine concernant $ a_ {tm} $

Question

Je suis une physique / C.S. étudiant et ont eu du mal avec ce problème particulier pendant quelques jours maintenant. Donc, la tâche est comme suit:

---

Considérez les langues suivantes:

$ \ hspace {20pt} l_1={\ utilg m \ RANG \, | \, L (m)= a_ {tm} \} \\ \ hspace {20pt} l_2={\ \ lelopper m \ rangs \, | \, L (m)=overline {a_ {tm}} \} $

sont ces décidables? Prouver votre décision.

$ a_ {tm} $ $ est défini comme $ \ {\ langle m, w \ rangs \, | \, \ text {m est un tm et m accepte w} \} $

---

Donc, tout d'abord, j'essaie de comprendre la première langue $ l_1 $ . Qu'est-ce que cela signifierait exactement pour $ l_1 $ pour être décidable? Je comprends pourquoi $ a_ {tm} $ n'est pas décembre, mais qu'est-ce qu'un TM qui décide $ l_1 $ réellement faire?

Je me sens comme si je connais déjà la solution au deuxième problème, mais je voudrais savoir si mon instinct d'intestin est juste. Donc, depuis $ \ overline {a_ {tm}} $ ne peut-il pas reconnaître cela signifie que $ m $ avec $ l (m)=overline {a_ {tm}} $ n'existe pas / est vide. Ainsi $ l_2=videtyset $ et c'est facilement décidable.

Answer 1

résoudre le langage $ l_1 $ signifie savoir pour chaque TM s'il est semi-décidant de $ a_ {tm} $ problème.

Votre instinct a raison - il est vide et donc décidable. si , il n'était pas vide par hasard, alors par le théorème de Rice, il n'aurait pas été décidable