prélogique

La recherche de la question première, celle qui se pose avant toutes les autres, la cause des causes, qui étendue à tous les domaines constitue de fait un élément clef des croyances religieuses, et qui par le biais du pouvoir unificateur des sciences dures donna un avantage aux religions monothéistes, se pose également pour la science exacte elle-même qu'est la mathématique.

Dans notre approche pragmatique et social on passe de suite de l'objet au verbe. On définit les mathématiques par la question "C'est quoi, faire des mathématiques ?" C'est raisonner. L'acte du mathématicien est de faire des démonstrations, des raisonnements logiques, dans une logique, dans sa logique. Et c'est aussi le rêve..., des analogies naissantes, des alignements incomplets, des métamorphoses arbitraires, comme autant d'intuitions éphémères, telles le contrependant de l'exactitude intemporelle. Un réseaux de neurones, une intelligence artificielle, peut très bien faire les deux. Demain, les découvreurs de théories mathématiques seront des machines.

La question première en mathématique se résume donc pour nous à cette unique question : « Qu'est-ce que le raisonnement logique ? ». Mais pour bien comprendre ce que recouvre le raisonnement logique, et en connaitre les délimitations qui sont toujours fuyantes si on aborde la question de l'intérieur, il faut poser en faite, une question plus générale sur ce qu'est le raisonnement formel, et qui nous ramène à la notion primordiale de calculabilité et au concept de machine. En effet, il y a une multitude de logiques, et le mécanisme général qui les fait fonctionner s'appelle la calculabilité.

Mais comme un calcul peut de jamais s'arréter et ainsi ne jamais donner de réponse, lorsque de tels cas peuvent se produire on parlera plutôt de semi-calculabilité, gardant le terme de calculabilité pour décrire tout calcul assurer de s'arréter en un temps fini et ainsi de donner toujours une réponse. Autrefois on disait d'un tel calcul qu'il était totalement calculable.

Le raisonnement formel..., c'est un langage formel et un système de démonstration formel. Et il n'est pas nécessaire de donner un sens aux formules, de définir une sémantique pour raisonner formellement. Car ce n'est qu'un calcul sur la forme, qui s'effectue par un algorithme, et qui énumére toutes les déductions possibles.

Raisonner formellement devient l'acte d'une machine. Le concept de raisonnement formel dans sa plus grande généralité coïncide avec celui de machine, et avec la faculté d'être énumérable par une machine.

La machine la plus générale représentée par la machine de Turing avec son ruban indéfini représentant un potentiel de mémoire non limité, définit justement ce qui est énumérable. Pour une machine de Turing, l'énumérabilité et synonyme de semi-calculabilité.

Un premier travail consiste à unifier certains concepts sous l'éclairage des travaux de Chomsky, de Church, de Turing et de Gödel, sur la hiérarchie des langages, sur la semi-calculabilité, sur la complétude du calcul des prédicats, et sur l'incomplétude des théories énumérables.

2) Le cadre linguistique

On se place dans un langage d'alphabet fini `A`. Par exemple, considérons l'alphabet `A = {a,b,c}`. Le langage d'alphabet `A` se note `A^"+"` . C'est l'ensemble des mots qu'il est possibles d'écrire dans cet alphabet, où un mot est une succession finie quelconque de caractères de l'alphabet :

On utilise l'opérateur de Kleene en exposant `""^"+"` qui, appliqué à un ensemble, retourne l'ensemble des suites finies non-vides d'éléments de cet ensemble, avec cette simplification que chaque élément de l'ensemble est identifié à la suite-singleton le contenant. Ainsi, nous avons :

On choisit comme cadre ce langage mère `A^"+"` qui va servire de carrière. Les langages définis dans ce cadre sont inclus dans ce langage mère `A^"+"`. Un langage est donc un sous-ensemble de `A^"+"`.

3) Le langage formel

Il découle de ces 3 contraintes que l'alphabet est énumérable. En effet, le langage étant énuméré par une machine, et les mots étant de taille finie, l'alphabet restreint aux seuls caractères utilisés dans les mots du langage constitue un nouvel alphabet énumérable par une machine qu'il est facile de concevoir.

On peut délors identifier cet alphabet restreint à l'ensemble des entiers naturels `NN`. On remarque alors la possibilité de remplacer chaque tel caractère par une succession fini de chiffres binaires délimitée par un caractère supplémentaire "`#`", ramenant ainsi l'alphabet `NN` à l'alphabet `{#,0,1}`. Autrement dit, il n'y a nulle restriction à ne concevoir que des alphabets finis. Et donc par principe simplificationnel, l'alphabet est choisi fini.

C'est pourquoi on entendra dans ce présent document par "langage formel", un langage énumérable d'alphabet fini.

4) La calculabilité

La calculabilité est un concept central qui traite de tout ce qui peut être calculé ou résolu par un algorithme ou une machine. Elle inclut donc toutes les démonstrations que peut faire le mathématicien. Et en ce sens, elle peut prétendre être à la racine des mathématiques.

Néanmoins, elle est liée à une propriété physique, sur la conception physique d'une machine qui, dans sa plus grande généralité physique, est considérée comme un système physique fini.

Alan Turing propose une machine idéale pour définir ce qui est semi-calculable, et qui portera son nom. Il démontre en 1936 l'indécidabilité du problème de l'arrêt, c'est à dire qu'il n'existe aucune machine de Turing capable de décider en un temps fini si une machine de Turing appliqué à un mot, va s'arréter ou pas. Et il propose de définir la calculabilité comme étant ce qui est calculable par une machine de Turing, et d'une façon plus générale de définir la semi-calculabilité comme étant ce qui est semi-calculable par une machine de Turing.

La thèse de Church promue 7 ans plus-tard peut être considérée comme étendant la notion de calculabilité à la physique, en la définissant comme une propriété physique : Tout ce que peut produire un système physique fini est calculable par une machine de Turing. Cependant comme cela est une propriété physique et non une propriété mathématique, la thèse ne peut pas faire l'objet d'une démonstration mathématique.

L'apport de la mécanique quantique n'à pas modifié le consensus sur la question. Richard Jozsa montre même que, d'un certain point de vue, les machines de Turing quantiques sont moins complètes que les machines de Turing classiques.

20 ans plus-tard, Chomsky découvre la hiérarchie des langages formels avec leur grammaire formelles, chaque grammaire constituant un programme énumérant les mots d'un langage. La démonstration est faite en 1959 que tout langage énuméré par une machine de Turing, est définissable par une grammaire formelle de type 0. Notez que l'énumérabilité est plus simple à aborder que la semi-calculabilité bien que ces deux concepts coïncide pour une machine de Turing.

La forme trés rudimentaire des règles de réécriture utilisant un alphabet augmenté de caractères non-terminaux ne présageait pas cette capacité de pouvoir définir tous les languages énumérables, c'est la découverte fondamentale des grammaires de type 0 faite par Noam Chomsky. Ces découvertes établies au cours du 20ième siècle sont d'une importance considérable comme il y en a une tous les milles ans, et Noam Chomsky est sans doute le seul savant encore vivant pouvant s'enorgueillir d'avoir participé à une telle avancée pour l'humanité. Notez qu'en intégrant ces découvertes sur la calculabilité, le "formalisme" mathématique est en mesure de réunifier tous les courants de pensées mathématiques.

Kurt Gödel démontre en 1929 la complétude du calcul des prédicats du permier ordre : « Quelque soit une formule `P`, si tous les modèles satisfont `P` alors il existe une démonstration de `P` ». Et il démontre en 1931 l'incomplétude des théories énumérables : « Quelque soit une théorie `T` cohérente énumérable capable de formaliser l'arithmétique, il existe toujours des formules que `T` ne peut pas décider. Et en particulier, la cohérence de `T` n'est pas démontrable dans `T` ».

Aux vues des travaux de Gödel qui étaient antérieurs, il est possibile de définir mathématiquement le domaine calculable d'une façon relativement simple et qui produit une version suffisament abstraite de la thèse de Church pour qu'elle soit démontrable. Une machine aura cette puissance de calcul, dite Turing-complet, si elle est capable d'énumérer l'ensemble des tautologies de l'arithmétique.

Dans des époques futurs, il n'est pas impossible que la thèse de Church soit contredite et que l'on découvre des procédés physiques, tels des oracles, capables de produire des données incalculables par une machine de Turing. Ces procédés physiques seront alors à introduire dans la machine de Turing pour la perfectionner et en faire une nouvelle machine idéale agrandissant le domaine de calculabilité au delà de la capacité calculatoire de l'arithmétique.

5) La machine de Turing

La machine de Turing est un machine idéale suceptible de calculer tout ce qui est calculable, et ainsi d'énumérer tout ensemble qui est énumérable, inventé par le mathématicien britannique Alan Turing en 1936. Et c'est cette machine qui définit le concept de calculabilité et de semi-calculabilité à notre époque.

On pose un alphabet et on considère un caractère supplémentaire qui est le caractère blanc. La machine de Turing comprend un ruban indéfini qui est une succession de cases numérotées par un entier relatif servant d'index et une tête de lecture-écriture intialement positionnée sur la case numéro zéro du ruban. Chaque case contient un caractère. Initialement le ruban contient la données initiale qui doit être de taille finie, et le reste du ruban doit contenir des caractères blancs. Notez que le ruban de longueur infini donne à la machine de Turing un potentiel de mémoire non-limité.

La machine possède un nombre fini d'états numérotés. L'état initial est l'état numéro `1`. À chaque étape de calcul, la machine effectue une action qui dépend de l'état en cours et du caractère qu'elle lit sur le ruban. L'action de la machine consiste à écrire un caractère sur le ruban en remplaçant celui qui s'y trouve, puis à se déplacer d'une case sur le ruban en augmentant ou en diminuant de `1` l'indexe, puis à passer à un nouvel état.

Il existe `2` états supplémentaires dits d'arrêt. L'état d'acceptation indique que la machine a trouvé une solution et c'est arrêtée. L'état de rejet indique que la machine n'a pas trouvé de solution correcte et que le calcul s'est terminé sans succès.

On note l'alphabet `A`, l'alphabet augmenté du caractère blanc `A"+"1`, le nombre d'états `N`, et on note l'ensemble des états par la même lettre `N"="{1,2,3,...,N}`. Il y a deux états d'arrêt supplémentaires, l'état d'acceptation et l'état de rejet. L'état d'acceptation est l'état numéro `N"+"1`. L'état de rejet est l'état numéro `N"+"2`. On note l'ensemble des états augmenté de ces deux états d'arrêt `N"+"2={1,2,3,...,N,N"+"1,N"+"2}`. Il y deux mouvements possibles de la tête de lecture-écriture à droite ou à gauche, on note l'ensemble contenant ces deux mouvements par le chiffre `2`. La machine de Turing, que l'on identifie à son programme, est une application dite de transition appartenant à :

Dans une telle application de transition servant de programme pour la machine de Turing, généralement seul une petite partie de son graphe va déterminer le comportement de la machine de Turing. C'est par soucis simplificationel de la structure que l'on rend carrée en quelque sorte, que l'on intègre dans le programme toute une partie non-utilisée, pouvant de fait transporter un héritage informationnel issu de sa génèse.

On note `ccM` l'ensemble des machines de turing. On note `Omega` l'ensemble des données qu'il est possible d'écrire sur le ruban. La machine de Turing `M` prend en entrée un élément `x "∈" Omega`, et lance son calcul :

Comme il y a une troisième possibilité qui correspond au calcul sans fin, il apparait deux notions de calculabilité, une première anciennement dite totale dans laquelle le calcul se termine toujours en un temps fini, et une notion de calculabilité plus faible dans laquelle le calcul peut ne jamais s'arrèter, dite de semi-calculabilité.

6) Abstraction

La mathématique aime discourir d'objet qui peuvent n'avoir aucun lien avec la réalité. Mais la façon dont on les évoquera constituera un lien.

En mathématique, une fonction `f` possède un ensemble de départ `f_sf"S"` et un ensemble d'arrivé `f_sf"L"`. Et au sein de son ensemble de départ, la fonction `f` possède un domaine de définition `f_sf"D"` qui en est une partie.

Pour définir les critères de calculabilités d'une fonction `f`, on doit d'abord choisir une représentation sur le ruban de la machine de Turing des éléments appartenant à `f_sf"D" uu f_sf"L"`. Il convient de prouver l'existence d'une application injective de `f_sf"D"uu f_sf"L"` vers `Omega` et d'en choisir une. Mais attention !, la notion de calculabilité sera alors relative à ce choix, ou autrement dit, en posant cette application injective comme étendant notre domaine de calculabilité.

On peut alors définir les critère de calculabilité et de semi-calculabilité de `f` :

Une fonction `f` est calculable si et seulement s'il existe une machine de Turing qui appliqué à chaque élément `x` de l'ensemble de départ de la fonction, s'arrète sur l'état acceptant en un temps fini et donne la valeur de `f(x)` comme réponse sur le ruban si `x` fait bien partie du domaine de définition de `f`, et sinon s'arrète en un temps fini sur l'état de rejet.

Une fonction `f` est semi-calculable si et seulement s'il existe une machine de Turing qui appliquée à chaque élément `x` de l'ensemble de départ de la fonction, s'arrète sur l'état acceptant en un temps fini et donne la valeur de `f(x)` comme réponse sur le ruban si `x` fait bien partie du domaine de définition de `f`, et sinon soit s'arrète en un temps fini sur l'état de rejet ou soit ne s'arrête jamais de calculer.

Pour définir les critères d'énumérabilité d'un ensemble `E`, on doit d'abord proposer une représentation sur le ruban de la machine de Turing des éléments appartenant à `E`. Il suffit de prouver l'existence d'une application injective de `E` vers `Omega` et d'en choisir une. Mais attention !, la notion de calculabilité sera alors relative à ce choix :

Un ensemble `E` est énumérable si et seulement s'il existe une machine de Turing qui appliquée à chaque valeur `x` de `Omega` produit en un temps fini une valeur appartenant à `E`, et tel qu'elle définit ainsi une surjection de `Omega"↠"E`.

7) Restriction

Les données que nous voulons manipuler sont les mots de `A^"+"`. On plonge l'ensemble `A^"+"` dans `Omega` en codifiant les mots de manière stricte sur le ruban de la machine de Turing. Un mot doit commençer sur case n°0 et toutes les autres cases doivent contenir le caractère blanc. De telle sorte, qu'avec cette définition, nous avons :

La machine de Turing définie les fonctions semi-calculables de `Omega` vers `Omega`. Considérons une partie `X "⊂" Omega`. La restriction du domaine des données possibles à `X` se définit comme suit. On se restreint aux seuls données appartenant à `X`. Considérons une machine de Turing `M`. La machine de Turing restreinte à un domaine choisi `X "⊂" Omega` se note `M"|"_X`. Si elle est appliquée à un élément en dehors de `X`, elle retourne `sf"FALLAR"`. Et si la machine `M` retourne un élément en dehors de `X`, alors sa restriction `M"|"_X` retourne `sf"FALLAR"`. En revanche, si `x` est bien dans `X` et que `M(x)` procède à un calcul sans fin ou abouti à l'état d'echec, alors il en est de même pour sa restriction `M"|"_X (x)`.

Il est facile de programmer `M"|"_X` à partir de `M` à condition quand-même que `X` soit décidables, c'est à dire énumérable et de complément énumérable. Et cela peut s'écrire dans un langage de programmation adapté comme suit :

L'instruction `x"="M(m)` lance le calcul `M(m)` et trois comportements peuvent se produire :

Le calcul étant fini, on peut manipuler la méta-donné `sf"FALLAR"` comme une donnée, ce qui n'es pas le cas de l'infinit de Turing `oo`. Si le résultat d'un programme ce trouve être la méta-donné `sf"FALLAR"` cela devra être interprété comme un échec du calcul. Ce sont là les rudiments du langage de programmation turingien.

L'instruction `"condition" ⟶ "valeur"` met fin au programme en retournant la `"valeur"` si la `"condition"` est validée en un temps fini, mais si le calcul de la condition ne s'arrête jamais alors le calcul du programme ne s'arrête jamais.

Le littéral `y"∈" X` se calcul en un temps fini car `X` est énumérable, et le calcul du littéral `x"∉"X` se calcul en un temps fini car le complément de `X` qui est `Omega-X` est énumérable. D'où la nécessité que `X` soit décidable.

On peut ainsi choisir arbitrairement un univers des données dans lequel on se restreint volontairement. La seule contrainte est que l'univers doit être décidable. D'une manière générale, l'univers, qui est l'ensemble des valeurs possibles, se re-note `Omega`. Et l'ensemble des machines de Turing restreinte à `Omega` se re-note `ccM`.

8) La machine de Chomsky

Comme nous l'avons déjà signalé, l'énumérabilité est un concept plus simple à aborder pour les néophytes que la semi-calculabilité. C'est pourquoi on commence par décrite un second type de machine qu'est la machine énumérante de Chomsky. En effet, on peut présenter les grammaires de Chomsky sous la forme de machines énumérantes, d'où le concept de machine de Chomsky. C'est un machine virtuelle susceptible d'énumérer tout langage énumérable.

La machine de Chomsky est identifiée à son programme qui est une grammaire formelle écrite dans un alphabet `A` augmenté d'un second alphabet `B` de caractères dits non-terminaux. La grammaire comprend deux types d'instruction, les mots étendus et les règles de réécriture. Les mot étendus sont des mots d'alphabet `A"∪"B`. Les règles de réécriture sont des couples de mots étendus que l'on note à l'aide du symbole `→`.

La règle de réécriture s'applique à un mot étendu. Elle effectue une recherche d'occurrence de séquence dans ce mot étendu en prenant comme modèle le premier membre de la règle, et produit le mot étendu transformé en lui substituant une et une seule occurrence par le second membre de la règle. Exemple : Considérons l'alphabet `{a,b,c}`. Considérons un second alphabet de caractères non-terminaux `{S,R}`. Considérons la règle `aS"→"bcR` que nous appliquons au mot étendu `baScaS` cela produit les deux mots étendues `b bcR caS` et `baScbcR`.

On considère un alphabet `A` et un second alphabet `B` disjoint de caractères dits non-terminaux.

La grammaire forrmel est un ensemble d'instructions. La grammaire apparait comme deux ensembles finis, un ensemble de mots étendus et un ensemble de règles de réécriture. L'ensemble de mots étendus ne sera utilisé dans l'algorithme d'énumération qu'au cours d'une phase d'intitialisation. La grammaire formelle est traduite en un programme informatique comme suit. la traduction est globalement canonique dans le sens où elle n'introduit pas d'arbitraire non-local. Les mots étendus contenus dans la grammaire sont traités dans la phase d'initialisation. L'ordre arbitraire des règles de la grammaire va bien sûr induire un ordre arbitraire d'énumération du langage mais limité uniquement à chaque cycle.

On initialise 3 listes vides de mots étendus L, U, V.
On programme un aspet : à chaque fois que l'on ajoute un mot étendu dans la liste V on vérifit si le mot ne contient pas de caractères non-terminaux, si c'est le cas alors le mot est un mot du langage reconnu et on le produit.
On ajoute les mots étendus de la grammaire dans la liste V.
On répète indéfiniment le cycle suivant :
- On ajoute dans L les mots étendus qui sont dans U.
- On vide U.
- On met dans U les mots étendus qui sont dans V.
- On vide V.
- Pour chaque règle de réécriture de la grammaire, on l'applique à chaque mot étendus de la liste U, et les résultats, s'il ne sont pas déja dans L ni dans U ni dans V, sont ajoutés à la liste V.

La liste V accumule les nouveaux mots étendus produits lors du cycle en cours. La liste U contient tous les nouveaux mots étendus produits lors du cycle précédent. Et la liste L contient tous les nouveaux mots étendus produits lors des cycles précédant le cycle précédent. Chaque mot produit possède un niveau de complexité de calcul qui est le numéro de cycle dans lequel il est produit.

On ne s'intéresse qu'aux machine de Turing qui prennent en entrée un élément de `A^+` et qui retourne soit l'echec soit ne s'arrête jamais de calculer, ou soit aboutisse à un résultat appartenant à `A^+`. Soit bbbM l'ensemble des machine de Turing ayant cette propriété.

Pour pouvoir définir les fonctions semi-calculables de `A^"+"` vers `A^"+"`, Nous verrons qu'il suffit d'exhiber une bijection calculable entre `Omega` et `A^"+"`.

7) Exemples :

Considérons l'alphabet `A = {x,y,f,g,'(',',',')'}`, et le caractère non terminal `S`. Et considérons la grammaire suivante :

Cette grammaire énumère l'ensemble des termes engendrés par `{x,y,f("."), g(".,.")}` :

Deuxième exemple : Considérons l'alphabet `A = {a,b,c}` et des caractères non-terminaux `{S,P,Q}`. La grammaire qui énumère `Omega` peut s'écrire assez simplement :

6) Le concept d'énumérabilité

Comme nous l'avons déjà évoqué, l'énumérabilité est un concept plus simple à aborder pour les néophytes que la semi-calculabilité. C'est pourquoi on commence par décrite un second mode de fonctionnement de la machine de Turing qu'est la machine énumérante, et la première machine que nous allons concevoir énumérera `Omega`.Elle est fastidieuse à programmer mais on voit bien qu'il en existe une, que `Omega` est bien un ensemble énumérable décrit par le couple d'un entier relatif et d'une formule régulière suivante :

où l'entier relatif désigne le numéro de la case du ruban où se trouve le premier caractère appartenant à `A` de l'expression mémorisée sur le ruban.

où `A` signifie que l'on place à la suite un caractère quelconque de l'alphabet `A`,

où `_^"+"` signifie que l'on place à la suite un ou plusieurs caractères blancs,

et où `(...)"*"` signifie que l'on place à la suite un nombre quelconque ou nul d'expression `(...)`,

L'ordre total dans l'alphabet `A` engendre canoniquement un ordre total dit alphabétique dans le langage `A^"+"`. Et cet ordre permet d'énumérer les mots dans un ordre précis et donc de les numéroter. Le nombre `1` désignera la première lettre de l'alphabet. Par exemple :

La première machine énumérante que l'on conçoit est la machine qui énumère les éléments de `A^"+"` dans l'ordre alphabétique en commençant par `1`.

On conçoit un second type de machine dite énumérante, qui énumère les éléments d'un ensemble. Pour cela, on s'inspire de la conception des tubes sous UNIX. On conçois un flux de mots. La machine qui énumère `A^"+"` peut se programmer comme suit :

Où `1` désigne le mot constitué du premier caractère de l'alphabet. Où `sf"salida"` désigne la sortie standart qui sera raccordé à l'entrée d'un flux de mots. Où `x"≫" sf"salida"` signifie que l'on transmet le mot `x` sur la sortie standard. Où `sf"bucle"{...}` est une boucle sans fin, une répétition indéfinit du bloc de code `{...}`. Où `x"+"1` calcul le mot juste suivant `x`.

Ainsi chaque mot de `A^"+"` est désigné de façon biunivoque par un entier naturel non-nul, de telle sorte que l'on identifie chaque mot à son entier naturel non-nul, et donc :

La définition de l'énumérabilité est la suivante : Un ensemble non-vide de mots `E` est énumérable si et seulement s'il existe une machine de Turing `M` tel que `M(NN"*")"="E`. Cette notation ensembliste signifie que la machine de Turing `M` définit une surjection de `NN"*"` sur `E` noté `NN"*↠"E`. Littéralement cela signifie que pour tous les mots `m` de `NN"*"`, le calcul `M(m)` aboutit à un mot de `E`, et que pour tout mot `e` de `E`, il existe un mot `m` de `NN"*"` telle que `M(m)"="e`.

Une seconde définition de l'énumérabilité existe qui est la suivante : Un ensemble de mots `E` est énumérable si et seulement s'il existe un mot `e` et une machine de Turing `M` tel que `E"="{e,M(e), M^2(e),...}`

On simplifie cette définition en ajoutant dans `M` le choix de `e`. Cela peut se faire en fixant la valeur de `M(ø)` à `e` ce qui est toujours possible :

Il convient de démontrer que ces deux définitions sont équivalentes. Suppossons que `M(NN"*")"="E`. Considérons un mot `m` appartenant à `E`. On programme une machine `L` qui calcul le mot suivant dans `E` comme suit :

Et ainsi nous avons bien : `E = {e, L(e), L^2(e),...}`. Réciproquement supposons cette conclusion. On programme une machine `K` qui appliquée à un entier `n "∈" NN` produit `L^n(e)`, en prenant comme convention que `L^0(e)"="e`, comme suit :

Concidérons trois sous-ensembles de `Omega` notés `A,B,C`. Et considérons une fonction `f` de `A` vers `B`, et une fonction `g` de `B` vers `C`. La composition de fonction en notation française se note en juxtaposant les fonctions :

Si `f` et `g` sont semi-calculables alors `fg` est également semi-calculable. Réciproquement considérons une fonction semi-calculable `h` de `A` vers `C`, peut-elle se décomposer en la composition de deux fonctions semi-calculables ?

On ne s'intéresse qu'aux machine de Turing qui prennent en entrée un élément de `A^+` débutant à la case n° 0 et qui une foi lancé, soit, ne s'arrète jamais de calculer, ou s'arrête sur l'état de rejet, ou bien s'arrête sur l'état d'acceptation avec comme résultat sur le ruban un mot débutant à la case n° 0.

On précise la nature des données manipulées. On donne au caractère blanc le seul rôle de séparateurs de mots. Les données manipulées comprennent les mots d'alphabet `A`. Et elles comprennent également les successions finies de mots, car en effet, la présence du caractère blanc qui sert de délimitation entre deux mots, permet d'écrire une succession fini de mots. La séparation entre deux mots peut également se faire par une succession de plusieurs caractères blancs. On s'inspire ainsi du langage de programmation Bash, le shell UNIX, où les instructions et les arguments sont disposés sur une ligne de commande séparés par un ou plusieurs caractères blancs. C'est un choix qui n'est pas aussi arbitraire que l'on pourrait le penser et qui nous permet de définir, comme on a l'habitude de le faire, les mots et les n-uplet de mots d'alphabet `A` utilisés comme données.

On remarquera que le mot vide est exclus. Néanmoins il correspond à une disposition trés particulière du ruban, un ruban qui ne contient rien, et que l'on représente par le symbole `ø` qui sera utilisé comme méta-donnée. Ainsi `M(ø)` désigne le calcul de la machine de Turing `M` lancer à partir d'un ruban vide.

Cela nous amène à codifier cette nouvelle structure de données. On utilise l'opérateur de Kleene en exposant `""^"+"` qui, appliqué à un ensemble `A`, retourne l'ensemble des suites finies non-vides d'éléments de `A`, avec cette simplification que chaque élément de l'ensemble est identifié à la suite-singleton le contenant. Ainsi, nous avons :

L'alphabet `A` qui je le rapelle ne contient pas le caractère blanc, donne naissance au langage `A^"+"` composé des mots d'alphabet `A`. Et il donne naissance au langage `(A^"+")^"+"` composé des séquences finies non-vides de mots d'alphabet `A`.

On plonge notre structure de donnée dans `Omega`, en les codifiant de manière stricte sur le ruban de la machine de Turing en commençant par un mot sur la case n°0 et où les mots sont séparés d'un seul caractère blanc.

Puis par soucis de simplicité, on utilise un standard encore plus restrictif, en ne retenant que le premier mot des séquences. Le domaine des données d'entrée souhaité devient `A^"+"+ø`, et le domaine des données de sortie souhaité devient `A^+`.

On soushaite n'utiliser comme seuls données d'entrée possibles l'ensemble `A^"+"+ø`. Et on souhaite n'obtenir que des résultats appartenant à l'ensemble `A^"+"`. Pour cela, on procède à une restriction. On ne retient parmi l'ensemble des machines de Turing que celles qui ont ces deux propriétés. On obtient ainsi toutes les machines de Turing qui calcul les surjections de `A^"+" + ø` vers `A^"+"`. La propriété essentielle qui nous assure ne pas avoir réduit notre domaine de calculabilité, tient en cette remarque :

Puis, on définit une projection sur cette ensemble de machine de Turing comme suit : La machine de Turing `M` est dite restreinte au domaine choisie `Omega` et se note `M"|"_Omega`. Si elle est appliquée à un élément en dehors de `Omega"+"ø`, elle retourne `sf"FALLAR"`. Et si la machine de Turing d'origine `M` retourne un élément en dehors de `Omega`, alors sa restriction `M"|"_Omega` retourne `sf"FALLAR"`. En revanche, si `x` est bien dans `Omega"+"ø` et que `M(x)` procède à un calcul sans fin alors il en est de même pour sa restriction `M"|"_Omega(x)`.

Il est facile de programmer `M"|"_Omega` à partir de `M` à condition quand-même que `Omega"+"ø` et `Omega` soient tout deux décidables, c'est à dire énumérable et de complément énumérable. Et cela peut s'écrire dans un langage de programmation adapté comme suit :

On reprend la notation des blocs de code que l'on trouve dans le langage Ruby où par exemple le bloc `{x,y,z | ...}` est le programme d'une fonction prenant 3 arguments nommés en interne respectivement `x,y,z`. L'instruction `x"="M(m)` lance le calcul `M(m)` et retourne le résultant dans `x`, et si le calcul ne s'arrête jamais alors le calcul du programme ne s'arrête jamais. L'instruction `"condition" ⟶ "valeur"` met fin au programme en retournant la `"valeur"` si la `"condition"` est validée en un temps fini, et si le calcul de la condition ne s'arrête jamais alors le calcul du programme ne s'arrête jamais. d'où la nécessité d'avoir `Omega+ø` de complément énumérable, et `Omega` énumérable.

On peut ainsi choisir arbitrairement un univers des données dans lequel on se restreint. La seule contrainte est que l'univers doit être énumérable. L'univers, qui est l'ensemble des valeurs possibles, se note `Omega`. Et l'ensemble des machines de Turing restreinte à `Omega` se note `ccM`.

On ajoute une restriction supplémentaire, à savoir que appliqué au ruban vide, `ø`, la machine de Turing doit également produire un élément de `Omega`.

Puis, on utilise un autre standard qui est plus restrictif encore, en ne retenant que le premier mot des séquences. Le domaine des données produites par la machine devient alors simplement `A^"+"`. Dans la suite du document, les machines de Turing sont choisies obéissant à ce standard, et s'appliquent sur un mot de `Omega"="A^"+"` ou sur `ø` pour produire un mot de `Omega`.

7) Le concept d'énumérabilité

La première machine énumérante que l'on conçoit est la machine qui énumère les éléments de `A^"+"` dans l'ordre alphabétique en commençant par `1`.

Ainsi chaque mot de `A^"+"` est désigné de façon biunivoque par un entier naturel non-nul, de telle sorte que l'on identifie chaque mot à son entier naturel non-nul, et donc :

On simplifie cette définition en ajoutant dans `M` le choix de `e`. Cela peut se faire en fixant la valeur de `M(ø)` à `e` ce qui est toujours possible :

8) Les 3 modes d'une machine de Turing

On conçoit deux autres modes primordiaux pour la machine de Turing, la machine énumérante, et la machine sélective :

Un ensemble de mots est dit énumérable s'il existe une machine de Turing qui les énumère. Un ensemble de mots est dit semi-décidable s'il existe une machine de Turing qui les reconnait, c'est à dire telle que lorsqu'on lui soumet un mot, la machine répond "oui" si ce mot fait partie de l'ensemble, sinon elle répond "non" ou bien ne s'arrête jamais de calculer ce qui se note par l'infini de Turing `oo`. On passe d'une machine de Turing en mode énumératif à celle en mode selectif, passant ainsi de l'énumération à la reconnaissance, et vice-versa, par un complément algorithmique assez simple. C'est pourquoi tout ensemble énumérable de mots est un ensemble semi-décidable de mots et vice-versa.

La machine de Turing possède une mémoire qui peut s'agrandire sans limite, qui est son ruban sur lequel elle peut lire et écrire des caractères. Ce qui fait qu'elle peut mettre en oeuvre l'algorithme de minimalisation, c'est à dire dans le mode énumératif, lancer une succession sans fin de calculs qui pour chacun d'entre-eux peut être sans fin, pour finalement énumérer que les seuls résultats de ces calculs qui aboutissent.

En revanche la machine de Turing ne possède qu'un programme de taille finie, autrement dit, il n'y a qu'un nombre fini d'états. Et elle n'agit que sur un mot d'entrée de taille finie.

8) Définir un langage de programmation à partir de la notion de calculabilité

En étudiant les modes primordiaux de la machine de Turing déterministe, on dévoile des algorithmes permettant de passer d'un mode à l'autre. La codification de ces algorithmes se programme dans un langage adapté que nous développons.

On note l'application d'une machine `M` à un mot `m` par l'expression `M(m)`. On introduit le symbole `ø` pour désigner un ruban vide. Et `M(ø)` doit désigner un mot de `A^"+"`, On introduit, le symbole `sf"FALLAR"` de nom court `"⊥"` pour indiquer l'échec du calcul, le symbole `sf"ACEPTAR"` de nom court `"⊤"` pour indiquer que le calcul se termine en trouvant la solution, et le symbole `oo` pour indiquer que le calcul ne s'arrête jamais.

Pour indiquer que le mot est accepté on note `M(x)"=⊤"`. cela signifie que la machine `M` appliquée au mot `x` fini par s'arrèter sur l'état acceptant. Puis symétriquement, l'expression `M(x)"=⊥"` signifie que la machine `M` appliquée au mot `x` fini par s'arrèter sur l'état refusant. On crée ainsi 4 nouveaux éléments distincts qui ne sont pas des mots de `A^"+"`:

Dans notre langage de programmation, nous définissons un premier type de variable qui correspond à un mot de `A^"+"` ou à l'expression `ø` ou à l'expression `sf"⊤"` ou à l'expression `sf"⊥"` ou à l'expression `oo` et que l'on note par des lettres minuscules `e,x,y,z,...`. Puis nous avons un second type de variable qui correspond aux machines de Turing identifiées à leur programme, et que l'on désigne par des lettres majuscules `M,K,L,...`.

L'expression `M(x)"=⊤"` signifie que la machine c'est arrêté sur un état acceptant. L'expression `M(x)"=⊥"` signifie que la machine c'est arrêté sur un état refusant. L'expression `M(x)"="oo ` signifie que la machine ne s'arrête jamais de calculer. La machine `M` définit 3 ensembles :

L'approche algorithmique fait que l'on utilise le concept de suite avant celui d'ensemble. On définit un troisième type de variable qui correspond aux suites énumérables, finis ou non, de mots, et que l'on note par des lettres majuscules `E,X,Y,Z....`. Ces suites, sont donc chacune énumérable par une machine de Turing.

On note l'énumération par une machine de Turing `M` et commençant par `m` comme suit :

Etant donné une suite énumérable `E`, Soit elle est non-vide et il existe un permier mot `m` et une machine `M` qui l'énumère `E"="M"*"(m)`, ou plus simplement il existe une machine `M` qui l'énumère `E"="M^"+"(ø)`. C'est la définition de l'énumérabilité. Vous aurez remarqué que `M"*"` et `M^"+"` se comportent comme des machines énumérantes `M"*""="(M^0,M, M^2, M^3,...)` et `M^"+""="(M,M^2,M^3,...)` où `m^0"="sf"id"`. C'est la définition des opérateurs de Kleene `"*"` et `""^"+"` appliqués à une fonction.

L'ensemble `E` correspond à la suite `E` en ne tenant pas compte de l'ordre. L'ensemble `E` est dit semi-décidable si et seulement si la suite `E` est énumérable. La machine de Turing qui reconnait `E` se note pareillement. Ainsi `E(x)` calcul le prédicat `x "∈" E` et retourne `"⊤"` si `x` appartient à `E` , sinon soit il retourne `"⊥"` ou bien le calcul de s'arrête jamais ce qui se note par le résultat `oo`. L'ensemble est dit semi-décidable car pour chaque élément de l'ensemble, la machine de Turing le définissant répondra assurément oui en un temps fini, par contre pour chaque élément en dehors de l'ensemble, la machine de Turing ne répondra pas toujours non en un temps fini, d'où le concept de demi-réponse. Il n'y a que le oui qui est assuré, le non ne l'est pas.

Si on applique une machine de Turing `M` non pas à un mot mais à une suite énumérable de mots `E`, on note `M(E)` et cela correspond à un calcul parallèle en diagonal : A chaque nouvel élément de `E` passé en revue on lance un calcul en parallèle, et chaque calcul parallèle déjà lancé, avance d'un changement d'état les uns à la suite des autres dans l'ordre de leur création, et se termine par l'ajout d'un nouvelle élément de `E`. Et à chaque fois qu'un calcul s'arrète sur un état acceptant le résultat est émis. Cela produit une suite énumérable notée de façon ensembliste comme suit :

`M"*"(E)` lance une énumération d'énumérations qui peut être parcouru en parallèle par diagonales successives et produit donc une énumération. Considérons que `E "=" (e,K(e),K^2(e),K^3(e),...)` alors nous avons :

9) La machine de Chomsky

On peut présenter les grammaires de chomsky sous la forme de machines énumérantes, d'où le concept de machine de Chomsky.

La machine de chomsky est un machine virtuelle susceptible d'énumérer tout langage énumérable.

On pose un alphabet fini. La machine de Chomsky est identifiée à son programme qui est une grammaire formelle écrite dans un alphabet fini `A` augmenté d'un second alphabet fini `B` de caractères dits non-terminaux. La grammaire comprend deux types d'instruction, les mots étendus et les règles de réécriture. Les mot étendus sont des mots d'alphabet `A"∪"B`. Les règles de réécriture sont des couples de mots étendus que l'on note à l'aide du symbole `→`.