Discussion:Problème de correspondance de Post
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
 Tâches à accomplir pour Problème de correspondance de Post
|
aide | |
| ||
Tout ou partie de cet article est issu de la traduction de l'article sous licence CC-BY-SA « (en) Post correspondence problem » dans sa version du 11 décembre 2012.
Consultez l'historique de la page originale pour connaître la liste de ses auteurs.
Avec deux morphismes[modifier le code]
On trouve ( par exemple Berstel transduction and context free languages )
la formulation suivante:
A alphabet fini , A* monoide libre engendré par A, l’ensemble des mots muni de la concaténation d’élément neutre le mot vide.
B alphabet fini , B* monoide libre …..
f:A*->B* morphisme de monoide
g: A*->B* morphisme de monoide
question : existe t’il un mot non vide u de A*
tel que f(u)=g(u).
comme A* est libre, il suffit de définir f
et g sur les lettres de A. Et on est donc sur une instance de PCP. Et après un moment de réflexion, on voit qu’elles sont toutes comme cela.
personnellement je comprends mieux la formulation algébrique avec morphismes de monoide. Je sais, c’est idiot c’est la même chose. Le morphisme de monoide y a que ça de vrai.
je ne me sens pas, pour l’instant, de le mettre en forme
Latex ( Delbex) ou Anne Beauval.
( Il m’est arrivé d’être reverté par Anne, après avoir voulu homogénéiser des fi et Var phi sur quelques pages autour de la suite de Fibonacci ou du nombre d’or. Puis j’ai trouvé quelques pages de discussions sur ce thème, et j’ai compris que c’était un peu tendu.)
Je serais curieux de voir comment Martin Davis, qui vient de nous quitter ce premier janvier, racontait le Post Correspondance Problem.
2A01:CB11:8060:80BF:1822:1EB5:E907:50D3 (discuter) 6 janvier 2023 à 16:33 (CET)
Variantes en fixant le nombre de types de blocs utilisables[modifier le code]
La description a été modifiée de :
Si on fixe N, le nombre de types de blocs utilisables, le problème devient décidable pour N ≤ 2, et reste indécidable pour N ≥ 7. Le statut du problème est inconnu pour 3 ≤ N ≤ 6.
à
Si on fixe N, le nombre de types de blocs utilisables, le problème devient décidable pour N ≤ 2, et reste indécidable pour N ≥ 5. Le statut du problème est inconnu pour 3 ≤ N ≤ 4.
en reprenant les références indiquées sur : https://en.wikipedia.org/wiki/Post_correspondence_problem Freisnard (discuter) 11 février 2024 à 16:05 (CET)