Problèmes de décision sur les demi-groupes

Abstract

En théorie de la calculabilité, un problème de décision est une question mathématique dont la réponse est soit "oui", soit "non". Formuler un problème de décision c’est se poser une question de décidabilité, il s’agit de rechercher l’existence d’un algorithme résolvant le problème et, s’il existe, de l’expliciter. Dans ce travail, nous passons en revue plusieurs problèmes de décision sur des semi-groupes et discutons de leur décidabilité. Nous étudions en particulier le problème de décision qui traite du caractère libre des semi-groupes, ainsi que le problème de correspondance de Post, dont nous démontrons l'indécidabilité. Enfin, nous caractérisons certains problèmes appliqués au cas particulier des matrices carrées.