Problème Machine de Turing
Marough
Messages postés
3
Statut
Membre
-
Marough Messages postés 3 Statut Membre -
Marough Messages postés 3 Statut Membre -
J'ai des difficultés à résoudre les problèmes suivants:
1- Je dois construire une machine de Turing qui décide si le contenu du ruban 1 est identique à celui du ruban 2. Les deux rubans sont initialisés non vide ( avec respectivement v,w € {0,1}*dessus. La machine doit, avec un contenu vide du ruban2 et une valeur 1 du ruban1 (si v=w) ou 0 (sinon), s’arrêter sur le ruban1.
2- pour un langage L de l'alphabet je dois montrer que si L est décidable, alors Les deux Langages:
L1 : { w € Alphabet | pour tout préfixe v de w on a v € L }
L2 : { w € Alphabet | il existe un préfixe c de W tel que v € L }
sont aussi décidables.
Pour cela je dois apparemment construire deux machines de Turing pour L1 et L2 c'est ça? Si oui comment y procéder? sinon merci de me filer un tuyau, je bloque
Merci beaucoup!
1- Je dois construire une machine de Turing qui décide si le contenu du ruban 1 est identique à celui du ruban 2. Les deux rubans sont initialisés non vide ( avec respectivement v,w € {0,1}*dessus. La machine doit, avec un contenu vide du ruban2 et une valeur 1 du ruban1 (si v=w) ou 0 (sinon), s’arrêter sur le ruban1.
2- pour un langage L de l'alphabet je dois montrer que si L est décidable, alors Les deux Langages:
L1 : { w € Alphabet | pour tout préfixe v de w on a v € L }
L2 : { w € Alphabet | il existe un préfixe c de W tel que v € L }
sont aussi décidables.
Pour cela je dois apparemment construire deux machines de Turing pour L1 et L2 c'est ça? Si oui comment y procéder? sinon merci de me filer un tuyau, je bloque
Merci beaucoup!
A voir également:
- Problème Machine de Turing
- Machine virtuelle windows - Guide
- Time machine - Guide
- Machine virtuelle gratuite - Télécharger - Émulation & Virtualisation
- Carte de bus dans la machine à laver - Forum Matériel & Système
- Dépôt machine à laver - Guide
1 réponse
Dans quel langage de programmation veux-tu le faire ?
pour un langage L de l'alphabet je dois montrer que si L est décidable, alors Les deux Langages sont aussi décidables.
Un langage [de programmation je suppose] décidable ? Qu'est-ce que tu entends par là ? Le concept de décidabilité s'accompagne généralement d'une question ou d'un problème.
Note: le signe "appartient à" n'a qu'un seul trait horizontal, contrairement au signe "euro" que tu utilises.
La curiosité est une excellente qualité !
pour un langage L de l'alphabet je dois montrer que si L est décidable, alors Les deux Langages sont aussi décidables.
Un langage [de programmation je suppose] décidable ? Qu'est-ce que tu entends par là ? Le concept de décidabilité s'accompagne généralement d'une question ou d'un problème.
Note: le signe "appartient à" n'a qu'un seul trait horizontal, contrairement au signe "euro" que tu utilises.
La curiosité est une excellente qualité !
J'ai pas besoin de programmer, il suffit de décrire la machine construite (états, fonction de transition...etc), son fonctionnement, et de dessiner le graphe correspondant.
Sinon un langage est décidable ou récursif ça revient au même, c'est quand la Machine de Turing reconnait le langage s’arrete toujours.
Mais non mais non, c'est une très bonne idée au contraire ^^
Désolé pour le deuxième problème je n'ai toujours pas compris, mais je pense que c'est plutôt dû à mon manque de connaissances dans le domaine (bien que je serais ravi d'en apprendre plus) qu'à un vocabulaire indapté.
À quoi correspondent v et w ?