Stephen Cole Kleene 1909-1994

Stephen Cole Kleene

(1909-1994)

Kleene

 


Auteur:  Frédéric Jaëck ; Cette note accompagne un article principal de Ghazal Kachigar sur le fameux théorème de récursion de Kleene.


 

Stephen Cole Kleene est un mathématicien et logicien américain, né le 5 janvier 1909 à Hartford (Connecticut) et mort le 25 janvier 1994 à Madison (Wisconsin).

Kleene est connu pour avoir fondé la branche de la logique mathématique qui porte le nom de théorie de la récursion, en collaboration avec notamment Alonzo Church, Kurt Gödel, Emil Post et Alan Turing, et aussi le lambda-calcul avec Alonzo Church et John Barkley Rosser. Il est également connu pour avoir inventé le concept d’expression régulière et de langage régulier.

En créant les outils pour formaliser le concept de calculabilité, permettant ainsi de déterminer quels problèmes sont résolubles par des algorithmes, et d’autre part en élaborant les concepts permettant d’analyser les langages de programmation et de décrire les automates les plus simples, il a participé à établir les bases théoriques de l'informatique. L’étoile de Kleene, le théorème de Kleene le théorème de récursion de Kleene et le théorème du point fixe de Kleene rappellent le rôle qu’il a joué dans l'établissement de concepts importants.

Le site Mathematics Genealogy Project recense 13 docteurs qu’il a formé et pas moins de 1020 descendants !

 

Le concept d’étoile de Kleene permet d’apprécier une partie de son travail.

 

En théorie des langages, l’étoile de Kleene, parfois appelée fermeture de Kleene ou encore fermeture itérative, est un opérateur unaire utilisé pour décrire les langages formels. Le nom vient de la notation employée, un astérisque.

L’étoile de Kleene est l'un des trois opérateurs de base utilisés pour définir une expression régulière, avec la concaténation et l'union ensembliste.

Appliquée à un ensemble $X$, elle a pour résultat le langage $X^{*}$, défini ainsi :

Si $X$ est un alphabet, c'est-à-dire un ensemble de symboles ou caractères, alors $X^{*}$ est l'ensemble des mots sur $X$, mot vide $\varepsilon$ inclus.

Si $X$ est un langage, alors $X^{*}$ est le plus petit langage qui le contienne, qui contienne $\varepsilon$ et qui soit stable par concaténation.

 

Exemples :

 

Pour l'alphabet $\{a,b,c\}$, on a

$\{a,b,c\}^{*}=\{\varepsilon ,a , b , c , aa , ab , ac , ba , bb , bc , ca , cb , cc , aaa ,\ldots \}$

 

Pour la partie $X=\{aa,b\}$ composée des deux mots $aa$ et $b$ sur l'alphabet $\{a,b\}$, on obtient

 

$\{aa,b\}^{*}=\{\varepsilon , b , aa , bb , aab , baa , bbb , aaaa , aabb , baab , bbaa , bbbb , \ldots \}$

 

On peut préciser la définition de la façon suivante.

 

D’abord il faut se souvenir de la notion de magma associatif (pas forcément unifère).

 

Formellement, $(E, *)$ est un magma associatif lorsque, pour tous éléments $x$, $y$ et $z$ de $E$ :

 

$x*y\in E$ (loi interne) ;

$ x*(y*z)=(x*y)*z$ (associativité) ;

 

Il est unifère si de plus on a un neutre $e$ :

${\displaystyle x*e=e*x=x}$ (e est neutre).

On parle alors de monoïde = magma associatif unifère

 

Par exemple $(\mathbb N,+)$ est un magma associatif, commutatif et unifère.

 

On appelle alors étoile de Kleene d’une partie $X$ d’un monoïde $M$ le sous-monoïde engendré par $X$. Ce sous-monoïde est noté $X^*$.

Comme d’usage pour les opérations de fermeture, il peut être défini de trois manières équivalentes :

 

 

Si $X$ est un ensemble générateur du monoïde $M$ , on a en particulier $ X^{*}=M$.

 

On pourrait penser que ces idées sont jolies mais inutilisées en mathématiques. En fait elles font partie des bases conceptuelles avec lesquelles les mathématiciens abordent les problèmes.