Discussion :

[DarK Sidious]

Bonsoir,

J'ai un problème d'algorithmique à résoudre : comment convertir un nombre binaire au format "bâton" avec une machine de turing.

Exemple, si la bande d'entrée contient "1101" cela doit sortir "aaaaaaaaaaaaa", où a symbolise un bâton donc

Si quelqu'un a une idée, je suis preneur !

[méphistopheles]

il me faudrais ta methode de comptage, mais subposons que tu aie ton nombre, il te suffit de faire valeur du dernier +somme des 2^position des 1-1 :par exemple,
11= 2^1+1 =3
de même, 1101= 2^3+2^2+1=13

ensuite, tu fait une petite manipulation de strings pour mettre autemps de a.

salut

[Trap D]

Salut
Ça doit être un truc comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
debut
  // affichage est la chaîne qui sera affichée à la fin
  affichage <- ""
  // valeur_en_ cours nombre de baton à ajouter si on lit un 1
  valeur_en_cours = 1
  // car est le caractère qui vient d'être lu 3 possibilité 0, 1 ou TERMINE
  // car_lu() est la fonction d'obtention du prochaine caractère
  // nombre_batons(n) crée un chaîne composée de n batons.
  car <- car_lu()
  tant que car <> TERMINE faire
    si car = 1 alors
       affichage <- affichage + nombre_batons(valeur_en_cours)
    fin si
    valeur_en_cours <- 2 * valeur_en_cours
    car <- car_lu()
  fin tant que
  afficher(affichage)
fin

Je me rapelle plus bien des ordres pour les machines de Turing, mais ça peut-être traité dans car_lu() et nombre_batons(valeur_en_cours)

[DarK Sidious]

Merci pour vos réponses.

méphistopheles : malheureusement, ce n'est pas aussi facile avec une machine de turing car elle n'a pas de mémoire, juste des états (exemple, l'état 1 : on a lu un 1, état 2, on a lu un 0, état 11, on a lu un 1 et on lit un autre 1, etc. et le nombre d'état est fini !).

Trap D : oui, ca me paraît pas mal, mais il y a un hic : dans ton algo tu stocke 2 choses : la valeur en cours (chose déjà qui pose problème car les entiers écrit en binaire ne sont pas finis => ca implique une infinité d'états), et l'affichage qui doit être fait, là aussi ca demande une infinité d'états.

Ce que je cherche, ce serait un algorithme général qui pour n'importe quel nombre puisse le convertir en bâton avec un nombre d'états limité de la machine (par exemple 10 ou 20 états différents et non pas 1 pour chaque caractère lus).

[Trap D]

Stocker l'affichage n'est pas un problème, on peut afficher les bâtons quand on lit les caractères, par contre le il faut quand même bien mémoriser l'état pour savoir le nombre de bâtons à afficher.

[DarK Sidious]

ben oui, c'est ce qui me pose problème car avec des nombres très grands, il faudras beaucoup d'états !

Il doit bien existe une astuce pour afficher un multiple de la position actuelle (1 bâton pour le premier bit, 2 bâton pour le 2ème, 4 bâton pour le 3ème etc.). Car sinon, je suis bloqué !

[Trap D]

J'ai une vague idée :
On peut imaginer un système d'ecriture des batons basé sur le principe suivant
Au depart la tête d'écriture est sur une case marquée D
On lit un premier caractère 0 ou 1
La tête d'écriture ecrit 0 ou 1 puis ecrit un espace
Ensuite
Tant que on n'a pas lu TERMINE la tête d'écriture écrit 2 fois ce qui a été ecrit au tout précédent (délimité par des espaces) avec le caractère adéquat bien entendu et termine par espace.
Lorsque c'est terminé on balaie tout ce qui a été écrit en remplaçant les 1 par 'a' et en éliminant les 0 et les espaces de la chaîne.

[DrTopos]

Quand on veut représenter une fonction (récursive évidemment) par une machine de Turing, il faut d'abord choisir le vocabulaire de la machine. En l'occurence on choisit:

0 et 1 pour la numération binaire
a pour la numération unaire

On aura aussi besoin de symboles marqueurs, car une machine de Turing stocke toutes ses données sur un unique ruban. Il faut donc des marqueurs pour repérer les endroits où sont ces données. On pourra utiliser b et e (begin/end) pour délimiter l'input et B et E pour délimiter l'output. On aura d'ailleurs besoin d'autres marqueurs.

Rappelons qu'une machine de Turing est un automate fini (nombre fini d'états, nombre fini de transitions et nombre fini de symboles manipulés), qu'elle a une tête (de lecture/écriture), et qu'à chaque mouvement elle lit le symbole en face de la tête, le remplace éventuellement par un autre et fait soit un pas à gauche, soit un pas à droite. Elle peut également décider de s'arrêter. Tout le reste est interdit.

A partir de ces principes de base, on peut faire des sous-automates pour des tâches précises. Par exemple, trouver le b sachant qu'on est à droite de ce b. Pour cela, un automate à un seul état suffit. Il y a une transition sur lui même avec pas à gauche si le symbole n'est pas b, et sortie si le symbole est b. On aura besoin d'un certain nombre d'outils similaires, que je ne vais pas détailler ici, mais le principe est le même.

La machine démarre donc avec le ruban suivant (par exemple):

Code :

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

1
2
 
b0110100100011101e

c'est-à-dire un nombre écrit en base 2, délimité à gauche par b et à droite par e. La séquence entre b et e est ce qu'on appelle l'input. La tête de la machine est en face du b (par exemple).

La méthode consiste à effacer l'input tout en construisant l'output. On va effacer l'input en commençant par la gauche, et l'output sera construit à droite de l'input. La première chose à faire est donc de construire un sous-automate A1 qui va fabriquer un output vide (donc de la forme BE) . A la sortie de ce sous-automate, le ruban sera le suivant:

Code :

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

1
2
 
b0110100100011101eBE

Ensuite, il faut un sous-automate A2 qui va faire le calcul proprement-dit. La méthode consiste à parcourir l'input de gauche à droite, et a faire une boucle de A2 pour chaque chiffre 0 ou 1 rencontré. Cette boucle doit:

- doubler l'output dans le cas d'un 0,
- doubler l'output et ajouter un a, dans le cas d'un 1.

En fait cela signifie que A2 est fait de deux sous-automates principaux A20 et A21, le premier traitant le cas de 0 et le deuxième traitant le cas de 1.

Doubler l'output peut se faire comme suit. S'il est vide (BE) il reste comme il est puisque 2*0=0. S'il n'est pas vide, il faut commencer par positionner la tête en face du dernier a (ce qui revient à rechercher E puis faire un pas à gauche). On remplace ce a par le symbole D (comme 'dernier'). Puis on va vers la gauche jusqu'à trouver B, et on fait un pas à droite. On est donc sur le premier a (qui est peut-être D). Si c'est D ça veut dire que la valeur de l'output était 1, et qu'il faut donc mettre un autre a. On remplace donc D par a et on fait un pas à droite, on remplace E par a et on fait un pas à droite, et enfin on écrit E. L'output est donc passé par les états suivants:

Code :

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

1
2
3
4
5
6
 
BaE
BDE
BaE
Baa
BaaE

il a donc bien doublé.

Si au contraire, après le pas vers la droite partant de B, on trouve a, on remplace cet a par X. Puis on se déplace vers la droite jusqu'au E, qu'on remplace par a, puis on remet encore E à droite. Par exemple:

Code :

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

1
2
3
4
5
6
 
BaaaaaE
BaaaaDE
BXaaaDE
BXaaaDa
BXaaaDaE

On revient ensuite vers la gauche jusqu'au X, qu'on remplace par a en faisant un pas à droite on écrit alors X à cette place, sauf si on lit D. On est alors sur le deuxième a et on recommence. Quand on atteint D, on le remplace par a et on fait une dernière fois la boucle. Par exemple, voici ce que donne la duplication de BaaaE:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
BaaaE
BaaDE
BXaDE
BXaDa
BXaDaE
BaXDaE
BaXDaa
BaXDaaE
BaaDaaE
BaaaaaE
BaaaaaaE

On fait un automate analogue pour la duplication plus 1. C'est le même automate, sauf qu'on branche un petit bout d'automate supplémentaire à la sortie pour ajouter un a de plus.

Un fois que c'est fait, pour chaque 0 ou 1 de l'input qui n'est pas effacé (on prend toujours celui qui est le plus à gauche, c'est à dire par exemple qu'on déplace b vers la droite à chaque effacement), on se branche sur l'un des deux automates A20 ou A21 suivant qu'on a lu 0 ou 1.

Quand enfin on lit e dans l'input, le calcul est fini, et on peut brancher un dernier sous-automate pour placer la tête devant B (par exemple).

Si je ne me suis pas trompé, c'est ça qu'il te faut. Je te laisse développer les détails.

[DarK Sidious]

Ouaou ! Merci DrTopos !

En effet, avec des fonctions récursives, ca doit être possible à faire. Ca m'a l'air compliqué, mais ca doit marcher en effet.

Je vais essayer d'appliquer ta méthode et voir ce que ca donne (je sens que je vais avoir un sacré mal de tête ce soir .

Si quelqu'un a plus simple, je prends ! )

Je vous tiendrais au courant !

[Trap D]

DrTopos >> Est-ce que ce que j'ai eu comme idée pour l'affichage des batons (le post juste au-dessus du tien) était faisable simplement avec une machine de Turing ? Merci.

[DrTopos]

Salut Trap D. Au moment, ou j'ai posté, je n'avais pas encore vu ton post, sinon j'en aurai tenu compte. Ca ressemble à ce que j'ai écrit, mais je ne suis pas sûr de tout comprendre.

Au depart la tête d'écriture est sur une case marquée D
On lit un premier caractère 0 ou 1

Ce n'est pas très clair, car si on est sur une case marquée D on lit forcément D. Tu sous entends peut être qu'on fait un pas à droite à partir de ce D (qui doit correspondre à mon b), et que c'est là qu'on lit 0 ou 1.

La tête d'écriture ecrit 0 ou 1 puis ecrit un espace

Il faut qu'elle écrive sans compromettre (effacer) ce qui n'a pas encore été lu. Il faut donc qu'elle se déplace, éventuellement sur de longues distances. En fait, après cette opération, il me semble que tu as seulement inséré des espaces entre tous les chiffre de l'input.

Ensuite
Tant que on n'a pas lu TERMINE

je suppose que TERMINE est en fait le délimiteur droit de l'input (e chez moi).

la tête d'écriture écrit 2 fois ce qui a été ecrit au tout précédent (délimité par des espaces) avec le caractère adéquat bien entendu et termine par espace.

C'est là sans doute que la duplication se passe. Il est clair qu'il faut multiplier par 2 quelquepart. Mais cette opération elle-même requiert pas mal d'aller retours. La duplication d'une séquence se fait forcément symbole par symbole.

Je suppose que cette opération est effectuée pour chaque chiffre de l'input. Donc le résultat est qu'on multiplie par 2 le nombre de symboles dans l'output. Ca ne doit pas être correct, car il faut faire une chose différente suivant qu'on lit 0 ou 1. Si on lit 1, il faut doubler le résultat et ajouter encore 1.

Lorsque c'est terminé on balaie tout ce qui a été écrit en remplaçant les 1 par 'a' et en éliminant les 0 et les espaces de la chaîne.

Donc si j'ai bien compris les 1 jouent le rôle des a. Je n'ai pas compris à quoi servait de mettre des espaces. De toute façon, je ne pense pas que ça donne le résultat attendu. Par exemple (en supposant que j'ai bien compris ta méthode) en partant de

Code :

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

1
2
 
100

c'est à dire 4 en base 2, tu obtiendrais successivement:

Code :

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

1
2
3
4
5
6
7
 
1_
1_1_
1_1_0_
1_1_0_1_1_0_
1_1_0_1_1_0_0_
1_1_0_1_1_0_0_1_1_0_1_1_0_0_

au final tu te retrouves avec 8 au lieu de 4 (mais je n'ai peut être rien compris).

Remarques générales: Ce qui est important dans les machines de Turing est de délimiter les données dont la longueur peut être quelconque par des symboles spéciaux. Ce sont ces symboles qui permettent de savoir qu'une opération est terminée. En fait ils jouent le rôle des tests de sortie de boucle en programmation impérative habituelle.

Ce que tu proposes (indépendamment du fait que ça ne calcule peut-être pas ce qui était demandé) est bien entendu réalisable par une machine de Turing. De toute façon, le théorème fondamental de cette théorie est que toute fonction récursive (même partielle) est calculable par une machine de Turing, et réciproquement que toute fonction (même partielle) calculable par une machine de Turing est une fonction récursive. En d'autre termes tout calcul qui peut être fait par un PC peut l'être par une machine de Turing et réciproquement. Bien sûr ici par fonction récursive on entend toutes les fonctions engendrées par certains principes: duplication, échange, destruction, etc... et certaines formes de récursion.

ce qui me pose problème car avec des nombres très grands, il faudras beaucoup d'états !

Il faut bien comprendre qu'une machine de Turing a un nombre fini (et fixe) d'états, et qu'elle est quand même capable de calculer la fonction qu'elle représente aussi grand que soit l'input.

[Trap D]

Tout d'abord merci d'avoir pris le temps de me répondre.
Celà fait longtemps que j'ai entendu parler des machines de Turing, donc j'ai forcément sauté des étapes dans le mécanisme.

On peut imaginer un système d'ecriture des batons basé sur le principe suivant
Au depart la tête d'écriture est sur une case marquée D
On lit un premier caractère 0 ou 1
La tête d'écriture ecrit 0 ou 1 puis ecrit un espace
Ensuite
Tant que on n'a pas lu TERMINE la tête d'écriture écrit 2 fois ce qui a été ecrit au tout précédent (délimité par des espaces) avec le caractère adéquat bien entendu et termine par espace.

Mon principe était le suivant :
On lit de droite vers gauche le nombre, on écrit de gauche vers droite l'output
Zone d'écriture une partie du ruban ou il n'y a que des E.
Phase d'initalisation
on lit le premier caractère 0 ou 1 (et on l'efface d'après ce que je compris)
on se place au début de la zone d'écriture (marquée E) on inscrit le caractère lu et on ecrit un caractère de fin d'écriture _
Fin de la phase d'initialisation
Boucle principale de l'algo qui se termine lorsqu'on ne lit plus 0 ou 1 mais e
on revient lire un nouveau caractère 0, 1
on retourne dans la zone d'écriture que l'on parcourt jusqu'au dernier _
exemple de ce qu'il y aurait d'écrit si on avait lu "010" dans la partie lecture du ruban E0_11_0000_E et que le prochain caractère lu est 1:
on compte (celà doit être possible avec un automate auxiliaire) le nombre de caractères 0 soit 4, on retourne sur le _ avant le E, on se déplace à droite et on écrit 8 1 et _, on obtient donc E0_11_0000_11111111_E
On revient lire un chiffre
etc
Fin algo de lecture
On obtient donc pour l'input "11010" lu de droite vers gauche l'output E0_11_0000_11111111_1111111111111111_E
Phase de nettoyage de l'output
on parcourt l'output en déplaçant si possible les 1 (en les transformant en a) vers la gauche pour remplacer les _ ou les 0 par des a.
(l' automate lit le 1, le remplace par un _ revient en arrière jusqu'a trouver a ou E, se déplace d'une case vers la droite et écrit le a, et repart vers la droite jusqu'à lire 1 ou E, s'il lit E la phase de nettoyage est terminée).
Donc pour un input de "11010" on a un output Eaaaaaaaaaaaaaaaaaaaaaaaaaa__________E
On peut éventuellement remplacer les _ par des E lorsque tous les 1 on été déplacés.
Le nombre 11010 en binaire est 26 en base 10. J'ai bien 26 bâtons.

[DrTopos]

On lit de droite vers gauche le nombre,

Tu analyses donc l'input en commençant par le chiffre des unités (dans ma solution, on commence par le chiffre le plus signifiant). Mais bien entendu, les deux méthodes sont possibles.

Zone d'écriture une partie du ruban ou il n'y a que des E.

Ca me gène un peu, car cela ne pourra marcher que si le ruban est rempli vers la droite d'une infinité de E. Il ne faut pas oublier que l'input n'est pas limité en taille. Tu risques le dépassement de buffer si tu n'as qu'un nombre fini de E. Je ne pense pas qu'on ait droit à cette hypothèse. Le ruban ne contient à tout moment qu'un nombre fini de cases non vides. Mais tu dois pouvoir modifier facilement ta méthode. En fait, il faut utiliser des marqueurs de début et de fin et les déplacer pendant le calcul.

exemple de ce qu'il y aurait d'écrit si on avait lu "010" dans la partie lecture du ruban E0_11_0000_E

Je commence à comprendre ce que tu veux faire.

et que le prochain caractère lu est 1:
on compte (celà doit être possible avec un automate auxiliaire) le nombre de caractères 0 soit 4, on retourne sur le _ avant le E, on se déplace à droite et on écrit 8 1 et _, on obtient donc E0_11_0000_11111111_E

Effectivement, ton algo (que je viens enfin de comprendre) me semble correct. Pour le nettoyage terminal, pas de bp. par contre, tu est amené (comme dans ma solution) a dupliquer une séquence, puisque tu dois (dans ton exemple) produire la séquence 11111111 à partir de la séquence 0000. Tu as donc besoin d'un sous-automate faisant la duplication (en fait, comme dans le cas de ma solution, de deux sous-automates, un pour le cas ou on lit 0, et ou on transforme 0000 en 00000000, et un pour le cas où on lit 1, et où on transforme 0000 en 11111111). Maintenant, pour faire cet automate de duplication:

(celà doit être possible avec un automate auxiliaire)

il faut une méthode de marquage (le X et le D de ma solution, surtout le X d'ailleurs, c'est vraiment lui qui sert de compteur), car la machine de Turing n'a pas d'autre mémoire que son ruban et l'état dans lequel elle se trouve. En fait, dupliquer c'est simplement recopier la séquence à coté d'elle même. Il faut donc un marqueur pour savoir où on en est de ce recopiage.

[Trap D]

Justement pour le problème de la multiplication par 2 j'ai pensé à cette solution :
E0_11_0000_11111111_E
Le curseur se situe sur le _ le plus à droite
il lit le caractère le remplace par 2, va écrire le bon caractère à droite, dans mon exemple précédent un 1 et ajoute un _ et un E après
on se trouve dans la situation
E0_11_0000_11111112_1E
Le curseur revient à gauche rencontre un 2, il le transforme en 3 retourne à droite ecrire un 1 et ajouter le _ et le E.
On a maintenant
E0_11_0000_11111113_11E
Le curseur retourne sur la gauche rencontre le _ et le(s) 3 les saute et s'arrète au 1, le remplace par un 2 va écrire à droite un 1, un _ et E revient en arrière sur le 2 remplace par 3 et retourne à droite ...
Lorsque le curseur rencontre sur son retour arrière le _ il retransforme les 3 en leur caractère d'origine (on peut imaginer les caractère 2 et 3 pour 1 et 4 et 5 pour 0)

Je pense que ça doit résoudre le problème de la multiplication par 2.

En tout cas ça me rajeunit en me rappellant mes études d'info

[DrTopos]

Attention, tu utilises 1,2,3,4,5 etc... alors que tu n'as droit qu'à un nombre fini de symboles.

[Trap D]

Non 2 et 3 pour remplacer le 1 lors de la multiplication, 4 et 5 pour remplacer le 0, c'est tout.
On lit 1 on le remplace par 2 on va écrire le bon caractère au bon endroit on revient on lit 2 on le remplace par 3, on va écrire le bon caractère on revient on saute les 3 et on lit un autre 1 ou _ (si _ on repart sur la droite pour remplacer tous les 3 par 1 et on repart dans la zone d'input lire un caractère)
Pour le 0 on le remplace par 4 on va écrire le bon caractère au bon endroit on revient on lit 4 on le remplace par 5 et on repart vers la droite écrire le bon caractère, on revient sur la gauche, one saute les 5 et on lit un 0 ou un _, (si c'est _ on repart sur la droite pour remplacer tous les 5 par 0 et on repart dans la zone d'input lire un caractère)

[DarK Sidious]

En fait, il y a beaucoup plus simple, je viens tout juste de m'en rendre compte :

Il suffit de décrémenter la variable écrite sur le ruban, ainsi, à chaque décrémentation, on affiche un a à droite du nombre entré, et au bout de k décrémentation (donc le nombre initial est k), on obtiens k a sur la bande, et plus de problème d'états et de règles infinies.

Pour ce à qui ca interesse, voici la machine, en 2 règles, et 7 états :

Etat actuel || Caractère lu || Etat suivant || Caractère écrit || Deplacement de la tête de lecture

0 || 1 || 1 || 0 || D
0 || 0 || 0 || 1 || G
0 || a || 0 || a || G
1 || ' ' || 0 || a || G
1 || 0 || 1 || 0 || D
1 || 1 || 1 || 1 || D
1 || a || 1 || a || D

Vous pouvez essayer, ca marche à merveille.

Merci encore pour votre aide et pour le temps passer sur mon problème !

[DrTopos]

Il suffit de décrémenter la variable écrite sur le ruban, ainsi, à chaque décrémentation, on affiche un a à droite du nombre entré, et au bout de k décrémentation (donc le nombre initial est k), on obtiens k a sur la bande

Je suis bien d'accord que décrémenter k (je suppose que 'k' est tout simplement l'input) en ajoutant un 'a' à chaque fois dans l'output marche. Seulement, décrémenter l'input ne semble pas aussi simple que tu le dis.

, et plus de problème d'états et de règles infinies.

Il n'y avait rien d'infini dans ce que Trap D et moi avons proposé.

Pour ce à qui ca interesse, voici la machine, en 2 règles, et 7 états :

Etat actuel || Caractère lu || Etat suivant || Caractère écrit || Deplacement de la tête de lecture

0 || 1 || 1 || 0 || D
0 || 0 || 0 || 1 || G
0 || a || 0 || a || G
1 || ' ' || 0 || a || G
1 || 0 || 1 || 0 || D
1 || 1 || 1 || 1 || D
1 || a || 1 || a || D

Vous pouvez essayer, ca marche à merveille.

Merci encore pour votre aide et pour le temps passer sur mon problème !

Je ne comprends pas. Tu dis qu'il y a 7 états, mais je ne vois que deux noms pour ces états: 0 et 1. Il doit y avoir quelque chose qui cloche.

[DarK Sidious]

Oups, je voulais dire : 2 états et 7 règles bien sûr.

Décrémenter k est très simple en fait :
Avec la tête de lecture à droite : on inverse tout les chiffres binaires (donc 0 devient 1 et 1 devient 0) jusqu'à ce que la machine lise le premier 1 (décrémentation classique donc) et ensuite, rajouter un a à droite du nombre d'entrée, et le tour est joué !

[DrTopos]

Effectivement, ça a l'air de très bien marcher. C'est très sioux. Bravo.