Discussion:Problème du mot

Problème du mot dans les groupes

Le problème du mot dans les groupes en général est décidable. Il s'agit de savoir si deux expressions construites à partir des générateurs $e$, $i$, $*$ et une infinité de constantes peuvent être montrées égales en utilisant les relations:

• $x*(y*z)=(x*y)*z$
• $x*e=e*x=x$
• $x*i(x)=i(x)*x=e$

Il y a un algorithme pour décider si deux expressions ou mots $m_{1}$ et $m_{2}$ sont égales ou égaux. --Pierre de Lyon (d) 17 février 2012 à 16:28 (CET)

J'ai changé « décidable » en « indécidable », sinon il y contradiction avec Novikov. Mais je ne suis plus sûr de rien. --ManiacParisien (d) 31 juillet 2012 à 07:22 (CEST)

J'ai essayé d'être plus précis. --Pierre de Lyon (d) 2 août 2012 à 11:44 (CEST)

Je commence peut-être à comprendre. Les "groupes en général" dont tu parles sont vraisemblablement les groupes libres : quand deux expressions construites comme tu dis donnent des résultats différents, les éléments du groupe sont distincts pourvu qu'il n'y ait aucune autre relation, ce qui est bien la liberté du groupe au sens qu'il n'y a pas de relateur. Cela te parait probable ? --ManiacParisien (d) 8 août 2012 à 14:59 (CEST)

Oui, mais je me place plutôt dans l'algèbre universelle, que dans le groupe libre (à une infinité de générateurs). --Pierre de Lyon (d) 11 août 2012 à 20:05 (CEST)

Tarski ?

Tarski est cité comme le premier à avoir prouvé qu'un problème de mot est indécidable. Existe-t-il un référence à ce sujet que l'on pourrait citer ? Et une date précise ? --ManiacParisien (d) 31 juillet 2012 à 07:19 (CEST)