g(h,k) |
g|h,k| |
 |
 |
Table des matières :
La structure (M,*) est un semi-groupe si et seulement si l'opération * est associative et interne dans M. C'est à dire si elle vérifie les 2 axiomes suivants :
1) L'opération * est interne dans M : Quelque soit x, y appartenants à M, nous avons x*y∈M
2) L'opération * est associative : Quelque soit x, y, z appartenants à M, nous avons x*(y*z) = (x*y)*z
L'élément neutre joue un rôle tout à fait à part et indépendant dans les monoïdes, c'est pourquoi on le retire pour ne considérer que l'a structure de semi-groupe, une structure jugée davantage pertinente. En faite on peut toujours rajouter l'élément neutre sans perturber la structure de semi-groupe, et il est unique. Sa place existe donc, de sorte qu'il existe d'une façon catégorielle. Mais nous laissons sa place vide lorsque celle-ci est vide car elle dénote un choix, certe un choix simple, mais un choix qui participe au processus constructif de la structure. Et l'approche constructive est différente de l'approche catégorielle.
Un semi-groupe de fonctions, est un semi-groupe dont les éléments sont des fonctions unaires et dont l'opération est l'opération de composition de fonction notée °.
Dans un monoïde quelconque (M,*), l'expression x*y*z possède un sens physique qui dénote une succession de transformations x, puis y, puis z. Intuitivement cela correspond à la composition de transformations qui sont des fonctions unaires. Et l'intuition correspond à la réalité, c'est à dire que tout semi-groupe est isomorphe à un semi-groupe de fonctions. Aussi il conviendrait d'appeler cette structure, un fonctoïde, plutôt qu'un semi-groupe.
La démonstration se fait par construction. On pose un monoïde M quelconque, et on construit un monoïde de fonctions isomorphes à M, en faisant simplement opérer le monoïde M par multiplication à gauche sur lui-même. L'agitateur P est donc défini comme suit. Quelque soit a appartenant à M :
P(a) = (x-->a*x)
On remarque que ({P(x) / x∈M },°) est un monoïde de fonctions, que l'on peut noter (P(M),°). Les deux axiomes sont vérifiés. Quelque soit x, y, z appartenants à M :
L'opération ° est interne : P(x)°P(y) = (u-->x*u)°(u-->y*u) = P(x*y)
L'opération ° est associatif : P(x)°(P(y)°P(z)) = P(x*y*z) = (P(x)°P(y))°P(z)
P est un isomorphisme entre (M,*) et (P(M), °).
Dans un semi-groupe de fonctions, si l'élément neutre n'existe pas, on peut le rajouter sans difficulter, en ajoutant la fonction identité id = (x-->x). Le semi-groupe ainsi étendu reste un semi-groupe de fonctions et devient un monoïde de fonctions.
La cloture d'un ensemble d'opérateurs est une opération fondamentale. Elle constitue le mécanisme de construction des structures et délimite les possibilités de calcul. Elle constitue la pierre de voute des structures constructives.
On se place dans un langage d'opérateurs. Chaque opérateurs du langage se comportent comme des outils de construction, comme des constructeurs, comme des pièces de légo qui s'emboitent. Ce sont des fonctions dont les ensembles de départ et d'arrivé ne sont pas fixés. L'ensemble de départ et d'arrivé comprennent tous les termes exprimables par le langage en cours, et il s'agrandit en cours de route lorsque le langage s'étend. Seul le procéder de calcul de la fonction constructive est fixé. Et par défaut le calcul génère du code libre, de la structure libre.
Tous ce qui n'est pas exprimable ou analysable par le calcul, ne nous intéresse pas de prime abord. Ils le seront plus tard quand un langage pourra les exprimer et qu'un algorithme pourra éventuellement les calculer... Pour les intuitionniste, la preuve est un programme, et l''approche programmative est orienté object comme un retour introspectif sur le langage lui-même. Elle précise la portée des variables. Elle définie des contextes qui sont imbriqués dans différents types de hiérarchies....
Une structure est dite de type fini lorsqu'elle est engendrée par un nombre fini d'opérateurs et où chaque opérateur est d'arités fixé.
On note <a,b,c,*> la clôture de l'ensemble {a,b,c} par l'opération *. C'est l'ensemble des éléments calculables par une combinaisons d'opérateurs * et d'élements a ou b ou c, formant un terme clos de taille finie, appelé terme du langage. Si aucune propriété n'est donnée sur les opérateurs a,b,c,*, alors cela représente une structure libre. La syntaxe est simple, on regroupe entre crochet <a,b,c,*> les différents opérateurs autorisés à se combiner librement et le résultat en est l'ensemble des éléments qui peuvent être produits, c'est à dire l'ensemble sous-jacent de la strucure libre. Pour la nommer on utilisera une affectation telle que M = <a,b,*>. Cette affectation transporte l'ensemble des éléments, mais pas seulement, aussi le langage et la théorie, c'est à dire toute la structure.
Dans une structure libre, chaque terme distinct du langage correspond à un élément distinct de la structure. La structure coïncide exactement avec le langage d'opérateurs. La structure construit une représentation de ses éléments sous forme de terme qui constitue un codage et correspond à une implémentation informatique. l'opérateur binaire * peut être définie de la manière la plus générale comme suit * : (x,y)-->x*y. Et par défaut, elle l'est ainsi. Délors <a,b,*> est le magma libre engendré par a et b. Néanmoins une telle définition est récurcive et il est nécessaire de préciser comment la structure l'interprète. Elle évalue cette récursion jusqu'à obtenir une expression invariante. On aurait pu choisire un second symbôle passif, mais cela complique arbitrairement pour reporter une problèmatique de récursion qui de toute façon aurait réapparue plus tard. Autant tout de suite en poser les premières pierres pour aborder la question de façon centrale sans parti pris, quitte à la revoir après.
Puis les intuitionniste ne considèrent que des théorie d'égalités. Ce sont toutes les théorie écrite dans un langage sans quantificateur existentiel, sans négation et sans inégalité, c'est à dire avec seulement des quantificateurs universels, des variables élémentaires, l'égalité et les opérateurs générateurs de la structure. Lorsque il n'y a pas d'ambiguité on omet d'écrire les quantification universelles qui sont supposées implicites pour toutes nouvelles variables.
Pour les intuitionnistes une structure est le quotient d'une structure libre par une théorie d'égalité. Par exemple voici une structure de semi-groupe :
<a,b,*> / {∀x,∀y,∀z, (x*y)*z = x*(y*z)}
qui s'écrit en supprimant les quantificateurs universels posés comme implicites :
<a,b,*> / {(x*y)*z = x*(y*z)}
Une telle structure anonyme comprend deux partries, son langage qui est une listes d'opérateurs d'arité fixé mis dans un ordre quelconque tel que ici <a,b,*> et qui engendre par composition close l'ensemble des éléments de la structure, et sa théorie d'égalité qui est une liste de propriétés mises dans un ordre quelconque entre crochet et au dénominateur telle que ici {∀x,∀y,∀z, (x*y)*z = x*(y*z)}.
Pour éviter de devoir réécrire la théorie, on utilise un patron tel que Groupe bigène qui précise le type de structure souhaité, suivi de la liste des opérateurs générateurs énumérés dans un ordre précis tel que (*,1,s,a,b). L'ordre est important puisque le patron utilisé identifie ses opérateurs par leur positionnements dans la liste.
G = Groupe bigène (*,1,s,a,b)
G = <1,a,b,s,*> / {∀x,∀y,∀z,, (x*y)*z = x*(y*z), x*1=x, 1*x=x,s(x)*x=1, x*s(x)=1,}
La notation intuitionniste propose ainsi une nomenclature pour les noms de structures (dite de Skolème, c'est à dire lorsque sa théorie est une théorie d'égalité)
Pour insérer le contenue d'un ensemble dans une structure anonyme, on conviendra d'utiliser le symbôle @. Par exemple, avec M = {a,b}, on aura <@M, *> = <a,b,*>. La structure <@M, *> est une structure de type fini si et seulement si M est fini.
De même, pour insérer le contenue d'un ensemble fini dans une structure patronée, on peut placer K comme argument fini-set-gène :
M = Magma fini-set-gène(•, K)
ou dit autrement :
M = <@G,•,>
C'est un magma, une structure libre, engendrée par les éléments de G et par une nouvelle opération •. Le magma a une théorie vide.
L'extension d'une structure M par l'ajout d'opérateurs tel que l'opération +, l'élément a, et la fonction f , s'écrit M[+, a, f], et l'ordre n'a pas d'importance.
Le quotientage d'une structure M par l'ajout d'une propriété à sa théorie telle que {∀x,a*x=x*a} s'écrit M / {∀x,a*x=x*a}. Néanmoins la propriété en question doit s'exprimer dans le langage de la structure.
La concrétisation d'une structure consiste à préciser le calcul d'un de ses opérateurs. Cela s'écrit comme un quotientage particulier. Par exemple la structure M[+, a, f] se concrétise en définissant plus précisément l'opérateur + en par exemple + : (x,y)-->x*y*x. Cela revient au quotientage M[+, a, f] / {x+y=x*y*x}.
Puis on peut combiner ajouts d'opérateurs et ajouts de propriétés en une succession d'extensions et de quotientages, et cela est équivalent à la structure engendrée par l'ensemble des opérateurs évoqués et dont la théorie regroupe l'ensemble des propriétés évoquées.
Un opérateur d'artité variable prend en argument une liste finie d'éléments.
Une structure est dite de type énumérable lorsqu'elle est engendrée par un nombre énumérable d'opérateurs d'arité fixe ou variable.
De la même façon que l'on démontre l'énumérabilité de l'ensemble des suites finies d'entiers, on démontre qu'une structure de type énumérable est énumérable.
Par exemple <@N, •> représente le semi-groupe libre engendré par les entiers. La structure se note Magma set-gène(•,N) et est énumérable. C'est à dire qu'il existe un algorithme exprimable dans le langage de la structure qui énumère tous ses éléments.
Il existe deux façons simples d'énumérer des éléments, à l'aide d'un énumérateur qui est une fonction surjective de N vers l'ensemble que l'on souhaite énumérer, ou bien à l'aide d'une structure de type énumérable dont l'ensemble sous-jacent est l'ensemble que l'on souhaite énumérer.
Une suite énumérable est un programme de taille finie qui calcule les valeurs de la suite en fonction de l'indice qui doit également être énumérable.
Un opérateur d'arité infini prend en argument une suite énumérable infinie d'éléments. Autrement dit il prend en argument la fonction qui énumère la suite énumérable infinie.
---- 29 juin 2014 ----
Le produit représente une opération fonctionnelle, et le monoide en est sa cloture.
Le qualificatif fonctionnel signifie que l'opération consiste en la composition de fonctions unaires.
L'associativité découlant de la loi de composition des fonctions devient redondante et n'a plus besoin d'être mentionnée. En remplaçant ainsi l'associativité par la fonctionnalité, on rend la définition davantage dynamique sans la modifier. On renforce également le coté dynamique en remplacant la propriété de l'opération d'être interne, par la construction de sa cloture.
(M,*) est un monoïde si et seulement si l'opération * est fonctionnelle et si M en est la cloture. C'est à dire s'il vérifie les 2 axiomes suivants :
1) L'opération * est une opération fonctionnelle :
Il existe un choix de fonctions unaires, représenté par l'agitateur P, tel que quelque soit x, y éléments de M, P(x*y) = P(x) ° P(y)2) L'ensemble M est clos par * :
<@M,*> = M
L'opération dans le groupe est donc d'une certaine façon déterminée, c'est l'opération °, de composition de fonctions unaires. Le choix de construction de la structure ne porte donc plus sur l'opération mais sur les fonctions unaires que représentent chaque éléments, c'est à dire sur l'agitateur P qui définie ce choix.
Plus simplement dit, (M,°) est un monoïde de fonctions si et seulement si les éléments de M sont des fonctions et l'opération ° est l'opération de composition de fonction, et M est clos par ° c'est à dire <@M, °> = M.
Même raisonnement qu'avec les monoïdes. Tout groupe est isomorphe à un groupe de fonctions.
Le produit représente une opération fonctionnelle inversible, et le groupe en est sa cloture.
Le qualificatif fonctionnelle signifie que le produit consiste en la composition de fonctions. Et on le note par °.
(G,°) est un groupe de fonctions si et seulement si il vérifie les 2 axiomes suivants :
1) (G,°) est un monoïde de fonctions.
2) L'opération ° est inversible : Quelque soit f appartenant à G, la fonction f est réversible dans G. Autrement dit, il existe un inverseur S agissant sur G tel que quelque soit f appartenant à G nous avons S(f)°f = id, c'est à dire quelque soit l'élément x nous avons S(f)(f(x)) = x.
La réversibilité est ici une notion d'avantage physique, qui pourrait être asymétrique. On ne demande que seul f soit réversible. C'est la faculté de pouvoir revenir en arrière, et cela ne suppose pas que S(f) soit également réversible. Mais la quantification universelle de la propriété va assurer également que S(f) est réversible, c'est à dire que S(S(f))°S(f) = id.
Même raisonnement qu'avec les groupes. Tout groupe commutatif est isomorphe à un groupe commutatif de fonctions.
L'addition représente une opération fonctionnelle, commutative, inversible. Et le groupe commutatif en est sa cloture.
Le qualificatif fonctionnelle signifie que l'addition consiste en la composition de fonctions unaires. On note alors l'addition par °.
(G,°) est un groupe commutatif de fonctions si et seulement si il vérifie les 2 axiomes suivants :
1) (G,°) est un groupe de fonctions
2) L'opération ° est commutative : Quelque soit x, y appartenant à G, nous avons f°g = g°f. L'ordre dans lequel s'enchainent les transformations n'a alors pas d'importance. Pour tous éléments x nous avons f(g(x)) = g(f(x)).
Après l'addition + qui définie le groupe commutatif, on complète la structure en ajoutant le produit qui représente une opération fonctionnelle, inversible, distributive à droite sur l'addition, et distributive à gauche sur l'addition. Et le corps en est sa cloture.
Le qualificatif fonctionnelle signifie que les éléments sont des fonctions unaires, et qu'une des deux opérations, ici le produit, consiste en la composition de fonctions unaires. On note alors cette opération par °.
Mais pour pouvoir affirmer cela, il faut d'abord démontrer que tout corps est isomorphe à un tel corps de fonctions. Cela se fait par construction. On pose un corps (K,+,*) quelconque, et on construit un tel corps de fonctions isomorphe à K noté (P(K),+,°), en faisant opérer le corps K par multiplication à gauche sur lui-même. L'agitateur P est donc défini comme suit. Quelque soit a appartenant à K :
P(a) = (x-->a*x)
Et on note P(K) l'ensemble image regroupant toutes ces fonctions. La composition correspond à la multiplication. Quelque soit a,b appartenants à K nous avons :
P(a)°P(b) = (x-->a*x) ° (x-->b*x) = (x-->a*b*x) = P(a*b)
Ainsi P est un isomorphime de groupe entre (K*,*) et (P(K*),°), où K* désigne le groupe multiplicatif de K comprenant tous les éléments de K à l'exception de l'élément absorbant zéro. Puis on définie une nouvelle opération + sur P(K) comme suit. Quelque soit a,b appartenants à K :
P(a)+P(b) = P(a+b)
Ainsi P est un isomorphime de groupe entre (K,+) et (P(K),+). Et nous constatons dans la structure P(K) la distributivité gauche et droite de ° sur + :
P(a)°(P(b)+P(c)) = P(a)°P(b+c) = P(a*(b+c)) = P(ab+ac) = P(ab)+P(ac) = P(a)°P(b) + P(a)°P(c)
(P(b)+P(c))°P(a) = P(b+c)°P(a) = P((b+c)*a) = P(ba+ca) = P(ba)+P(ca) = P(b)°P(a) + P(c)°P(a)
Ainsi P est un isomorphime de corps entre (K,+,*) et (P(K),+,°).
Noter que la structure nommée (P(K),+,°) a un nom composé P(K), et qu'il faut donc étendre cette faculté, de pouvoir porter une strucure implicite, à des noms composés. Deplus le même symbôle est utilisé dans les deux structures (K,+,*) et (P(K),+,°) pour désigner une opération d'addition distincte. Pour savoir, dans une expression quelconque, à quel opération d'addition on a à faire, on regarde à quelle structure appartiennent les éléments arguments de l'opération. Mais que ce passe-t-il si les deux ensembles sous-jacents ne sont pas disjoints ? Il y a une information implicite, dite de contexte, qui permet de savoir dans quel structure les éléments sont considérés être à l'intant et lieu où apparait l'expression, et là nous entrons dans des paradigmes de programmation, pour un langage qui n'est pas encore de programmation, car aucun algorithme efficient à ce stade n'est implémentable.
Une autre construction du corps de fonctions est possible, une autre conception du corps aussi. Après la multiplication * qui définie un groupe, on complète la structure en ajoutant l'addition qui représente une opération fonctionnelle, commutative, inversible, receptionnant la distributivité à droite de la multtiplication, et receptionnant la distributivité à gauche de la multtiplication. Et le corps en est sa cloture.
Le qualificatif fonctionnelle signifie que l'addition consiste en la composition de fonctions unaires. On note alors l'addition par °.
Mais pour pouvoir affirmer cela, il faut d'abord démontrer que tout corps est isomorphe à un tel corps de fonctions. Cela se fait par construction. On pose un corps (K,+,*) quelconque, et on construit un tel corps de fonctions isomorphe à K noté (A(K),°,*), en faisant opérer le corps K par addition à gauche sur lui-même. L'agitateur A est donc défini comme suit. Quelque soit a appartenant à K :
A(a) = (x-->a + x)
Et on note A(K) l'ensemble image regroupant toutes ces fonctions. La composition correspond à l'addition. Quelque soit a ,b appartenant à K nous avons :
A(a)°A(b) = (x-->a+x) ° (x-->b+x) = (x-->a+b+x) = A(a+b)
Ainsi A est un isomorphime de groupe entre (K,+) et (A(K),°). Puis on définie une nouvelle opération * sur A(K) comme suit. Quelque soit a,b appartenant à K :
A(a)*A(b) = A(a*b)
Ainsi A est un isomorphime de groupe entre (K*,*) et (A(K*),*), où K* désigne le groupe multiplicatif de K comprenant tous les éléments de K à l'exception de l'élément absorbant zéro. Et nous constatons dans la structure A(K) la distributivité gauche et droite de * sur ° :
A(a)*(A(b)°A(c)) = A(a)*A(b+c) = A(a*(b+c)) = A(a*b+a*c) = A(a*b)°A(a*c) = A(a)*A(b) ° A(a)*A(c)
(A(b)°A(c))*A(a) = A(b+c)*A(a) = A((b+c)*a) = A(b*a+c*a) = A(b*a)°A(c*a) = A(b)*A(a) ° A(c)*A(a)
Ainsi A est un isomorphime de corps entre (K,+,*) et (A(K),°,*)
L'approche constructive se différencie de l'approche catégorielle, en mettant l'accent non pas sur l'unicité de la structure pour prouver sa capacité à constituer une référence, mais sur les choix construtifs minimaux nécessaires pour construire cette structure, et qui apporte d'autres valeurs de pertinence pour évaluer sa capacité à constituer une référence.
On modèlise la structure selon la théorie des langages en trois volets, un premier volet dit de données qui décrit l'information portée par la structure, et qui finalement la définie informativement, un second volet dit d'algorithme qui décrit les différentes opérations calculables qui peuvent se faire sur la structure et qui finalement la définie algoritmiquement, et un troisième volet qui décrit les propriétés de la structure et qui finalement la définie axiomatiquement.
Ces trois volets désignes trois langages qui peuvent être perçu également au travers de cette même trilogie. Un langage informatif pour déclarer les éléments, un langage d'algorithmes pour déclarer les constructeurs, et un langage logique pour déclarer les propriétés. Nous allons formaliser ces trois langages qui ont probablement l'essentiel de leur partie commune.
Les principes de construction sont la recherche d'un minimum d'opérateurs générateurs, toujours pris dans leur plus grande généralité, intéropérables et denses (tels que chacune de leur combinaisons soit autorisée et possède une signification distincte), efficaces (tels que leurs évaluations soient rapides, qu'il y ait peu de complexité dans les calculs qu'ils opèrent.) et puissantes (apportant une forte capacité d'expression, capable de décrire un large spectre de propriétés), en avançant de paire avec chacun des trois volets, en s'interdisant tout choix arbitraire et en construisant une intuition qui nous guide certe informelle et échappant au label d'exactitude des sciences hypothétiquo-deductives, dans le but de les implémenter informatiquement, pour en obtenir une grande facilité de programmation. Nous procédons étape par étape, et ce sont les premières étapes les plus importantes car c'est elles toujours qui optent pour des choix arbitraires souvent désastreux et qui nous égard dans une complexité inutile, dans des mauvaise représentation, lourde, éloigné de l'intuition et de la trisymétrie recherchée.
La programmation au sense générale est l'art d'ouvrir des voix de résolutions. Le démonstrateur de théorème devra accumuler un savoir qui constitue une puissance de programmation et de résolution.
Nous emboitons les structures, c'est à dire que nous effectuons un lien à un niveau élevé, mais un lien adaptable comme une multitude d'aiguillages possibles avec passage de paramètres. Les structures se présentent alors comme des croisements composés d'entrés associés à des sorties. Une entré est caractérisé par une liste minimale d'opérateurs d'arités diverses et une liste minimale de propositions relatives à ces opérateurs qui constituent un jeu d'axiomes de la structure traduit dans un langage ne comprenant que ces seuls opérateurs d'entrés. Une sortie se présente de même, mais avec un jeu d'opérateurs beaucoup plus conséquents, maximisé, et un jeu de propositions relatives à ces opérateurs beaucoup plus importants, maximisé, offrant un pouvoir de programmatrion, de traduction et d'implémentation. La structure, quant à elle, va transmettre aux opérateurs de sortie, une implémentation que sont ses algorithmes appliqués sur les opérateurs d'entrés. Ainsi une structure qui possède 3 entrés pour une sortie, propose 3 implémentations différentes de cette sortie, faisant référence à des jeux d'opérateurs d'entrés différents.
L'emboitement de ces structures devient un langage dans lequel on assemble non pas des caractères mais des structures, et cela apporte une puissance de programmation, puisque l'aiguillage de ces entré/sortie sont autant d'implémentations successives possibles exploitant les savoirs faire de ces structures.
On part d'un langage d'opérateurs élémentaire quelconque tel que par exemple L = {a, b, f(.), g(.,.)}, qui permet de désigner les éléments, et qui répond au premier volet, le langage informatif.
Un élément est un terme clos du langage L. Exemple : g(a,f(g(a,b))). Les opérateurs a, b, f, g sont les opérateurs générateurs du langage. Noter que tous les éléments exprimables sont également des opérateurs d'arité zéro.
Un opérateur d'arité 1 appliqué à un élément du langage retourne un élément du langage. Cette opération d'application appelée applicateur est un meta-opérateur que l'on représente par le caractère blanc de séparation ou l'absence de signe. Ainsi f a est égal à f(a). Noter à ce stade que f n'est pas un éléments mais un opérateur d'arité 1. Dans un langage d'opérateurs élémentaire, les seuls éléments sont les opérateurs d'arité zéro qui sont les termes clos du langage L.
On étend cette meta-opération nommée applicateur à tous les opérateurs selon le principe de la currification. Un opérateur h d'arité 3 appliqué à un élément retourne un opérateur d'arité 2 comme suit :
h = (x,y,z)-->h(x,y,z)
h(a) = (x,y)-->h(a,x,y)
h(a,b) = x-->h(a,b,x)
On obtient ainsi un meta-langage. Intuitivement, la composition accumule l'arité des opérateurs et les emboite dans l'ordre de leur apparition. Ainsi la composition g g b f a b est égal à g(g(b,f(a)),b), et g f est égale à quelque chose comme cela g(f(1),2) c'est à dire à l'opérateur (x,y)-->g(f(x),y). Les opérateurs exprimables par ce meta-langage sont dit L-emboitable terminal-clos. Et les parenthèses n'ont plus d'utilitées.
Les élément sont généralisés et comprenent les opérateurs L-emboitable terminal-clos, d'arité zéro et d'arité supérieur à zéro. L'ensemble des parenthèses et virgules peut être enlevé. L'applicateur est associatif et est représenté par le caractère blanc de séparation. Mais ainsi définie l'opération d'application n'est pas close. Il faut donc encore étendre l'ensemble sous-jacent de la structure, rajouter d'autres éléments.
Lorsque l'application n'est pas définie on crée une construction libre qui produit un élément d'un genre particulier tel que a b et a b g. Ces compositions ne s'évaluent pas et constitue la définition de nouveaux éléments, ils possèdent une arité dite de sortie supérieur à 1 (dans l'exemple, respectivement 2 et 3). Ce sont des compositions d'éléments d'arité zéro éventuellement terminées par un élément L-emboitable terminal-clos d'arité supérieur à zéro.
Tous les opérateurs L-emboitable terminal-clos possède une arité de sortie égale à 1, ce qui signifie qu'ils occupent une place s'ils sont mis dans la liste des arguments transmis à un opérateur.
L'arité d'un opérateur est alors composé de deux arités, une arité d'entré et une arité de sortie. Mais lorsqu'on parle de l'arité sans préciser laquelle, il s'agit toujours de l'arité d'entré. Les opérateurs d'arité (u,v) se présentent comme des calculateurs prenant en entré une séquence de u éléments et produisant en sortie une séquence de v éléments.
Le meta-langage que l'on construit en ajoutant l'opération d'applicateur, et en ajoutant les éléments d'arité supérieurà zéro L-emboitable terminal-clos, et les éléments d'arité de sortie supérieur à 1 décrit précédement, aboutie à un langage plus générale et plus simple à la fois, et constitue une adhérence du premier ordre. C'est un meta-langage juste au dessus incluant l'opération d'applicateur cloturé librement. Un mot de ce meta-langage L, se présente exactement comme une composition séquentielle d'opérateurs générateurs. Le meta-langage est exactement le langage de caractère que l'on note L* = {a,b,f,g}*. Voici quelques exemple :
g a f b = g(a,f(b))
a b f g = a b f(g(1,2)) = a b (x,y)-->f(g(x,y))
g b = g(b,1) = x-->g(b,x)
b f a b = b f(a) b
g a b a b f = g(a,b) a b f(1) = g(a,b) a b x-->f(x)
La nature des calculs opérés par les opérateurs évolue également. Elle peut être étendu, car nous ne voulons pas limiter le langage d'algorithme. Un opérateur peut retourner un autre opérateur d'arité de sortie superieur à 1. Par exemple f : x--> a g(x,a), faisant que f(x) = a g(x,a). L'arité de sortie de f est égale à 2. On note f1 et f2 les deux sorties de f. Ainsi f1 et f2 sont deux opérateurs de même arité d'entré que f mais d'arité de sortie égale à 1. Mais en terme de complexité ils sont calculés en parallèle dans f et non en série par f1 puis f2.
Un opérateur peut-il retourner un autre opérateur d'arité d'entré supérieur à 0, non, dans le sense où il n'y a pas d'évaluation à plusieurs étapes. Selon le procédé de currification, un tel opérateur aurait l'arité d'entré finale résultante. Ainsi par exemple une fonction unaire f retournant une fonction unaire comme suit, f : x-->(y-->g(y,x)) est en faite par currification la fonction binaire suivante : f (x,y)--> g(y,x). Autre exemple, si on pose f : x-->(y-->g(x,y)), cela signifit que f(x)=g(x,1), c'est à dire que f(x,y) = g(x,y), et finalement que f = g et on voit que f est d'arité 2.
On insère des places vides que l'on numérote dans l'ordre de leur affectation future à partir de 1. Elles peuvent possèder un même numéro auquel cas il s'agit d'une projection, les deux variables d'entré désignées par le même numéro seront pourvues de la même entré dans l'ordre indiqué par le numéro. Les places vides correspondent aux variables d'entré de l'opérateur désigné par l'expression. Ainsi l'expression f g 3 g 1 2 correspond à l'application f(g(3,g(1,2)) : (x,y,z)-->f(g(z,g(x,y)). Vous aurez remarqué les trois façons de désigner un opérateur. La première appartient au langage L*[. avec relation d'ordre totale], la seconde explicite les parenthèses, et la troisième explicite les parenthèses et les variables muettes. On définie une opération de composition plus générale composant deux tels expressions. Cela permet la composition au sense générale noté °, sans boucle, d'opérateurs d'arité prédéfinie par le langage
Ainsi l'expression f g 1 g 2 1 correspond à l'application f(g(1,g(2,1)) : (x,y)-->f(g(x,g(y,x)). Nous décrivons l'algorithme de composition. La liste des variables d'entré regroupées par numéros d'ordre, est affecté à la liste des variables de sortie de la seconde expression. Ainsi (f g 1 g 2 1)°(a f 1 b) = (f g a g f 1 a b), une égalité en valeur seulement mais pas en complexité. On remarquera qu'une expression tel que g 2 g 3 1 est égale à l'expression g 2 g 3 1 4 5 6... dans la quelle on complète par la suite des variables restantes et en nombre quelconque et dans l'ordre. Et la composition ° est bien associative.
La nature des calculs opérés par les opérateurs peut être étendu encore. Un opérateur peut retourner un opérateur dont l'arité d'entré et de sortie dépend du résultat du calcul. Car nous ne voulons pas limité le langage d'algorithme. On parlera d'arité dépendante. Ainsi f(a) peut être égal à g et f(b) peut être égale à f si sa définition constructible le précise. Ce qui signifie que l'on ne connait pas l'arité du résultat avant d'avoir effectué le calcul. Les opérateurs peuvent avoir une arité dépendant de la valeur de leurs premiers arguments. Il est nécessaire d'évaluer l'opérateur avec son premier argument pour savoir s'il en demande un autre et ainsi de suite. Et pour les arguments de sortie ceux-ci apparaissent dans un ordre quelconque de même après des évaluations partielles de l'opérateur. On vérifiera que l'applicateur ainsi que la composition ° sont toujours associatives. L'ordre d'évaluation est imposé en profondeur d'abord dans le cas d'opérateurs d'arité dépendante.
On peut définir l'applicateur par p : (x,y)-->(x y), c'est un opérateur d'arité dépendante. En effet p(g,x) = y-->g(x,y) et donc si g qui est d'arité 2 est premier argument de p alors p devient d'arité 3 et p(g,x,y) = g(x,y).
Nous avons p(f,a) = f(a). Ce faisant l'applicateur devient un élément du meta-langage.
Les opérateurs dont l'arité est constante sont dit réguliers.
La définition constructive des opérateurs doit respecter l'associativité de l'applicateur et de la composition, garantie par le principe de currification. Par exemple pour f d'arité 1, l'expression f g est égal à l'opérateur f g 1 2 = f(g(1,2)) : (x,y)-->f(g(x,y)). Et l'expression f(a b) est égal à f(a) b qui se note f a b.
L'aspect constructif primant, on peut concevoir des opérateurs définis de tel sorte qu'il ne respecte pas l'associativité de l'applicateur. L'ordre de l'évaluation de l'expression devient alors déterminante, on évalue l'expression de façon paresseuse et selon un sense arbitraire fixé par l'opération. Mais nous n'allons pas ouvrir cette problèmatique maintenant. Nous considérerons des constructeurs toujours réguliers, et respectant l'associativité de l'applicateur. Une autre approche du langage est possible, perçu au travers les propriétés physiques d'une suite de caractères, d'un flux de caractère, beaucoup plus proche de l'informatique, en partant de la séquence de caractères où chaque caractère peut être définie comme un algorithme de calcul à part entière opérant localement relativement à sa position dans la séquence.
On ajoute a notre langage un nombre de variables nommées x, y, z.... Ce nombre est appelé degrés de liberté. Ces variables nommées x, y, z, sont des opérateurs dits universels, c'est à dire susceptibles de prendre toutes valeurs d'éléments exprimables par le langage L, ainsi que par ses extensions futures si le langage est étendu.
Les variables peuvent s'unifier ente elles, il n'y a pas de restriction d'affectation, chaque variable peut être égale à une autre ou à n'importe quel élément exprimable par le langage L.
A ce stade le langage peut exprimer des "images" tel que g(g(y,x),g(a,x)) qui parcourt un ensemble image lorsque x et y parcourent l'ensemble des éléments exprimables par L. Et cela s'écrit également par : g g y x g a x
Néanmoins cette définition de la variable universelle est trop vaste. Elle inclue les compositions séquentielles d'éléments d'arité zéro qui ne sont pas proches de l'intuition corpusculaire, et qui pose un problème d'efficacité dans l'opération d'unification. En effet si x y = a b a b, il y a 5 solutions {(x=ε,y=abab), (x=a,y=bab), (x=ab,y=ab), (x=aba,y=b), (x=abab,y=ε)}où ε désigne la composition vide si elle existe. L'unification n'est plus unique, et le fait qu'elle ne soit plus déterminée, augmente concidérablement la complexité des calculs basés sur cette unification..
Aussi nous nous restreignons à une notion d'universalité élémentaire. Les opérateurs dits universels auront comme contrainte d'avoir une arité (0,1). En d'autres termes, l'opérateur universel x est susceptibles de prendre toutes valeurs d'éléments exprimables par le langage élémentaire L, ainsi que par ses extensions futures si le langage est étendu.
/***** Voir la notion plus générale d'universalité d'arité de sortie égale à 1.
*****/
Les variables peuvent s'unifier ente elles, il n'y a pas de restriction d'affectation, chaque variable peut être égale à une autre ou à n'importe quel élément d'arité (0,1) exprimables par L.
A ce stade le langage peut exprimer un élément image tel que g(g(y,x),g(a,x)) qui parcourt un ensemble image lorsque x et y parcourent l'ensemble des éléments d'arité (0,1) exprimables par L. Et cela s'écrit également par : g g y x g a x
/***** Voir les possible représentations de l'élément image lorsque x, y, z sont indiscernables, c'est à dire à permutation près, ou bien lorsque seul l'ordre des variables est connue, dans ce cas l'image est représenté par g g 2 1 g a 1
Ce langage est dit du premier ordre car il n'y a qu'un seul type de variable universelle, et l'unification y est unique.
Intuitivement l'opérateur prend en argument une séquence d'éléments et retourne une séquence d'éléments, et correspond à une unité de calcul. La séquence correspond à l'énumération qui constitue une opération fondamentale en programmation. D'où l'importance du concept de séquence d'éléments. (f,b,x) est une séquence, (f,(b,x)) n'en n'est pas une, ou plus exactement, nous avons les simplification suivantes :
(f,(b,x)) = (f,b,x)
(a) = a
La séquence est toujours ramené au premier niveau, il n'y a pas d'information d'emboitement. La séquence est une énumération finie d'éléments, une pile d'éléments.
On ajoute au langage la faculté d'exprimer les séquences, c'est à dire la capacité de désigner une liste d'opérateurs qui ne sont pas appliqué l'un sur le suivant, mais énumérés. Ces séquences constituent de nouveaux éléments. Cela correspond à ajouter l'opérateur d'énumération, appelé énumérateur, et qui est représenté par une virgule, et qui possède une arité 2, et qui est associatif, et de convenir de quelques règles de composition garantissant l'associativité de l'applicateur et de l'énumérateur.
Un opérateur appliqué à une séquence d'arguments de même taille que son arité va retourner un nouvel opérateur avec une arité égale à la somme des arités de ses arguments comme suit :
g(f,f) = g(f(1),f(2)) = (x,y)-->g(f(x),f(y))
Un opérateur appliqué à une séquence d'arguments de taille plus petite que son arité va retourner un nouvel opérateur avec une arité égale à la somme des arités de ses arguments plus celle de l'opérateur moins la taille de la séquence argument :
h = h(1,2,3) = (x,y,z)-->h(x,y,z)
h(f,a) = h(f(1),a,2) = ((x,y)-->h(f(x),a,y))
h(f,a) b a = h(f(1),a,2) b a = h(f(b),a,a) (on suppose ici que f(b) est d'arité zéro)
La liste des entrés de l'opérateur résultant est constitué selon un ordre précis, les entrés des arguments sont placées avant les entrés non pourvues, sans quoi l'associativité de l'applicateur n'est plus respecté.
Un opérateur appliqué à une séquence d'arguments de taille plus grande que son arité va retourner une séquence composée de l'opérateur appliqué aux premiers arguments suivit des autres arguments en trops :
f(a,b) = f(a),b
f(f,f) = f(f), f = x-->f(f(x)) , x-->f(x)
a (a,b) = (a,a,b)
L'autre hypothèse de la troncation n'est pas possible car f a b = f(a) b = (f(a),b).
L'opérateur virgule possède la priorité la plus basse. Et les parenthèses ne jouent alors qu'un rôle de priorisation.
La nature des opérateurs évolue également. Un opérateur retourne à présent une séquence d'éléments. L'arité de l'opérateur est alors composée de deux chiffres positifs libre, l'arité d'entré et l'arité de sortie. C'était déjà le cas avant en partie, et cela se complète. Ainsi le terme a b a g a d'arité (1,4) est égale au terme (a, b, a, g(a,1)).
Le meta-langage se complète ainsi selon une logique polonaise empilant les entrés et les sorties, assemblant les unité de calcul que sont les opérateurs, tantôt en composition série (applicateur), tantôt en parallèle (énumérateur). La séquence d'opérateurs devient un opérateur, ainsi (g,f(a),f) correspond à l'opérateur (x,y,z) --> (g(x,y),f(a),f(z)). Son arité d'entré est égale à la sommes des arités d'entré, et son arité de sortie est égale à la somme des arités de sortie plus la taille de la séquence. L'applicateur, noté par le caractère blanc de séparation ou l'absence de signe, compose deux séquences d'opérateurs pour en produire une autre selon la logique polonaise d'empilement. Voici quelques exemples :
(f,f) a = (f(1),f(2)) a = (f(a),f(1)) = (f(a),f)
(a,b) f = (a,b) f(1) = (a,b,f(1)) = (a,b,f)
(f,g) (a,b,a,b) = (f(1),g(2,3)) (a,b,a,b) = (f(a), g(b,a), b) (On suppose ici que f(a) et g(b,a) sont d'arité 0.)
(a,b) (a,b) = (a,b,a,b)f(f,a) = f(1) (f(1),a) = (f(f(1)), a)
/***** vérifier la cohérence si f(1) = g(1,2) alors f f a = g(f,a) mais f (f,a) = (f(f),a) = (g(f,1),a)(f,g) (f,f,a,b) = (f(1),g(2,3)) (f(1),f(2),a,b) = (f(f(1)),g(f(2),a),b)
/***** à vérifier
a b a = (a,b,a)
a f (a,b) = (a,f(a),b)
f f f a = f(f(f(a))) (Si f n'est pas définie)
(f,f,f)a = (f(a),f,f)
La virgule est associatives. Les parenthèses ne jouent qu'un rôle de priorisation. L'applicateur est associatif.
A ce stade le langage peut exprimer des séquences d'éléments, des séquences images, qui sont constitués d'images liées entre-elles tel que (y,g x,f y), et qui parcourent un ensemble image à plusieurs dimensions lorsque x, y, z .... parcourt l'ensemble des éléments d'arité zéro exprimables par L. Et cela s'écrit également par : (y, u-->g(x,u), f(y)) = (y, g(x,1), f(y)).
/***** Si on vouler numéroter les variables présentes (toujours à partir de 1) pour ne les distinguer que selon un ordre connue, il faudrait utilisé une seconde numérotation, puisque une première numérotation est utilisée pour définir les fonctions (opérateurs), leurs arguments étant ordonnés.
Néanmoins le langage ainsi proposé reste faible, il lui manque la capacité de factoriser, de distribuer, d'opérer des algorithmes parallèles de composition. Nous allons ajouter l'opération de composition parallèle, que l'on décompose en deux opérations, l'une unaire dite de parallélisation et portant sur une séquences, l'autre binaire qui est l'applicateur. L'opération unaire consiste en la parallélisation des entrés d'une séquence d'opérateurs. Cette opération est une modification physique. Elle présupose que l'ordre des arguments d'entré des opérateurs est fondamentale, et qu'il n'est donc pas arbitraire de les parallèliser.
L'opération de parallèlisation des entrés d'une séquence, est noté par le symbôle | remplaçant les parenthèses de la séquence. Elle prend comme argument une séquences d'opérateur et retourne la même séquence mais dans laquel les entrés sont parallélisés. Par exemple :
Ce qui s'écrit :
g(h,k) = g(h(1,2),k(3,4))
g|h,k| = g(h(1,2),k(1,2))
La parallélisation se généralise à toutes les séquences. Ainsi |f,g,a,f,g| = (f(1),g(1,2),a,f(1),g(1,2)). La composition parallèle notée * se généralise ainsi par une apparante troncation, les opérateurs d'arité plus petite ignoreront les arguments supplémentaires pris par leur voisins..Par exemple :
(f,g)*(a,b,a) = |f,g|(a,b,a) = (f(1),g(1,2)) (a,b,a) = (f(a),g(a,b),a)
(f,g)(a,b,a) = (f(1),g(2,3)) (a,b,a) = (f(a),g(b,a))
Cette opération est associative.
Une autre approche du langage est possible, perçu au travers les propriétés physiques d'une suite de places tels des mémoires, beaucoup plus proche de l'informatique. Il faut trouver les opérations génératrices agissant sur une séquences de caractères, les plus perspicaces c'est à dire qui permettent de désigner les opérations intéressantes avec un minimum de complexité expressive et algorithmique. C'est une question physique sur les séquences et leurs interactions possibles. En avançant en concomitance, représentation de l'algorithme d'un opérateur pour l'executer, et représentation de l'opérateur pour le désigner, et représentation des propriété de l'opérateur pour l'axiomatiser.
On ajoute l'opérateur de construction d'opérateur --> (appelé également opérateur d'unification) qui prend non pas une séquence d'arguments mais deux séquences d'arguments, et qui définie l'opérateur qui transforme les éléments unifiables à la première séquence, en la seconde. Ainsi l'opérateur (a x, f(y))-->(f(x),y) appliqué à l'élément (a, f(a),f(b)) retourne (f(f(a)),b).
Si l'argument n'est pas unifiable, l'opérateur retourne FAIL une valeur particulière qu'est l'élément FAIL, et que l'on ajoute à la structure pour cloturer l'opérateur d'unification. On ajoute donc l'élément FAIL d'arité (0,1) au langage qui devient L = {a, b, f(.), g(.,.), FAIL}
Ce langage permet de définir des littéraux, propriétés atomiques, qui ne nécessitent aucun connecteur logique (et, ou, non...). Voici quelques exemples de littéraux. On notera au passage que l'on priorise les opérateurs afin de na pas utiliser trop de parenthèses, l'opérateur + est posé prioritaire sur l'opérateur =.
f(x+b)+x
x+y = y+x
f(a+x) = x+f(a)
(f(a)=b) = a
f(a=x) = (b=x)
Nous n'avons pas fait de distinction entre la valeur logique et la valeur élémentaire. Ainsi l'opérateur = retourne 1 ou 0 selon que l'égalité est constaté ou non. L'élément 1 représente la valeur logique vrai, et l'élément 0 la valeur logique faux. Le choix semble arbitraire, mais nous verrons comment les structures admettent des représentations de références incluses les unes dans les autres et ceci de manière canonique.
Reste à définir ce que signifie une expression logique retournant un élément différent de 1 ou 0 ? Mais nous n'allons pas ouvrir cette problèmatique maintenant. Nous considérerons des littéraux toujours égaux à 1 ou 0.
Les littéraux peuvent se combiner à l'aide de connecteur logique pour former des propriétés plus générales appelées théories. Et à chaque théorie correspond une structure.
Le littéral est une expression logique, ou propriété dite atomique car elle ne possède pas de connecteur logique (et, ou, non) et ne peut donc pas être décomposé.
Déja plusieurs structures admettent comme théorie un simple littéral. Par exemple le monoïde possède comme théorie x*(y*z) = (x*y)*z. Mais pour être précis, il faut faire une déclaration de structure, appelé présentation. La présentation déclare en même temp le langage de la structure, et sa théories exprimées dans son langage.
(M,* / x*(y*z) = (x*y)*z)
Et si la théorie se suffit à elle même alors il n'y a pas besoin de patron et la structure peut être anonyme.
<@M,* / x*(y*z) = (x*y)*z>
Si on ajoute un axiome structurel supplémentaire qui affirme que la structure est engendré par 2 générateurs par exemple. Alors la présentation anonyme devient :
<a,b,* / x*(y*z) = (x*y)*z>
La structure est anonyme mais ses générateurs a, b, ainsi que son opération *, sont nommés. C'est le langage de la structure. Et ce langage a une portée, dans la structure (hierarchie structurelle) et dans des déclarations (hierarchie déclarative) selon une syntaxe qui reste à préciser.
Le volet concernant les algorithmes est absent.
Un groupe engendré par 2 éléments admet comme présentation :
<a,b,*, S / x*(y*z) = (x*y)*z et y*x*S(x) = y>
Mais l'opérateur ° n'est pas un opérateur comme les autres, il est prédéfinie, c'est la composition de fonction unaire, que l'on peut définir comme suit :
° : (f,x)--> f(x)
Mais f est un élément du second ordre.
C'est la partie commune
Et on construit les 3 méta-langages, selon deux buts, l'un pour déclarer les constructeurs, l'autre pour construire les propositions, faisant apparaître les deux volets, algorithmes et propriétés, et qui se concrétise dans les deux facultés emblèmatiques que sont l'énumérable et le décidable.
Le littéral est une expression logique, ou propriété dite atomique car elle ne possède pas de connecteur logique (et, ou, non) et ne peut donc pas être décomposé. Mais déja plusieurs structures admettent comme théorie un simple littéral. Par exemple le groupe de fonctions cyclique à 3 élements possède comme théorie f(f(f(x))) = x. Mais pour être précis, il faut donner la déclaration de la structure qui déclare en même temp un langage, un langage qui coïncide avec la structure tant que la structure reste libre. Et il convient d'ajouter à la présentation de la structure sa théorie. Et si la théorie se suffit à elle même alors il n'y a pas besoin de patron et la structure peut être anonyme :
< f, ° / f(f(f(x)))=x >
Mais l'opérateur ° n'est pas un opérateur comme les autres, il est prédéfinie, c'est la composition de fonction unaire, que l'on peut définir comme suit :
° : (f,x)--> f(x)
Mais f est un élément du second ordre.
L'extension de monoïde (M,°)[u] = <@M, u, ° > est le monoïde M avec un générateur de plus noté X ne possèdant auncune règle restrictives. L'ensemble des prorpiétés du premier ordre exprimable