Problème Machine de Turing

Fermé

Marough Messages postés 3 Date d'inscription jeudi 16 juin 2016 Statut Membre Dernière intervention 16 juin 2016 - 16 juin 2016 à 07:26
Marough Messages postés 3 Date d'inscription jeudi 16 juin 2016 Statut Membre Dernière intervention 16 juin 2016 - 16 juin 2016 à 13:19

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!

A voir également:

Problème Machine de Turing
Machine virtuelle windows - Guide
Time machine - Guide
Machine virtuelle gratuite - Télécharger - Émulation & Virtualisation
Washing machine mac - Guide
Id machine ✓ - Forum Logiciels

1 réponse

Réponse 1 / 1

paly2 Messages postés 254 Date d'inscription vendredi 29 août 2014 Statut Membre Dernière intervention 15 février 2018 25
Modifié par paly2 le 16/06/2016 à 07:41

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é !

Marough Messages postés 3 Date d'inscription jeudi 16 juin 2016 Statut Membre Dernière intervention 16 juin 2016
16 juin 2016 à 07:52

Salut! Désolé de pas utiliser les mots qu'ils faut, j'ai fait l'erreur de poursuivre mon Master en Allemagne, j'ai essayé de traduire les énoncés mais il se peut que les termes ne soient pas 100% les mêmes que ceux en Français.

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.

paly2 Messages postés 254 Date d'inscription vendredi 29 août 2014 Statut Membre Dernière intervention 15 février 2018 25
16 juin 2016 à 12:13

j'ai fait l'erreur de poursuivre mon Master en Allemagne
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 ?

Marough Messages postés 3 Date d'inscription jeudi 16 juin 2016 Statut Membre Dernière intervention 16 juin 2016
16 juin 2016 à 13:19

Pour le premier problème v et w c'est les contenus des rubans 1 et 2. En gros c'est ce qu'on cherche à comparer pour savoir s'ils sont identiques ou pas.

Discussions similaires

Carte bancaire passée à la machine à laver

Carte bleu passé a la machine à laver

Machine à laver CB

message"press a key to reboot"

C’est pour savoir si ma carte de bus peut encore marcher