Langages indécicables

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
hansou
Messages: 9
Enregistré le: 21 Nov 2009, 21:30

Langages indécicables

par hansou » 04 Mai 2014, 13:08

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
Membre Rationnel
Messages: 654
Enregistré le: 03 Oct 2009, 15:44

par wserdx » 04 Mai 2014, 17:32

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

Thomas Joseph
Membre Rationnel
Messages: 506
Enregistré le: 22 Avr 2014, 15:49

par Thomas Joseph » 04 Mai 2014, 18:01

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
Membre Rationnel
Messages: 506
Enregistré le: 22 Avr 2014, 15:49

par Thomas Joseph » 04 Mai 2014, 18:03

wserdx a écrit: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
Habitué(e)
Messages: 5010
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 04 Mai 2014, 18:19

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
Membre Rationnel
Messages: 654
Enregistré le: 03 Oct 2009, 15:44

par wserdx » 06 Mai 2014, 10:17

hansou a écrit: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

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 23 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite