Le sous-langage n'est pas reconnaissable par Turing, ou pourrait-il l'être?

10

Soit A et B des langues avec A ⊆ B, et B est reconnaissable par Turing. A ne peut-il pas être reconnu par Turing? Si oui, y a-t-il un exemple?

computability gfe
la source

18

C'est quelque chose qui déroute beaucoup d'étudiants. Le point ici est qu'être un sous-ensemble d'une autre langue n'implique pas grand-chose de leur difficulté de calcul. Vous pouvez toujours considérer le langage trivial et et tout autre langage est entre eux par rapport à l'inclusion d'ensemble. $\emptyset$ $\Sigma^*$

Par conséquent, le simple fait de savoir qu'un langage contient ou est contenu dans un langage facile à calculer ne dit rien sur la difficulté de le calculer.

Kaveh
la source

Mais je ne trouve aucun langage de sous-ensemble de Σ ∗ qui ne soit pas reconnaissable par Turing.

gfe

3

@Wilhelm, prenez n'importe quelle langue qui n'est pas reconnaissable par Turing et cela fonctionnera.

Kaveh

Je vois, donc je peux utiliser le problème d'arrêt pour prouver qu'il existe un tel langage.

gfe

@Wilhelm, oui. :)

Kaveh

1

Lorsqu'un langage reconnaissable par Turing n'est pas décidable, cela implique qu'il n'est pas reconnaissable par Turing (en d'autres termes: n'est pas reconnaissable). Puisque est un sous-ensemble parfaitement valide de , cela confirme le fait que pour un langage où est reconnaissable par Turing, peut très bien ne pas l'être. $X$ $X^c$ $X^c$ $\Sigma^*$ $A \subseteq B$ $B$ $A$

Sander
la source

Je pense que la réponse de Kaveh est meilleure et plus pertinente. Toute langue est un sous-ensemble de

et nous savons que

est décidable et qu'il existe des langues arbitrairement dures.

Σ^{*}

$\Sigma^*$

Σ^{*}

$\Sigma^*$

Pål GD

C'est ce que j'ai essayé d'expliquer, car

pourrait être n'importe quelle langue, car

tient automatiquement. ;)

X

$X$

X \subset Σ^{*}

$X \subset \Sigma^*$

Sander

-3

Votre discussion m'a confondu avec succès :(

"A ne peut-il pas être reconnu par Turing?"

Je sens que A est toujours reconnaissable par Turing . Voici ma pensée,

Puisque B est Turing reconnaissable => Il y a un TM qui accepte tous les mots du langage B => Il y a un TM qui accepte (tous les mots du langage A + quelques autres mots) => Il y a un TM qui accepte tous les mots du langage A => A est Turing reconnaissable.

Est-ce mal? Peut-il y avoir n'importe quel cas où A est non-TRL tandis que B est TRL. Aide aimablement

bongubj
la source

1

Oui, c'est faux: l'accepteur d'une langue ne doit accepter aucun mot sauf ceux de la langue.

reinierpost

Veuillez ne pas poster de questions de suivi comme réponses. Utilisez des commentaires (après avoir prouvé au système que vous êtes digne de confiance) ou créez un nouveau message si la nouvelle question est sensiblement différente (ce n'est pas le cas ici).

Raphael

-4

Dans ce cas, A ne pouvait pas être reconnu par Turing. Prenez ceci comme exemple:

la langue B est l'union d'une langue tr (C) et d'une langue non tr (A). vous pouvez créer une machine de turing qui reconnaît B. A n'est pas tr et A ⊆ B.

Est-ce correct? je ne sais pas si c'est .. donc .. =)

Philip A.
la source

3

C \in R E

$C\in RE$

A \notin R E

$A\notin RE$

C = \emptyset

$C=\emptyset$

A

$A$

B = A \cup C

$B=A \cup C$ .

Ran G.

Le sous-langage n'est pas reconnaissable par Turing, ou pourrait-il l'être?

Réponses: