Machine de Turing et graphes de Cayley

[Seirios]

Bonjour à tous,

Un résultat classique de théorie géométrique des groupes est l'équivalence entre le problème du mot et la construction des graphes de Cayley. Mais les démonstrations que je connais utilise la notion intuitive d'algorithme, donc j'aimerais savoir comment formaliser ces notions.

Pour le problème du mot, j'ai lu des formalisations en termes de machine de Turing : le problème du mot est résoluble dans un groupe G si l'ensemble des mots sur une partie génératrice valant l'identité est récursif.

Qu'en est-il pour le problème de la construction des graphes de Cayley, y a-t-il une formulation en terme de machine de Turing ?

Merci d'avance,
Seirios

[Seirios]

Plus généralement : Comment formaliser la notion d'algorithme dans la construction d'un graphe ?