Mikael de la Salle : "Compression et indécidabilité, d'après Marks"

mardi 17 mars 2026, 09:45 → 11:30 Europe/Paris

Résumé: Cet exposé est la suite logique de l'exposé précédent, mais sera essentiellement indépendant. Je rappellerai l'énoncé du lemme de compression de Marks, qui est un critère d'indécidabilité d'un problème de décision, et dont j'avais expliqué la dernière fois qu'il était un des ingrédients clés dans la solution du problème de plongement de Connes. Je donnerai ensuite sa preuve. Si le temps le permet et si j'arrive à trouver l'argument, j'expliquerai peut-être comment ce lemme permet également de prouver de façon nouvelle le fait classique que le problème du domino est indécidable https://en.wikipedia.org/wiki/Wang_tile