Langages indécicables

[hansou]

Bonjour,

J'essaye depuis plusieurs jours de trouver la solution à cette question :

Soient L1 et L2 deux langages indécidables.
Si L1 et L2 sont deux langages indécidables. Peut-on avoir L1 L2 indécidable ? Si oui donner un exemple, sinon justier brièvement.

Merci d'avance de votre aide

[wserdx]

bonjour,
peux-tu rappeler ce qu'est un langage indécidable? Tu auras peut-être ainsi plus de réponses

[Thomas Joseph]

Bonjour,

étant néophyte sur la théorie de la décidabilité et des langages, ma réponse sera peut-être ridicule, mais je tente malgré tout, car la réponse me parait évidente :
- L1 indécidable signifie que certains mots sont indécidables
- L2 indécidable signifie que certains mots sont indécidables
Si un même mot indécidable appartient à L1 et L2 alors L1interL2 est indécidable.

Pour trouver un exemple : pourrais-tu préciser le contexte de ton travail ?

[Thomas Joseph]

bonjour,
peux-tu rappeler ce qu'est un langage indécidable? Tu auras peut-être ainsi plus de réponses

hansou confirmera, mais il me semble que la définition que nous pouvons utiliser est
"Un langage L est décidable lorsque chacun de ses mots est décidable par une machine de Turing" "(c'est à dire que la machine s'arrête)

[Doraki]

Non, les machines de Turing ne reconaissent pas des mots, mais des langages.
Si tu veux faire une machine qui reconnait 1 seul mot, c'est complètement trivial (tu peux même faire ça avec un automate). Donc ton concept de "mot indécidable" est un peu bidon.


Un langage indécidable c'est un langage pour lequel il n'existe pas de machine de turing qui pour chaque mot que tu lui donnes, répond en temps fini si le mot est dans le langage ou non.

A part ça moi je propose de prendre L1 = L2 >_> <_< >_>

[wserdx]

Bonjour,

J'essaye depuis plusieurs jours de trouver la solution à cette question :

Soient L1 et L2 deux langages indécidables.
Si L1 et L2 sont deux langages indécidables. Peut-on avoir L1 L2 indécidable ? Si oui donner un exemple, sinon justier brièvement.

Merci d'avance de votre aide

As-tu eu ta réponse finalement?

Un lien intéressant sur les langages formels