Sous la langue n'est pas reconnaissable Turing, ou pourrait-il être?

Question

Soit A et B avec des langues A ? B et B est reconnaissable Turing. Peut-être un non-reconnaissable Turing? Si oui, est-il par exemple?

Answer 1

Ceci est quelque chose qui confond beaucoup d'étudiants. Le point ici est que d'être sous-ensemble d'une autre langue ne signifie pas grand-chose au sujet de leur difficulté de calcul. Vous pouvez toujours considérer la langue triviale $ \ emptyset $ et $ \ Sigma ^ * $ et toute autre langue est entre eux w.r.t. inclusion jeu.

Par conséquent, tout en sachant qu'une langue contient ou est contenu dans un langage facile à compute ne dit rien au sujet de la difficulté de le calculer.

Answer 2

Quand une langue reconnaissable $ Turing X $ est pas décidable, il implique qu'il n'y a pas co-Turing reconnaissable (en d'autres termes: $ X ^ c $ est méconnaissable). Depuis $ X ^ c $ est un sous-ensemble parfaitement valide de $ \ Sigma ^ * $, ce soutien le fait que pour une langue $ A \ subseteq B $ où $ B $ est Turing reconnaissable, $ A $ peut très bien ne pas être .

Answer 3

Votre discussion me confondre avec succès :(

"Can A ne soit pas reconnaissable Turing?"

Je me sens toujours reconnaissable Turing . Voici ma façon de penser,

Puisque B est Turing Reconnaissable => Il y a une TM qui accepte tous les mots de la langue B => Il y a un TM qui accepte (tous les mots de la langue A + d'autres mots) => Il y a un TM qui accepte tous les mots de la langue A => A est Turing Reconnaissable.

Est-ce mal? il peut y avoir tous les cas où A est non-TRL tandis que B est TRL. Aide Veuillez

Answer 4

Dans ce cas, ne pouvait pas être reconnaissable Turing. Prenez cet exemple:

langue B est l'union d'un t.r linguistique (C) et une langue non t.r (A). vous pouvez créer une machine de Turing qui reconnaît B. A n'est pas t.r et A ? B.

est-ce pas? Je ne sais pas si elle is..so .. =)