Discussion :

[patrick974]

bonjour tout le monde,
je dois ecrire une machine de Turing qui calcule la fonction f(n)=2n.
Dans un premier temps, je dois ecrire cette machine pour une notation unaire (par exemple f(0)=00, f(00)=0000, f(000)=000000) puis en notation binaire.
Mon probleme est que je ne sais pas dutout dans quelle direction aller pour ecrire une telle machine.
Est ce que quelqu'un pourai m'aiguiller pour l'ecriture de cette machine en notation unaire s'il vous plait ?
Je pense que je pourai ensuite me debrouiller pour ecrire la deuxieme machine tout seul.
Je vous remercie de m'avoir accordé un peut de votre temps en lisant ce message.
A bientot, en espérant avoir une réponse.
Au revoir.

re Bonjour,
je me suis trompé dans l'exemple de la fonction f pour la notation unaire. Les entiers naturels commencent a zero, donc on devrai pplutot avoir quelque chose comme :
f(0)=0, f(00)=000, f(000)=00000, f(0000)=0000000
f(0)=0, f(1) =2 f(2) =4 f(3) =6
Voila, je suis toujours en train de chercher une solution a ce probleme, si vous pouvez m'aider n'hesitez pas .
Merci, au revoir.

[Garulfo]

As-tu une idée de la manière de faire ?
Je veux dire en français.

Car l'idée est simple. Si tu sais déjà ce que tu cherches à faire tu verras que c'est finalement très simple. Comme en programmation, on fait la conception avec l'implémentation quoi

[ToTo13]

bonjour,

je suis d'accord, dit nous comment tu penses t'y prendre. Le principe de résolution des machines de Turing est presque toujours le même.

Pour le cas binaire, il est en fait BEAUCOUP plus simple. Multiplier un nombre binaire par deux revient à faire un décalage de bit vers la gauche

[SpiceGuid]

La solution à la Church pour la notation unaire:

Code Caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
type unary  = {c: 'a.('a -> 'a) -> ('a -> 'a)}
let  zero   = {c = fun f x -> x}
let  add1 n = {c = fun f x -> f (n.c f x)}
let  mul2 n = n.c (fun x -> add1 (add1 x)) zero;

[patrick974]

Bonjour a vous tous,
merci de m'avoir accordé un peu de votre temps.
SpiceGuid j'ai du mal a comprendre ta solution, dans la mesure jai fait du caml pendant 3 mois seulement et j'etais en premiere année (ça remonte ...). Mais je te remercie de me proposer une telle solution.

Garulfo et ToTo13 vous avez entierement raison. Je venais de finir toute une serie d'exercices lorsque j'ai abordé celui la et j'etais un peu fatigué (meme si ce n'est pas une excuse ). Je pense avoir la solution pour les deux problèmes :

pour la notation unaire :
Q={ q0, q1, q2, q3, q4 }
Sigma={ 0 }
Gama={ 0, A, B, # }
s=q0
B=#
F={ q4 }
delta est definie par :
( q0, 0 ) -> ( q1, B, R )
( q1, 0 ) -> ( q1, A, R )
( q1, # ) -> ( q2, 0, L )
( q2, 0 ) -> ( q2, 0, L )
( q2, A ) -> ( q3, 0, R )
( q2, B ) -> ( q4, #, R )
( q3, 0 ) -> ( q3, 0, R )
( q3, # ) -> ( q2, 0, L )
Il suffisait juste de remarquer que la multiplication de n par 2 revient a ajouter n-1 fois 0 a la notation unaire.

Pour la notation binaire, la solution est vraiment facile, et je pense que j'ai la plus petite machine qui fasse le calcul demandé.

Maintenant, je voudrai savoir si il est possible d'ameliorer ma premiere MDT (pour la notaion unaire). Qu'en pensez vous ?
Merci encore, au revoir en espérant une réponse.