Les langages formels sont à la base de l'informatique et des mathématiques, leurs définitions sont équivalentes à celles des machines.
Nous allons les décrire en procédant à une construction pas à pas telle une génèse.
Cet éclairage nous permettra d'ouvrir une voie aux langages de programmation de nouvelles générations ayant la capacité de se définir eux-même, décuplant ainsi leurs capacités de factorisation.
Au départ nous avons un alphabet `A`, un ensemble de caractères servant de brique élémentaire à la construction des expressions du langage. Et déjà, de multiple possibilités s'offrent à nous pour définir des langages libres correspondant au choix de règles générales de composition de ces briques élémentaires, définissant un mode d'assemblage appelé aussi mode d'écriture, tel que l'écriture linéaire, l'écriture d'arbre, l'écriture de graphe, l'écriture alpha... À chaque mode d'écriture correspond un langage libre.
Pour trouver les modes d'écriture de plus en plus riches, on ajoute une à une des fonctionnalités nouvelles, mais toujours parmi les plus générales pour en limiter le nombre et l'arbitraire. La première fonctionnalité que l'on conçoit est celle d'un unique assemblage séquentiel d'un ou plusieurs caractères, pour former un mot. L'ensemble des mots d'aphabet `A` se note `A^"+"` et forme le langage libre pour ce mode d'écriture dit linéaire.
Une autre façon d'obtenir le même résultat par un procédé décentralisé, consiste à introduire une fonctionnalité décentralisée, qui s'applique à tous les caractères. On considére le caractères comme un opérateur unaire produisant un élément nullaire. L'opérateur unaire est une application d'un ensemble de départ inconnu vers un ensemble d'arrivé inconnu. Un élément nullaire signifie que l'élément n'est pas une application.
Et si on veut pouvoir répéter l'opération d'application d'un opérateur sur le résultat d'une première application d'un opérateur sur un élément de l'ensemble de départ, il faut que l'ensemble d'arrivé soit inclus dans l'ensemble de départ, et donc, sans ajouter de contrainte supplémentaire, que ce soit le même ensemble, `E`. Dés lors, un caractère est une application de `E "→" E` où `E` est un ensemble inconnu et arbitraire. Deux caractères `a,b` se composent en `a"∘"b` pour former une application de `E"→"E`, définie par :
`AA (a,b) "∈" (E"→"E)^2, AAx"∈" E,`
`(a"∘"b)(x) = a(b(x))`
On utilise également une seconde notation, dite française, qui inverse l'ordre d'écriture par rapport à la notation anglaise "∘". La composition se note à la française par absence de symbole :
`ab = b"∘"a`
L'appel de fonction se note à la française de façon exponentielle :
`x^a=a(x)`
Et lorsque les éléments de `E` sont disjoints des applications de `E"→"E`, alors l'appel de fonction peut se noter à la française par absence de symbole :
`xa=a(x)`
On perd dans cette dernière expression, le discernement par inférence de type, entre les deux possibilités `x "∈" E` et `x "∈" E"→"E`.
L'alphabet `A` est un ensemble d'opérateurs unaires. On le munit de l'opération de composition `"∘"`, et cela engendre un ensemble d'opérateurs unaires plus vaste `F` qui constitue un langage formel qui est une structure de semi-groupe :
`F="<"A,"∘>"`
C'est un semi-groupe de fonction de `E"→"E` engendré par les fonctions appartenants à `A`. Le semi-groupe est dit librement engendré par `A` si et seulement si quelque soit deux séquences distinctes de briques de `A` la composition correspondante (ici notée à la française) est également distincte.
`AA(n,m) "∈" N^2, AA (a_1,a_2,...,a_n) "∈" A^n, AA(b_1,b_2,....b_m) "∈" A^m`
`(a_1,a_2,...,a_n) != (b_1,b_2,...b_m) => a_1a_2....a_n != b_1b_2....b_m`
Pour certaines valeurs de `E` tel qu'un ensemble de cardinalité plus petite que celle de `A`, ce semi-groupe de fonctions ne peut pas être librement engendré par `A`. Par contre, un moyen simple existe pour qu'il le soit. Cela consiste à faire agire le semi-groupe sur lui-même par translation droite. C'est à dire que l'on choisie une action `T`. C'est une règle qui associe à chaque élément `x` du semi-groupe `F` une transformation `T_x` de l'ensemble `E` de telle sorte que le produit de deux éléments du semi-groupe `x"∘"y` (en utilisant l'opération du semi-groupe) est associée au composé des deux transformations correspondantes `AA(x,y) "∈" E^2`, `T_(x"∘"y)= T_x"∘"T_y`, ou en notation française `T_(xy)=T_xT_y` avec la propriété que `T` est une bijection de `F` dans `E` c'est à dire `T_F"="E` et `AA(x,y) "∈" E^2`, `x"≠"y => T_x"≠"T_y`
Notez que c'est une définition récurcive.
---- 5 juillet 2021 ----
suivante , `AAa "∈" F,AAx"∈" F,`
`T_a(x) =a"∘"x`
On choisie `E=F` en posant les définitions suivante, `AAa "∈" A,AAx"∈" F,`
`a(x) = a"∘"x`
Dans cette égalité, l'inférence de type précise que le premier `x` est dans `E` et constitue donc une conversion en élément nullaire de l'opérateur `x`, tandis que les deuxièmes `a` et `x` sont des opérateurs se combinant par composition `"∘"`, et l'opérateur résultat `a"∘"b` est implicitement plongé dans `E` pour le convertir en un élément nullaire. Si nous explicitons le plongement `varphi` de `F"→"E`, la propriété s'écrit :
`a(varphi(x))` `"="` `varphi(a"∘"x)`
Avec cette propriété, une composition quelconque de briques `a_1(a_2(a_3...))` est égale à `a_1"∘"a_2"∘"a_3...`, et quelque soit `u"∈" F,v"∈" F,` l'application `u"∘"x"∘"v` sera nécessairement différente de l'application `u"∘"y"∘"v` si `x` et `y` sont deux caractères distinctes.
On choisie `E=F` en posant les définitions suivante, `AAa "∈" A,AAx"∈" F,`
`a(x) = a"∘"x`
Dans cette égalité, l'inférence de type précise que le premier `x` est dans `E` et constitue donc une conversion en élément nullaire de l'opérateur `x`, tandis que les deuxièmes `a` et `x` sont des opérateurs se combinant par composition `"∘"`, et l'opérateur résultat `a"∘"b` est implicitement plongé dans `E` pour le convertir en un élément nullaire. Si nous explicitons le plongement `varphi` de `F"→"E`, la propriété s'écrit :
`a(varphi(x))` `"="` `varphi(a"∘"x)`
Avec cette propriété, une composition quelconque de briques `a_1(a_2(a_3...))` est égale à `a_1"∘"a_2"∘"a_3...`, et quelque soit `u"∈" F,v"∈" F,` l'application `u"∘"x"∘"v` sera nécessairement différente de l'application `u"∘"y"∘"v` si `x` et `y` sont deux caractères distinctes.
L'ensemble des mots correspond à l'ensemble `E` des applications `u` de `E "→" E` définie par `AAx"∈" E, u(x) = u"∘"x`. Pour résumer, nous obtenons cette définition récurcive :
`A ⊆ E`
`E={u ∈ E"→" E "/" AAx"∈" E, u(x) "=" u"∘"x}`
Par cette définition, nous avons doté le langage libre d'une sémantique, qui n'apporte aucune information supplémentaire. Chaque mot `u` appartenant à `E` désigne un objet mathématique plus complexe qui est l'application de `E "→" E` définie par `AAx"∈" E, u(x) = u"∘"x`. C'est une définition, répartie sur tous les éléments, de ce qu'est la concaténation. Ainsi `E="<"A,"∘>"` constitue le semi-groupe libre pour le mode d'écriture linéaire.
---- 4 juillet 2021 ----
Un langage formel est un ensemble d'expressions reconnues par une machine. Les expressions sont des assemblages de briques élémentaires. Les machines sont des assemblages de règles de production rudimentaires.
La forme du langage n'est pas prise en compte. On la codifie en détectant quelles sont les briques composant les expressions et en choisissant un mode d'assemblage de ces briques. Le premier mode choisi est l'écriture linéaire. Les expressions sont des successions de briques.
L'écriture linéaire : Les briques sont des caractères. Les expressions sont des successions de caractère appelées mots. L'ensemble des différents caractères constitue l'alphabet. L'ensemble de tous les mots constitue le langage libre qu'est le semi-groupe libre engendré par l'alphabet et l'opérateur de concaténation. Le langage formel en est un sous-ensemble reconnu par une machine.
La grammaire : La forme de la machine n'est pas prise en compte. On la codifie en détectant quelles sont les règles de production rudimentaire qui la compose et en choisissant un mode de production. Le premier mode choisi est celle d'une grammaire.
« Un langage formel est un sous-ensemble de l'ensemble des mots, reconnu par une grammaire. »
Un langage formel est un ensemble d'expressions reconnues, énumérées ou engendrées par une machine. Dés lors, on peut résumer la définition du langage formel par cette phrase :
« Un langage formel est un ensemble énumérable. »
Pour chaque mode d'écriture, il existe un langage libre qui est engendré par un ensemble de règles générales. Le langage formel en est un sous-ensemble reconnu par une machine.
Le langage libre est un langage formel plus vaste et plus simple, il est donc également énumérable.
Le concept de machine n'est pas défini formellement. Il va l'être avec Turing, Church, Smullyan, .... Une machine est un procédé mécanique qui possède un état initial de mise en route, et qui peut ne jamais s'arréter, qui enregistre des données en entrées tel que mécaniquement c'est possible de le faire, qui calcule à partir de ces données par un procédé mécanique d'autres données, et qui les écrits en sortie tel que mécaniquement c'est possible de le faire.
Une machine énumère un langage `L` si et seulement si la machine initialisée va produire toutes les expressions du langage `L` les unes à la suite des autres. Et donc, quelque soit une expression du langage `L`, la machine finira au bout d'un temps fini par produire cette expression.
Une machine reconnaît un langage `L` si et seulement si la machine appliquée à une expression du langage `L`, c'est à dire initialisée et prenant comme entrée l'expression considérée, répond oui. Et appliquée à tout autre expression du langage libre, soit elle ne répond pas c'est à dire ne s'arrête jamais, ou soit elle répond non.
À partir d'une machine énumérant un langage formel `L`, on peut construire une machine reconnaissant le langage `L` dans le langage libre. Et réciproquement, à partir d'une machine reconnaissant le langage `L` dans le langage libre, le langage libre étant également énumérable, on peut construire une machine énumérant le langage `L`.
Un langage formel `L` d'alphabet `A` est engendré par une grammaire `G`. La grammaire utilise deux sortes d'alphabets `A` et `B`. les caractères de `A` sont dits terminaux et les caractères de `B` sont dits non-terminaux. La grammaire engendre un langage formel plus vaste d'alphabet `A"+"B` qui est un ensemble de règle de production rudimentaires.
L'ensemble des mots et des règles de production produites par la grammaire constitue la mémoire du processus de production puisqu'ils sont réutilisés pour produire d'autres mots et règles de production. Ainsi au cours de l'énumération du langage `L`, une énumération souterraine d'un langage plus vaste d'alphabet `A"+"B` est faite.
Les premières règles sont les mots mêmes que l'on souhaite ajouter au langage.
Puis viennent les règles pour produire le langage libre. Ce sont les règles de composition, la règle de concaténation des mots. La règle de concaténation indique que si `U` et `V` sont deux mots du langage formel alors le mot `UV` obtenue en concaténant `U` à `V` fait également parti du langage formel.
Se pose alors la question de savoir comment écrire cette règle dans le même mode d'écriture. Pour cela on utilise une brique non-terminal `"→"` qui va indiquer la production, et on utilise une autre brique non terminal `U` pour désigner un mot quelconque du langage. Par exemple considérons l'alphabet `{a,b,c,d}`, Les règles se regroupent en la grammaire suivante :
`U"→"UU`
`U"→"a`
`U"→"b`
`U"→"c`
`U"→"d`
La première règle indique qu'un mot peut être la concaténation de deux mots. Et les deux mots en question sont des mots quelconques qui peuvent ne pas être égaux mais qui doivent être produits par la grammaire. Les règles suivantes indique que le mot en question peut être un caractère terminal.
---- 4 juillet 2021 ----
En écriture linéaire, le langage formel se définie par la phrase suivante, qu'il faut compléter par la définition d'une sémantique :
Pour trouver les modes d'écriture de plus en plus riches, on ajoute une à une des fonctionnalités nouvelles, mais toujours parmi les plus générales pour en limiter le nombre et l'arbitraire. La première fonctionnalité que l'on conçoit est celle d'un assemblage séquentiel d'une ou plusieurs briques, pour former un mot. Soit `A` l'ensemble des briques élémentaires. Cet ensemble `A` est appelé l'alphabet. L'ensemble des mots d'aphabet `A` se note `A^"+"`.
Une autre façon d'obtenir le même résultat consiste à introduire une fonctionnalité décentralisée qui s'applique à toutes les briques. On considére les briques comme des opérateurs unaires produisant des éléments nullaires. L'opérateur unaire est une application d'un ensemble de départ vers un ensemble d'arrivé. Un élément nullaire signifie que l'élément n'est pas une application.
On sépare le caractère qui est un composant du mot, de la règle qui produit le mot. L'ensemble des différents caractères s'appelle l'alphabet. L'ensemble des règles rudimentaires de production s'appelle la grammaire.
La règle s'écrit dans un alphabet plus riche utilisant d'autres caractères dits non-terminaux (deuxième type).
Le langage formel ne comprend que les mots composées de caractères terminaux (premier type). Ainsi tout langage formel, tel la pointe d'un iceberg sortant de l'eau, est inclus dans un langage formel plus vaste comprenant ses règles de production sous forme de mots.
Et on pourrait répéter cette opération, si on ajoute des règles de production supplémentaires pour compléter ce langage formel plus vaste. Ces nouvelles règles étant écrites dans un alphabet plus riche utilisant d'autres caractères dits de troisième type, le langage formel plus vaste se trouve ainsi inclus dans un langage formel encore plus vaste. Et il y aura 3 niveaux emboitée de langage : les mots du langage formel (langage du premier type), les règles de production des mots (langage du second type), les règles de production des règles de production des mots (langage du troisième type).
Mais on va s'arrtéter qu'aux deux premier niveaux.
La production est de nature mécanique. Autrement dit, la règle de production est équivalente à une machine, et le qualificatif rudimentaire indique que l'arrêt est sûr, de complexité linéaire et davantage encore que le procédé mécanique mis en oeuvre est particulièrement simple. Une machine est constituée d'un assemblage de règles de production mécaniques rudimentaires. La régle rudimentaire prend en entrée 1 ou 2 ou 3 ou 4 mots du 1er ou 2-ième type et retourne une suite finie d'expression du 1er ou 2-ième type.
Un langage formel comprend toutes les mots composées de caractères terminaux qu'il est possibles de construire à partir d'un ensemble de caractères (terminaux et non-terminaux) et d'un ensemble de règles de production rudimentaires.
Un tel dispositif regroupant une carrière de caractères (terminaux et non terminaux) et des règles de production mécaniques rudimentaires, constitue une machine qui va énumérer le langage en explorant toutes les voix de constructions possibles. La machine va produire, les une à la suite des autres, en pouvant se répéter, toutes les mots du langage du premier type et du second type. Une telle machine s'appelle un énumérateur. Et quelque soit un mot du langage formel en question, l'énumérateur finira au bout d'un temps fini par produire ce mot.
La définition du langage formel n'est pas à ce stade complétement achevée. On a, là, simplement présenté la syntaxe du langage, qui constitue cette machine énumérant le langage ou reconnaissant le langage. Et ce n'est qu'une première partie. La seconde partie, que l'on appelle la sémantique, indique ce que signifie le langage. Un langage formel a pour but de communiquer sans aucune ambiguïté par opposition à un langage naturel, et possède donc une signification parfaitement bien définie..., qui reste donc à définir.
Pour une expression donnnée du langage, la syntaxe se développe en une preuve que l'expression en question appartient bien au langage, et la sémantique constitue l'ensemble des entités qu'elle désigne.
Avant de hiérarchiser les langages en fonction du perfectionnement des machines capables de les reconnaitre, nous allons explorer les différents modes d'écriture possible, différents modes d'agencement des briques, différentes règles de composition de briques se voulant les plus générales possibles, et qui paradoxalement nous permettrons de définir ce qu'est une machine.
Et on commence par présenter le premier mode d'écriture le plus simple, qu'est l'écriture linéaire, la succession de caractère. Puis nous décrirons des écritures non linéaires, écriture Alpha, écriture d'arbres, écriture de graphes. Ces écritures se contiennent mutuellement, alors, qu'elle en est l'intérêt ? Elles sont nécessaires pour définir mécaniquement le partage de données et la matrice mémoire d'un procédé général de calcul. Puis, en utilisant une écriture plus riche, non linéaire, on peut utiliser la structure de l'écriture pour décentraliser le calcul la produisant. L'analyse consiste à diviser le problème en sous-problèmes et à déléguer la charge de résolution des sous-problèmes à des sous-structures. Ainsi l'écriture dans un mode plus sophistiqué est capable de contenir dans ses expressions mêmes, une partie de la machine qui les produits.
Chaque mode d'écriture définit une notion spécifique de langage libre. Le langage libre se veut ne signifier rien d'autre que lui-même. Chaque expression du langage libre sera décrite syntaxiquement à l'aide des règles générales d'agencements choisies. Et l'on complètera cette description syntaxique par une description sémantique canonique constituant un modèle canonique, une sorte d'auto-représentation, mais qui n'apporte aucune information supplémentaire, le langage libre ne devant signifier que lui-même. Cette auto-représentation constituera une structure de l'écriture.
La partie non calculable est simplement posée comme acquise et le langage formel ne fait alors que compléter cet acquit par ses procédés calculatoires. L'alpabet peut alors être infini, un infini de n'importe quel nature, et l'ensemble des règles rudimentaires également.
Pour trouver les modes d'écriture de plus en plus riches, on ajoute une à une des fonctionnalités nouvelles, mais toujours parmi les plus générales pour en limiter le nombre et l'arbitraire. La première fonctionnalité que l'on conçoit est celle d'un assemblage séquentiel d'une ou plusieurs briques, pour former un mot. Soit `A` l'ensemble des briques élémentaires. Cet ensemble `A` est appelé l'alphabet. L'ensemble des mots d'aphabet `A` se note `A^"+"`.
Une autre façon d'obtenir le même résultat consiste à introduire une fonctionnalité décentralisée qui s'applique à toutes les briques. On considére les briques comme des opérateurs unaires produisant des éléments nullaires. L'opérateur unaire est une application d'un ensemble de départ vers un ensemble d'arrivé. Un élément nullaire signifie que l'élément n'est pas une application.
---- 30 juin 2021 ----
Par exemple considérons l'alphabet `{a,b,c,d}`, et considérons la règle `bc"→"abb`. Celle-ci signifie que l'on peut remplacé dans tout mot, n'importe quelle portion de mot `bc` par `abb` et produire le mot ainsi modifié.
Puis viennent les règles de substitutions inspirées par la linguistique. Pour écrire la règle en restant dans le même mode d'agencement ou d'écriture, on utilise une brique non-terminal `"→"`. Par exemple considérons l'alphabet `{a,b,c,d}`, et considérons la règle `bc"→"abb`. Celle-ci signifie que l'on peut remplacé dans tout mot, n'importe quelle portion de mot `bc` par `abb` et produire le mot ainsi modifié.
Mais cette définition s'avère insuffisante pour différentier à coup sûr `a` de `b`, pour faire qu'ils désignent deux objets distincts, deux applications distinctes. En effet `a` et `b` peuvent désigner une même application de `E"→"E`, auquel cas seul leur nom est différent. Or s'ils sont syntaxiquement distincts de par leur nom, ils doivent alors être distincts dans le langage libre. Ils doivent désigner des objects distincts.... Comment introduire cette identification dans la définition de l'application ?
Soit `F` l'ensemble des opérateurs unaires, qui contient les briques appelées opérateurs générateurs, `A "⊆" F`, et qui est engendré par les compositions de ces opérateurs générateurs `F="<"A,"∘>"`. Un moyen simple de s'assurer de cette identification nominale consiste à plonger `F` dans `E` (comme `E` est inconnu et arbitraire, cela consiste à ajouter dans `E` une copie des éléments de `F` mais sous forme nullaire) et de poser la règle suivante, `AAa "∈" A,AAx"∈" F,`
`a(x) = a"∘"x`
Etant donné un alphabet `A = {a,b,c}`. Le langage libre d'alphabet `A` se note `A^"+"`. C'est l'ensemble de tous les mots non vides qu'il est possibles d'écrire dans cet alphabet :
`A^"+" = {a, b, c, aa, ab, ac, ba, b\b, bc, ca, cb, c\c, aaa, aab,...}`
On ne fait pas de distinction entre un caractère et le mot d'un seul caractère qui le contient. De telle sorte que `A"⊂"A^"+"` et que `A^"+"` constitue la clôture de `A` par concaténation. On note la concaténation de deux mots par simple juxtaposition ou en utilisant l'opérateur de concaténation, "·". Ainsi `x"·"y=xy` désigne le mot obtenue en concaténant le mot désigné par la variable `x` et le mot désigné par la variable `y`.
`A^"+" = "<"A,"·>"` désigne le semi-groupe libre engendré par l'alphabet `A` et par l'opération de concaténation, et est appelé le langage libre d'alphabet `A`.
Un langage `L` d'alphabet `A` est par définition un sous-ensemble du langage libre `A^"+"`. La seul contrainte que nous nous fixons dans cette terminologie, est que l'alphabet `A` doit être fini, et que le sous-ensemble `L` doit être reconnue par une machine.
Parfois on ajoute le mot vide, qui est l'élément neutre de l'opération de concaténation, et que l'on note `ε`. On obtient le monoïde libre d'alphabet `A` noté :
`A"*" = A^"+" uu {epsilon} = "<"A, epsilon,"·>" `
Le suffixe `"*"` est l'opérateur de Kleene. On parlera de langage d'alphabet `A` auquel on a ajouté le mot vide `ε`.
Le langage libre `A^"+"` est le semi-groupe libre engendré par l'alphabet et l'opérateur de concaténation `"<"A,"·>"`. Et il possède une auto-représentation `varphi`, en un semi-groupe de fonctions, obtenu en faisant opérer le semi-groupe sur lui-même par translation droite. Et on démontre qu'il y a bien un iosomorphisme entre ces deux semi-groupes :
` "<"A,"·>" ≅_varphi ({u in A^"+""→"A^"+" "/" AAx"∈" A^"+", u(x) "=" varphi^-1(u)"·"x}, "∘")`
` "<"A,"·>" ≅_varphi "<"{u in varphi(A) "/" AAx"∈" A^"+", u(x) "=" varphi^-1(u)"·"x}, "∘>"`
Où `varphi` est une application de `A^+ "→" (A^"+" "→" A^"+")`.
La seconde fonctionnalité qui vient à l'esprit ressemble à la précédente. Elle consiste à considérer les briques comme des opérateurs unaires produisant des opérateurs unaires de même type.
Puis on utiliser les briques tantôt comme des opérateurs unaires, tantôt comme des éléments nullaires. On a donc posé une bijection `varphi` de l'ensemble des opérateurs unaires sur l'ensemble des éléments nullaires, que l'on utilise implicitement pour converrtir les types. Ainsi, à partir de quatres briques `a,b,c,d`, l'expression `a(b(c)(d))` signifie que l'on a appliqué l'opérateur unaire `b` sur l'élément `c` puis que le résultat qui est un opérateur unaire, est appliqué à nouveau sur l'élément `d`, puis le résultat qui est un opérateur unaire et converti en un élément nullaire qui sert d'argument à l'opérateur `a`.
Les briques se comportent ainsi comme des opérateurs d'arité soit nullaire ou unaire, la syntaxe permettant de déterminer à chaque fois quel rôle leur est demandé.
Et pour les mêmes raisons invoquées au paragraphe précédent, il faut que l'ensemble d'arrivé soit inclus dans l'ensemble de départ, et donc, sans ajouter de contrainte supplémentaire, que ce soit le même ensemble `E`. Dés lors, une brique dans son rôle d'opérateur unaire, est une application de `E "→" E` où `E` est un ensemble inconnu et arbitraire d'opérateurs unaires de `E "→" E`. Ce qui se note :
`E sube E "→" E`
Deux expressions `u,v` s'appliquent en `u(v)` pour former encore une application de `E"→"E`, qui peut donc à nouveau s'appliquer sur une expression `w` pour former `u(v)(w)`. Dans le langage libre, l'expression `u(v)(w) est différente de l'expression `u(v(w)). Comment introduire cette distinction dans la définition de l'application ?
---- 30 juin ----
La troisième fonctionnalité consiste à considérer les briques comme des opérateurs multi-aire produisant des éléments nullaires.
---- 27 juin ----
Etant donné une présentation `B = {a,b,f"(.)",g"(.,.)"}`, où l'arité des opérateurs symboliques est indiqué par un suffixe `(.), (.,),(.,.,.),...`, ou par absence de suffixe si ce sont des opérateurs nullaires, autrement dit, des éléments. Le langage libre de présentation `B` se note `"<"B">"`. C'est l'ensemble de toutes les compositions d'opérateurs possibles parmi les opérateurs de la présentation `B`.
`"<"B">" = {a, b, f(a), f(b), g(a,a), g(b,a), g(f(a),a), g(f(a),f(a)), ...}`
On ajoute à la structure libre, les termes récurcifs. Ce sont les compositions de taille infinie qu'il est possible de définir par des compositions récurcives de taille finie. On utilise les entiers pour désigner les places dans un terme. Ainsi dans le terme `g(g(a,b),f(a))`, l'entier 1 désigne le terme globale, l'entier 2 désigne le sous-terme `g(a,b)`, l'entier 3 désigne `a`, l'entier 4 désigne `b` l'entier 5 désigne `f(a)`, et l'entier 6 désigne `a`. Ainsi par exemple, nous avons :
`1` désigne une nouvelle variable inconnue `X`.
`f(1)` désigne le terme infini `f(f(f(...)))`
`f(2)` désigne `f(X)` où `X` est une nouvelle variable inconnue.
`g(2,2)` désigne `g(X,X)` où `X` est une nouvelle variable inconnue.
`g(2,3)` désigne `g(X,Y)` où `X` et `Y` sont deux nouvelles variables inconnues.
`g(a,1)` désigne le terme infini `g(a,g(a,g(a, ... )))`
`g(2,1)` désigne le terme infini `g(X,g(X,g(X, ... )))` où `X` est une nouvelle variable inconnue.
Et chacune de ces compositions constitue un élément de la structure récurcive libre. On pourrait défnir un langage plus restreint éliminant tout terme contenant des inconnues, mais la restriction peut être faite après-coup et n'est donc pas pertinente. Car on prend le langage le plus vaste. Mais par contre, on ne va pas distinguer deux expressions récurcives qui produisent le même terme développé infini. Ce choix consiste à placer l'identité des termes dans ce qu'ils produisent syntaxiquement et non dans la façon dont ils le produisent.
On peut définir une machine comme un assemblage mécanique de rouages, de courroies de transmission, d'aiguillages, de flip-flop (mémoire à deux états), parfaitement bien définie par la mécanique classique, et qui entrent en interaction avec d'autres machines en s'emboitant. Des machines plus rudimentaire constitué d'une succession de flip-flops représentent des supports mémoire pour les données ou les résultats calculés.
Parallèlement à la définition de ces machines mécaniques, on définit le langage de programmation Brainfuck (BF).
...
Considérons deux langages formels `bbbA` et `bbbB` définis sur un alphabet commun `A`. Les opérations suivantes construisent de nouveaux langages formels :
La concaténation `bbbAbbbB= {ab "/" EEa"∈" bbbA, EEb"∈" bbbB}`. C'est l'ensemble des mots composés d'un mot de `bbbA` suivi d'un mot de `bbbB`.
L'union `bbbA uu bbbB`
L'intersection `bbbA nn bbbB`
Le quotient à droite `bbbA"/"bbbB= {v "/" EEv"∈"A^"+", EEb"∈" bbbB, vb"∈" bbbA}`. C'est l'ensemble des mots qui sont une première partie d'un mot de `bbbA` tel que la partie suivante est un mot de `bbbB`.
Par contre, le complément d'un ensembe énumérable n'est pas assurément énumérable. Car s'il l'était, le problème de l'arret serait décidable.
---- 20 juin 2021 ----
Une machine de Turing, à `n` états et d'alphabet `A` comprenant au moins un caractère appelé caractère blanc, est définie par une application `f` de `{1..n}"×"A ->{0..n}"×"A"×"{g,d}`. L'application prend en entrée un numéro d'état autre que zéro, et un caractère, et retourne en sortie un état, un caractère et un sens de déplacement. La machine se compose d'un ruban indéfini dans les deux sens, et d'une tête de lecture-écriture qui peut se déplacer d'une case à droite ou à gauche sur le ruban. À l'état initial, le ruban est rempli de caractère blanc. Lors d'un état quelconque `u` autre que zéro, la machine est à l'état `u`. La machine lit le caractère `x` présent sous la tête de lecture-écriture, applique la fonction `f` à `(u,x)` qui produit `f(u,x)=(v,c,s)`, change d'état en `v`, écrit le caractère `c` sous la tête de lecture-écriture, et déplace celle-ci d'une case dans le sens `s`. La machine s'arrête lorsque l'état `0` est rencontré, ce qui peut ne jamais se produire.
La thèse de Church-Turing affirme que toute fonction calculable est calculable par une machine de Turing. C'est une thèse démontrable si on se limite à une notion de calculabilité resteinte à la mécanique classique faite de rouages emboités, de courroies de transmissions, d'aiguillages et de dispositifs mécaniques à deux états. Parcontre, il existe une version non démontrable, appelé opinion de Church-Turing, si on étend la notion de calculabilité à tous ce que peut produire un système physique. La non démontrabilité provient du fait que ce n'est alors plus une théorie mathématique mais une théorie physique.
A partir de la machine de Turing, il est facile de concevoir des machines davantage sophistiquées, permettant une programmation davantage facile, tout en étant assurées de couvrir les mêmes domaines de calculabilité.
Les fonctions récursives constitue une autre façon de définir les fonctions calculable. Les fonctions considérées ont toutes une arité fixe d'entrée et une arité fixe de sortie. On commence par définir les fonctions primitives récurcives. Ces fonctions sont définies à partir d'un nombre restreint de fonctions élémentaires en utilisant la composition et le schéma de récurrence. Puis on définies les fonctions récurcives à partir des fonctions primitives récurcives en utilisant le schéma de minimisation.
On utilise des variables `x,y,z....`, chacune désignant un mot inconnu. La concaténation se note par simple juxtaposition. Ainsi `xy` désigne le mot obtenue en concaténant le mot désigné par la variable `x` et le mot désigné par la variable `y`.
On utilise un deuxième type de variable pour désigner des séquences de mots, et que l'on note avec un tilda. Ainsi, on utilise les variables `tilde x, tilde y, tilde z, ....`, chacune désignant une séquence de mots inconnus. Le tilde est une indication de type intégré dans le nom de la variable, aussi la variable `tildex` n'a rien à voir avec la variable `x`, ce sont deux variables distinctes.
La séquence de mots `tildex` peut se construire à partir de mots désignés par les variables `x,y,z, ...` par exemple `tilde x = (x,y,z)`. Les séquences peuvent être vides. La projection sur la `i`-ième composante se note `tilde(x)_i`. Ainsi `(x,y,z)_1"="x` et `(x,y,z)_2"="y` et `(x,y,z)_3"="z`. La concaténation de deux séquences se note par simple juxtaposition tel que par exemple `tilde x tilde y`.
Les fonctions considérées ont toutes une arité fixe d'entrée et une arité fixe de sortie. On utilise des variables-fonctions. Par défaut, leur aritée fixe de sortie est inconnues comme comme celle des séquences de mots, et c'est l'inférence de type qui en précisera l'arité ou la taille. D'autre part on précise, uniquement lors de la déclaration de variable-fonction, son arité d'entrée à l'aide d'un suffixe; absence de suffixe pour désigner une variable, suffixe `"(.)"` pour désigner une variable-fonction unaire, suffixe `"(.,.)"` pour désigner une variable fonction binaire, etc.. Notez que ce suffixe ou absence de suffixe n'est utilisé qu'au moment de la déclaration de la variable-fonction. Si la variable-fonction est d'arité d'entrée fixe inconnue, on note la variable fonction avec le suffixe `"(...)"` uniquement lors de sa déclaration.
L'inférence de type va préciser les arités fixes inconnues ainsi que la taille des séquences d'arguments. Considérons par exemple la proposition suivante :
`f in (A^"+")^n "→" (A^"+")^r`
`AA tildex, EE tilde y, (f(tilde x) = tilde y) "et" EE g(...), g(tilde y)=tildex`
L'inférence de type va préciser les types. Le type de `tildex` sera précisement une séquence de `n` mots. Et le type de `tilde y` sera précisement une séquence de `r` mots. Les quantifications se feront sur ces types spécifiques déterminés par l'inférence. L'inférence fonctionne dans les deux sens, faisant que le type de `g` sera précisement une fonction prenant une séquence de `r` mots pour produire une séquence de `n` mots.
On définit maintenant un certain nombre de fonctions primitives récurcives de base qui permettront de définir toutes les autres :
`AA f "(...)" AA g"(...)", f"(" g ")" (tilde x) "=" f( g(tilde x))`
`AA f "(...)" AA g"(...)"AA h "(...)", f"(" g, h")" (tilde x) "=" f( g(tilde x) h(tilde x) )`
`AA f "(...)" AA g"(...)"AA h "(...)"AA k "(...)", f"(" g, h, k ")" (tilde x) "=" f( g(tilde x) h(tilde x) k(tilde x))`
...
`A= {a,b}`
`h= "Rec"(f_a, f_b,g_a, g_b) <=> ( (AA tilde m"," h(a","tilde m) = f_a(tilde m)), (AA tilde m"," h(b","tilde m) = f_b(tilde m)) , (AAu AA tilde m"," h(ua"," tilde m)= g_a(u","h(u","tilde m)"," tilde m)), (AAu AA tilde m"," h(ub"," tilde m)= g_b(u","h(u","tilde m)"," tilde m)) )`
On considère la relation d'ordre totale sur l'ensemble des mots selon l'ordre de la tailles des mots, et pour les mots de même taille, selon l'ordre lexicographique.
`g"=Min"(f,tilde v) <=> AA tilde u, g(tilde u) "=Min"{x "/" f(x, tilde u) "=" tilde v}`
Un ensemble est énumérable si on peut construire tous ses éléments à partir de quelques briques élémentaires, et de quelque règles de constructions
---- 14 juin 2021 ----
La présente description de la machine de Turing s'applique pour une éciture linéaire. On obtient une même description pour une écriture de graphe en remplaçant la liste des déplacements possibles linéaires `{g,d}` par la liste des déplacements possibles dans un graphe qui sont les accès aux fils et les accès aux parents. Le caractère blanc correspond alors à une fonction symbolique unaire. À l'état initiale de la machine, le ruban comprend une succession infinie de caractère blancs emboités.
On formalise la machine de trois façons possibles : La machine de Turing, les fonction récurcives, l'énumérabilité de Smullyan.
Voir langageAlphabet.htm
Voir : Informatique et Langage formel
Voir langage Formelle et hierachie de Chomsky
Les ensembles constituent une catégorie d'éléments que l'on note `bbbE`. Puis le même symbole d'appartenance `in` est utilisé pour indiquer qu'un élément `x` appartient à la catégorie des ensembles : `x "∈" bbbE`. La notation ensembliste étend les fonctions aux ensembles comme suit :
`AA E"∈" bbbE ,`
`AA f "∈" (E"⤏"),`
`AA A"∈" bbbE "/" A"∉"E,`
`f(A) = {f(x) "/" EEx in A "∩" sf"Dom"(f)}`
L'expression `bbbE` désigne la catégorie des ensembles qui est une sous-catégorie des éléments. L'expression `AA E"∈"bbbE,` signifie quelque soit un ensemble `E`. L'expression `AA f "∈" (E"⤏"),` signifie quelque soit une fonction `f` d'ensemble de départ `E`. L'expression `AA A"∈" bbbE "/" A"∉"E,` signifie quelque soit un ensemble `A` qui n'est pas un élément de `E`. L'image de `A` par `f`, notée `f(A)` est l'ensemble des images par `f` des éléments de `A` qui appartienent au domaine de définition de `f`.
Mais ce n'est pas une extension au sens propre du terme, ni dans son but, ni dans sa forme. Il s'agit d'un second rôle de la fonction `f` qui est activé par un typage. Et ce typage consiste à avoir comme argument, non pas un élément du type attendu, mais un ensemble d'éléments. Notez que cette dernière condition n'est pas suffisante car l'élément attendu peut aussi être un ensemble, faisant que le typage devient dynamique c'est à dire dépendant de la valeur d'une variable, ce qui complexifie le raisonnement qui ne peut pas s'appliquer à toute les valeurs d'une variable d'un type donné. C'est pourquoi généralement on place cette notation ensembliste sous l'égide d'une condition d'intégrité. La condition est qu'il y ait une distinction catégorielle entre éléments et ensembles qui doit pouvoir être perçu du seul point du vue de la fonction. Cette condition correspond d'abord au choix d'un ensemble de départ, qui ne doit pas contenir parmi ses éléments, d'ensemble contenant des éléments de cet ensemble de départ.
`AAx "∈" sf"Dep"(f), x"∈" bbbE=>x"∩"sf"Dep"(f)"="Ø`
Littéralement : Quelque soit un élément de l'ensemble de départ de `f`, si cet élément est un ensemble alors il doit être disjoint de l'ensemble de départ de `f`.
Et cette condition impose au système de typage l'interdiction de définir un type mélangeant des éléments de l'ensemble de départ de `f` avec des ensembles contenant des éléments de l'ensemble de départ de `f`.
`AAT"∈"bbbT, (sf"Dep"(f)"∩"T"≠"Ø) => (AAx"∈"T, x"∉"bbbE "ou" x"∩"sf"Dep"(f)"="Ø)`
`AAT"∈"bbbT, (EEx"∈"T, x"∈"bbbE "et" x"∩"sf"Dep"(f)"≠"Ø) => (AAx"∈"T, x "∉" sf"Dep"(f))`
Comprenez que cette définition se décline pour les fonctions à plusieurs arguments de la même manière, car un ensemble peut être un produit d'ensemble. Le typage enembliste se déclenche alors si l'un des arguments possède un type satisfaisant la condition.
faisant par exemple que `a` étant un élément et `A` étant un ensemble d'éléments, et `g` étant une fonction à deux arguments , nous avons. `g(a,A)=g({x},A)`
Voici un exemple de langage formel. Tout y est parfaitement emboité. Le langage est totalement rigide, et se fonde sur un simple principe de calcul. On verra comment à l'aide de l'inférence de type on pourra réduire considérablement la formulation pour ne faire apparaitre que l'essentiel.
`P` représente une fonction propositionnelle qui donne une réponse `0` ou `1`, pour tout couple d'éléments.
La notation ensembliste définie l'image par `F` de l'ensemble `A` comme étant l'ensemble des images par `F` des éléments de `A`.
La relation est une notion plus générale que celle de fonction. La notation ensembliste des fonctions découle logiquement de la notation ensembliste des relations. Cette notation étend la définition des relations aux ensembles, comme suit : Quelque soit la relation `R(".,.")` :
`R(A,B) <=> ( (AAx "∈" A"," EE y "∈" B"," R(x,y)), (AAy "∈" B "," EE x "∈" A "," R(x,y)))`
`R(x,A) <=> (EEy "∈" A ", R(x,y))`
`R(A,x) <=> (EEy "∈" A ", R(y,x))`
et donc aussi des fonctions aux ensembles comme suit : Quelque soit des relations `R(".,.")`, `S(".,.,.")` Quelque soit des fonctions `f(".")` et `g(".,.")`, quelque soit des ensembles `A,B`, quelque soit un élément `x` nous avons par définition :
`f(A) ={f(x) "/" EEx"∈"A, x"∈Dom"(A)}`
`S(z,A,B) <=> ( (AAx "∈" A"," EE y "∈" B"," S(z,x,y)), (AAy "∈" B "," EE x "∈" A "," S(z,x,y)))`
`g(A,B) ={g(x,y) "/" EEx "∈" A, EEy "∈" B, (x,y) "∈Dom"(B)}`
`g(x,A) = {g(x,y) "/" EEy "∈" A, (x,y) "∈Dom"(A)}`
`g(A,x) = {g(y,x) "/" EEy "∈" A, (y,x) "∈Dom"(A)}`
---- 17 août 2022 ----