Thèse de Church-Turing et langages formels

1. La Thèse de Church-Turing : L'horizon du calculable

Jusqu'à présent, nous avons utilisé les machines de Turing comme un modèle de calcul parmi d'autres. Mais est-ce le modèle ultime ? Que se passerait-il si nous ajoutions plusieurs rubans, plusieurs têtes de lecture, ou si nous imaginions un tout autre type de machine ? Serions-nous capables de calculer plus de choses ?

Au cours des années 1930, indépendamment l'un de l'autre, le logicien américain Alonzo Church et le mathématicien britannique Alan Turing ont cherché à formaliser la notion intuitive d'« algorithme » ou de « procédure de calcul effective ». Church a développé le lambda-calcul, tandis que Turing a inventé ses machines. Remarquablement, ces deux modèles, ainsi que tous les autres modèles de calcul "raisonnables" proposés depuis, se sont avérés équivalents en puissance.

Cette convergence a donné naissance à la thèse de Church-Turing.

Pour une définition formelle et une discussion sur la portée de cette thèse, je vous invite à lire la section dédiée dans le cours de K. Perrot.

Pour résumer et consolider les points essentiels :

• Ce n'est pas un théorème : La thèse ne peut être prouvée mathématiquement car elle relie un concept intuitif (un "algorithme") à un objet formel (une machine de Turing). Elle est acceptée en raison de l'accumulation de preuves circonstancielles.
• L'argument de la robustesse : La principale preuve en sa faveur est que de nombreuses tentatives pour créer des modèles de calcul plus puissants ont toutes abouti à des modèles équivalents à la machine de Turing. Ajouter des rubans, des têtes, ou autoriser le non-déterminisme ne change pas l'ensemble des problèmes qu'une MT peut résoudre (même si cela peut changer l'efficacité).
• Implication fondamentale : La thèse nous autorise à dire : "un problème est calculable si et seulement si il peut être résolu par une machine de Turing". Cela nous donne un outil formel et stable pour raisonner sur les limites absolues de l'informatique.

La vidéo suivante illustre bien cet argument de robustesse en montrant que diverses variantes de machines de Turing ont en fait la même puissance de calcul.

2. Décidable vs. Reconnaissable : La hiérarchie des problèmes

Maintenant que nous acceptons la machine de Turing comme le mètre étalon de la calculabilité, nous pouvons classer les langages (et donc les problèmes) en fonction du comportement de la machine qui tente de les résoudre. La distinction la plus importante concerne l'arrêt de la machine.

Définitions formelles

Un problème de décision peut être vu comme la question de savoir si un mot w appartient à un langage L. Il y a deux niveaux principaux de "résolution" pour ce type de problème.

Explicitons ces définitions :

1. Langages Récursifs (ou Décidables)

Un langage $L$ est dit récursif (ou décidable) s'il existe une machine de Turing $M$ qui s'arrête sur toutes les entrées et qui décide le langage. C'est-à-dire :

• Si $w\in L$, alors $M$ s'arrête dans un état d'acceptation.
• Si $w\notin L$, alors $M$ s'arrête dans un état de rejet.

Une telle machine $M$ est appelée un décideur. Elle implémente un algorithme au sens plein du terme : une procédure qui termine toujours et fournit une réponse claire "oui" ou "non". La machine que nous avons construite pour $\{a^n{b}^n{c}^n\}$ est un décideur.

2. Langages Récursivement Énumérables (ou Reconnaissables)

Un langage $L$ est dit récursivement énumérable (r.e.) s'il existe une machine de Turing $M$ qui le reconnaît. C'est-à-dire :

• Si $w\in L$, alors $M$ s'arrête dans un état d'acceptation.
• Si $w\notin L$, alors $M$ soit s'arrête dans un état de rejet, soit ne s'arrête jamais (boucle infinie).

Une telle machine $M$ est un reconnaisseur. Elle implémente un semi-algorithme : elle peut confirmer l'appartenance ("oui"), mais si un mot n'appartient pas au langage, il est possible qu'on attende la réponse indéfiniment.

La vidéo suivante explique cette distinction de manière très claire, en insistant sur la condition de terminaison.

Origine des termes

• Récursif : Ce terme vient de la théorie des fonctions récursives (un des modèles équivalents aux MT). Un langage $L$ est récursif si sa fonction caractéristique $f_L$ (qui vaut 1 si $w\in L$ et 0 sinon) est une fonction calculable (ou "récursive").
• Récursivement Énumérable : Un langage $L$ est r.e. si et seulement si il existe une machine de Turing (un "énumérateur") qui peut lister tous les mots de $L$, un par un. Si le langage est infini, cette énumération ne se termine jamais, mais tout mot du langage finira par apparaître dans la liste. C'est une propriété équivalente très importante.

Il est évident que tout langage récursif est également récursivement énumérable. Si une machine s'arrête toujours, elle satisfait trivialement la condition pour être un reconnaisseur. La question la plus profonde, et qui sera l'objet de notre prochaine leçon, est : existe-t-il des langages qui sont récursivement énumérables mais non récursifs ?

Conclusion

Cette leçon nous a fait franchir un pas conceptuel majeur. Nous sommes passés de la construction de machines spécifiques à la classification générale de tous les problèmes de calcul.

Points clés à retenir :

• La thèse de Church-Turing postule que toute fonction calculable par un algorithme est calculable par une machine de Turing. C'est le fondement de la théorie de la calculabilité.
• Un langage est récursif (décidable) s'il existe une MT qui s'arrête sur toutes les entrées et donne une réponse "oui" ou "non". C'est un algorithme complet.
• Un langage est récursivement énumérable (reconnaissable) s'il existe une MT qui s'arrête et répond "oui" pour les mots du langage, mais qui peut boucler indéfiniment pour les autres. C'est un semi-algorithme.
• La classe des langages récursifs est incluse dans celle des langages récursivement énumérables.

La prochaine étape logique est de prouver que cette inclusion est stricte. Nous allons le faire en étudiant le problème le plus célèbre de l'informatique théorique : le problème de l'arrêt (Halting Problem). Nous définirons ce problème et démontrerons formellement son indécidabilité, vous donnant ainsi votre premier exemple concret d'un problème que nul ordinateur ne pourra jamais résoudre de manière générale.