Récursif (langage)

Prenez un mot formé de 0 et de 1, puis demandez s'il contient un nombre pair de 1. Un programme peut lire les symboles un à un, retenir seulement si le compte est pair ou impair, puis répondre après le dernier symbole.

Ce langage est récursif, ou décidable, parce que la procédure donne toujours l'une des deux réponses attendues : le mot appartient au langage, ou il n'y appartient pas. L'essentiel n'est pas la rapidité, mais la garantie que le calcul finit pour chaque mot.

Un langage formel est un ensemble de mots construits sur un alphabet. Un langage L est récursif, synonyme de décidable, lorsqu'il existe une machine de Turing M qui termine son calcul pour tout mot w et donne le verdict correct. Le critère complet s'écrit :

La condition d'arrêt vaut donc aussi bien pour les mots de L que pour ceux qui n'en font pas partie. Elle distingue la décision d'une procédure qui reconnaît seulement les réponses positives et pourrait continuer indéfiniment dans les autres cas. Les langages réguliers et les langages hors-contexte sont récursifs. La classe est également fermée par complémentaire : si L est récursif, l'ensemble des mots du même alphabet qui ne sont pas dans L l'est aussi, car il suffit d'échanger les verdicts d'une machine qui s'arrête toujours. Cette propriété relève de la calculabilité ; elle ne fixe aucun temps d'exécution maximal commun à tous les décideurs.

Considérons le langage L_pair des mots écrits avec 0 et 1 qui contiennent un nombre pair de 1. Le mot testé est 10110. La procédure conserve un état « pair » ou « impair » ; elle change d'état à chaque 1 et le conserve à chaque 0.

Le langage de l'exemple peut être noté : $L_{\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}=\{w\in \{0,1{\}}^{\ast }\mid \mathrm{\mid }w{\mathrm{\mid }}_1\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)\}L\_\{\backslash mathrm\{pair\}\}=\backslash \{w\backslash in\backslash \{0,1\backslash \}^\{*\}\backslash mid\; |w|\_\{1\}\backslash equiv\; 0\backslash pmod\; 2\backslash \}$. Ici, la quantité |w|₁ désigne le nombre de 1 dans le mot w.

1. Avant la lecture, le compte est pair.
2. Après 1, puis 0, les états sont impair, puis impair.
3. Les deux symboles suivants, 1 puis 1, donnent pair, puis impair.
4. Le dernier 0 conserve l'état impair.

Le mot 10110 contient exactement trois 1 : il est rejeté. Le contrôle consiste à recompter directement ces trois occurrences. La procédure lit cinq symboles, atteint la fin du mot et s'arrête ; le même point d'arrêt existe pour tout mot binaire fini.

Un diagramme d'états rend ce contrôle visible : chaque colonne associe le symbole lu à la parité obtenue, jusqu'au verdict impair.

Pour tester l'appartenance d'un mot, on cherche un algorithme qui traite aussi les réponses négatives et dont l'arrêt est garanti. Pour L_pair, le suivi de la parité suffit ; recompter toutes les possibilités serait inutile.

Pour établir qu'un langage est récursif, il faut décrire un décideur et justifier deux points séparément : son verdict est correct et il s'arrête sur chaque entrée. Une procédure qui trouve certains mots acceptés sans régler le cas des autres ne suffit pas.

Pour décider le complémentaire d'un langage récursif, on réutilise le même calcul et on inverse acceptation et rejet. Cette solution convient précisément parce que le décideur initial termine dans les deux cas.

Un langage récursivement énumérable dispose d'un procédé qui reconnaît ses mots, mais ce procédé peut ne jamais s'arrêter sur un mot extérieur. Pour L_pair, le test de parité termine aussi sur 10110, qui est rejeté : le langage est bien récursif.

Un problème semi-décidable garantit un constat fini pour les cas positifs, sans garantir un verdict négatif fini. Un problème décidable exige au contraire que chaque instance reçoive l'une des deux réponses en temps fini.

L'existence d'un algorithme qui accepte tous les mots du langage ne suffit pas. Si son comportement n'est pas établi pour les mots extérieurs, le symptôme est une exécution susceptible de durer indéfiniment ; il faut prouver l'arrêt sur les deux types d'entrée.

« En temps fini » ne signifie ni « rapidement » ni « avec une même limite pour toutes les tailles d'entrée ». Le temps peut croître fortement avec la longueur du mot ; le bon contrôle porte d'abord sur la terminaison de chaque calcul.

Le complémentaire doit être pris parmi tous les mots du même alphabet. Changer l'alphabet modifierait l'univers de référence et donc le langage obtenu ; il faut fixer cet alphabet avant d'inverser acceptation et rejet.

machine de Turing — Préciser le modèle abstrait qui exécute un décideur et formalise la condition d'arrêt.

Récursivement énumérable (langage) — Situer les langages reconnaissables pour lesquels l'arrêt sur une réponse négative n'est pas garanti.

Semi-décidable (problème) — Approfondir la différence entre reconnaître les cas positifs et décider toutes les instances.