Machine de Turing Fermé

Question

Bonjour,
svp j'ai vraiment besoin d'aide pour cet exercice,
enoncé le principe général de de reconnaissance basé sur la simplification.
à l'aide de ce principe ,dnoner
-une Machine de Turing (MT) qui reconnait les mots sur {a,b} dont la longueur est une puissance de 2.
-une Machine de Turing (MT) sur {0,1} qui calcule la representation unaire(par une séquence de 1) du nombre binaire d'entrée( avec '101', representation binaire de 5 en entrée, la sortie sera 11111).
-une MT qui effectue l'addition de 2 nombres non signés codés en binaire.

Rijina · Answer

Salut, je suis en 1ère année et on dédute avec la MT, j'ai un problème avec  le changement d'état surtout, quand est ce on doit changer d'état.
et si vous pouviez m'aider pour ce problème:
-écrire une MT qui permet de sommer deux (02) nombres binaires non signés X Y.
merci et bon courage.

torreshubert · Answer

ton probleme est simple tu décris la un exercice que l'on vous a demander de chercher c'est bien toi au moins tu cherche pour la premiere question

utilise le fait que tu trouver une MT pour les mots mirroir puis simplifier en considerant la premier partie

* seconde question utilise le fait que tu peux simuler un MT a une bande par une MT a deux bandes
sur la premiere bande tu mets le mots : sa representation binaire et tu vas la parcourir  de la droite vers la gauche
sur la deuxieme bande qui initialement est vide tu placera la representation unaire a generer du mot 
enfin pour chaque bit de la premeire bande tu double la taille de la seconde bande et tu ajoute un (1) si b=1

* enfin tu fais une addition sur une seule bande tu copie le premier mot et tu met un # puis le second et tu met un $ et en fin le symbole blanc mais avant tu ajoute des o pour que les deux mots aient la meme taille '(au debut bien sur)
puis tu fais la somme et le résultat tu le met dans la partie reservé au symbole blanc


bon il te reste maintenant a rediger ceci on se voit a la correction 
PS mais pourquoi n'as tu pas écris aux facilitateurs ils t'auraient repondu tu sais

Machine de Turing

2 réponses

Discussions similaires