Discussion:Problème du mot
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Ébauche | À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Problème du mot dans les groupes[modifier le code]
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 , , et une infinité de constantes peuvent être montrées égales en utilisant les relations:
Il y a un algorithme pour décider si deux expressions ou mots et 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)
- 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)
- J'ai essayé d'être plus précis. --Pierre de Lyon (d) 2 août 2012 à 11:44 (CEST)
Tarski ?[modifier le code]
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)