Le cours de calculabilité que je suis explique plusieurs langages qui sont dans RE - REC (récursivement énumérable mais non récursif, c'est-à-dire soluble par une machine de turing non haletante). Il montre d'abord comment l'un d'entre eux (L_d, langage des machines de turing qui n'acceptent pas leur propre encodage) n'est pas dans RE, et prouve que son complément est dans RE - REC. Il prouve ensuite qu'il est réductible au langage universel (L_u, l'ensemble de tous les encodages binaires des machines de turing concaténés avec une chaîne de caractères qu'elle accepte). Il montre ensuite que L_u est RE-dur, puis le réduit à L_PCP (Post's Correspondence Problem) et le réduit ensuite à Context Free Grammar Ambiguity. Existe-t-il des problèmes qui sont dans RE, mais pas RE-durs ? Parce que jusqu'à présent, pour chaque problème que notre professeur a expliqué dans RE - REC, il a prouvé qu'ils sont réductibles l'un à l'autre.
Réponses
Trop de publicités?
La réponse à votre question est oui, car même les langages finis sont RE. Mais ils ne sont en aucun cas difficiles dans le sens où vous l'entendez.
Peut-être que votre question est en réalité "Existe-t-il des problèmes récursivement énumérables qui ne sont pas difficiles à résoudre mais qui ne sont pas récursifs ?". Ici, la réponse dépend de votre notion de réduction. Probablement que votre professeur utilise des réductions many-one ; alors la réponse est probablement OUI (je ne suis pas complètement sûr). Pour les réductions plus faibles, la réponse est NON.
Le problème que vous mentionnez (avec la précision de Peter Leupold, qui devrait être intégrée dans la question) est connu sous le nom de problème de poste. La réponse est positive : en particulier, tous les ensembles dits "simples" sont des ensembles RE qui ne sont pas many-one complets.
Un ensemble simple est un ensemble RE dont la complémentaire est "immune". Un ensemble immun est un ensemble qui ne contient aucun RE-set infini. Cela suffit à prouver qu'un ensemble simple ne peut pas être complet, puisque le complémentaire d'un ensemble complet est productif, et que tout ensemble productif contient un sous-ensemble RE infini, généré par sa propre fonction de production.
Quelques ensembles simples sont connus. Mon exemple préféré est l'ensemble des nombres non aléatoires, selon la complexité de Kolmogorov, c'est-à-dire l'ensemble de tous les nombres qui peuvent être exprimés de manière plus compacte comme l'indice d'un programme les générant (sur l'entrée 0). La preuve qu'un tel ensemble est simple n'est pas difficile et peut être trouvée dans tout bon texte sur la calculabilité.
