algorithme de Markov

Imaginons une suite de lettres dans laquelle on cherche certains groupes pour les remplacer. Une liste indique les remplacements possibles et leur ordre de priorité. À chaque tour, on choisit la première règle applicable, puis on obtient une nouvelle suite de lettres.

L’algorithme de Markov est ce procédé de réécriture répété. Une transformation locale, limitée à quelques symboles, peut ainsi participer à un calcul complet.

Un algorithme de Markov agit sur une chaîne de symboles au moyen d’une liste ordonnée de règles de production. Chaque règle associe un sous-mot à un sous-mot de remplacement. L’ordre de la liste fixe la priorité : parmi les règles dont le motif apparaît dans la chaîne courante, celle de plus haute priorité est appliquée.

Dans la convention normale, l’application remplace l’occurrence la plus à gauche du motif retenu et produit une nouvelle chaîne. Le même examen recommence sur cette chaîne. Le calcul s’arrête lorsqu’aucune règle ne s’applique, ou juste après l’emploi d’une règle marquée comme terminale. Si les réécritures se poursuivent sans fin, il ne fournit pas de chaîne finale.

Ce modèle est Turing-complet : il peut exprimer tout calcul réalisable par une machine de Turing, avec un autre mécanisme élémentaire. Cette universalité concerne le modèle dans son ensemble, et non chaque liste particulière de règles. Le système a été introduit par Andrei Andreïevitch Markov.

On part d’une chaîne et d’une liste ordonnée de règles « motif → remplacement ». À chaque étape : 1. parcourir les règles dans l’ordre ; 2. retenir la première dont le motif est présent ; 3. remplacer l’occurrence la plus à gauche de ce motif ; 4. reprendre l’examen sur la chaîne obtenue. Le procédé s’arrête si aucune règle ne s’applique ou si la règle exécutée est terminale.

Le procédé demande une chaîne initiale, un ensemble de symboles et une liste de règles placées dans un ordre déterminé. Chaque côté d’une règle est un sous-mot explicite : le côté gauche est recherché, le côté droit le remplace. À une étape donnée, la priorité choisit une règle parmi celles qui sont applicables, puis la convention de gauche choisit l’occurrence remplacée. Une règle doit aussi être identifiée comme ordinaire ou terminale.

Si deux remplacements sont proposés sans ordre de priorité, la chaîne suivante n’est pas déterminée par cette procédure. Il faut alors fixer cet ordre avant l’exécution, ou décrire le dispositif comme un système de réécriture plus général. Même avec un ordre fixé, l’existence d’un résultat final exige que la suite des réécritures s’arrête.

Prenons la chaîne initiale aab. Deux règles ordinaires sont ordonnées : la règle 1, ab → ba, est prioritaire sur la règle 2, aa → a.

1. Dans aab, les motifs ab et aa sont présents. La priorité impose la règle 1 : aab → aba.

2. Dans aba, le motif ab est présent. La règle 1 donne aba → baa.

3. Dans baa, seule la règle 2 s’applique : baa → ba.

La chaîne finale est ba, car elle ne contient ni ab ni aa. Le contrôle consiste à rechercher de nouveau les deux motifs : aucun n’apparaît. Le schéma associé rend visible l’ordre complet des quatre états.

Pour exécuter une petite liste de règles à la main, on souligne tous les motifs présents, puis on compare leurs priorités. Après le choix de la règle, on remplace son occurrence la plus à gauche. Ces deux choix successifs évitent de confondre priorité de la règle et position du motif.

Pour décrire un calcul symbolique déterministe, on consigne la chaîne après chaque remplacement. Si plusieurs règles restent possibles sans ordre pour les départager, un système de réécriture général décrit mieux la situation.

Pour étudier la puissance d’un modèle de calcul, on peut traduire des opérations en règles de réécriture. La machine de Turing reste une autre représentation lorsque le déplacement sur un ruban est l’objet que l’on veut suivre.

Chaîne de Markov. Elle décrit des transitions entre états selon des probabilités. L’algorithme de Markov décrit ici des remplacements prioritaires de sous-mots. Une question portant sur la probabilité du prochain état relève donc d’une chaîne de Markov, pas de cette procédure de réécriture.

Machine de Turing. Les deux modèles ont la même puissance de calcul, mais leurs opérations élémentaires diffèrent. Une machine de Turing lit et modifie un support selon ses propres transitions ; l’algorithme de Markov transforme directement des sous-mots selon une liste prioritaire.

Il existe deux ordres de choix. On retient d’abord la règle applicable de plus haute priorité, puis l’occurrence la plus à gauche de son motif. Choisir d’abord le motif le plus à gauche peut donc produire une chaîne incorrecte.

Une suite peut ne jamais se terminer. Le retour périodique d’une même chaîne, ou une croissance indéfinie observée pendant l’exécution, empêche d’annoncer une chaîne finale. Il faut alors étudier la terminaison au lieu de poursuivre comme si l’arrêt était garanti.

Turing-complet ne signifie pas universel pour chaque programme. Une liste de deux règles comme celle de l’exemple ne réalise que les transformations qu’elle encode. Pour revendiquer un autre calcul, il faut fournir les règles qui le représentent et vérifier leur exécution.

La chaîne de Markov permet de distinguer un modèle probabiliste de transitions d’un système déterministe de réécriture.

La machine de Turing offre un autre mécanisme pour représenter des calculs, avec une puissance équivalente à celle des algorithmes de Markov.