On cherche un langage pour exprimer à la fois, données et programmes. L'élaboration d'un programme est généralement guidée par un but qu'est la résolution d'un problème, et donc une recherche de solutions. Un des algorithmes parmi les plus simples consiste à chercher au hasard les solutions et à les mémoriser. C'est l'algorithme cumulatif, aussi appelé algorithme Shadok.
L'idée est de résoudre `F(X)=0` ou plus exactement d'acquérir des connaissances sur l'ensemble `{X "/" F(X)"="0}` lorsque qu'il y a peu de solutions, en procédant, selon la logique Shadok, à des essais au hasard et en accumulant les rares essais qui satisfont l'équation.
Le calcul, appelé fonction, `F` est défini d'une certaine façon. Et appliquée à une données `X`, il peut donner une réponse en un temps fini, on bien ne jamais s'arrêter et donc ne jamais donner de réponse. La donnée `X` est définie d'une autre façon.
La donnée comme la fonction est de quantité finie d'information et donc peut être décomposés et mémorisée dans un nombre fini de bits, en un nombre fini de booléens. On peut les représenter par des listes de booléens.
`X` peut être concidéré comme une liste de booléens. De même pour `F` à ceci près qu'il faut convenir d'un système de construction de `F` transformant une donnée passive telle qu'une liste de booléens, en une fonction calculable, un processus de calcul. Et la difficulté reste de choisir un système suffisament générale pour satisfaire à notre exigence d'universalité. Cela est possible grâce à la machine de Turing, et à l'opinion de Church, qui affirme que tout ce qui est calculable peut se calculer à l'aide d'une machine de Turing.
On décompose la fonction afin qu'elle devienne booléenne. Le problème se reformule alors différemment avec une fonction booléenne `F` qui prend maintenant en entré une liste de booléens de taille variable, et retourne en sortie un booléen valant `1` si la contrainte est satisfaite et `0` sinon.
`F` est une fonction booléenne d'arité variable. L'équation devient alors l'équation booléenne `F(X)=1`, et est équivalente à l'expression logique `F(X)`. L'ensemble sur lequel nous voulons acquérir des connaissance est `{X "/" F(X)"="1}` noté également `{X "/" F(X)}`.
Les définition des données `X` sont de type énumératif, tandis que les définitions des fonctions `F` sont de type programmatif, faisant que l'application de `F` sur `X` correspond à un calcul `F(X)` complètement mécaniquement défini.
Il existe une conversion par défaut du type énumératif en type programmatif qui consiste à transformer une liste de booléens en une fonction énumérant ces booléens. Par exemple considérons `X = (1,1,0,0,0,1,0)`, sa conversion en type programmatif produira la fonction qui, sur l'entré `n` écrit en binaire avec l'endianess big-endian et autant de `0` devant que l'on veut, retournera le `n`-ième booléen de la liste `X`, et pour tout autre valeur retournera `0`.
On commence par faire une simplification majeur. On ne s'intéresse qu'aux fonctions booléenne d'arité fixe, c'est à dire opérant sur des données de taille constante. Ce choix est inspiré d'une constatation, que dans un langage d'opérateurs, un opérateur d'arité variable peut toujours être remplacé par deux opérateurs binaires. Mais ce choix appliqué aux fonctions booléennes, du fait de la finitiude des booléens, qu'il y en a que deux, `0` et `1`, va changer la nature du problème en le simplifiant considérablement..
En effet, la problèmatique de la puissance de calcul d'une machine de Turing ne se pose plus. Car pour chaque valeur de `n`, il n'existe qu'un nombre fini de fonctions booléennes `n`-aire. Il en existe exactement `2^n`. Et ces fonctions sont évidement programmables. Elles sont programmables en n'utilisant qu'un seul opérateur booléen binaire, l'opérateur NAND (le non-et) ou l'opérateur NOR (le non-ou), puisque ceux-ci individuellement engendrent tous les opérateurs booléens d'arité fixe.
On fixe préalablement une valeur de `n`. L'algorithme Shadock comprend :
La taille de `X` est constante et égale à `n`, faisant que `X` est mémorisé dans un mot de `n` bits.
Par contre la taille de `F` est variable puisque c'est un programme. On pose une structure de données correspondant à un langage de calcul, un langage de programmation, pour pouvoir écrire et mémoriser `F`.
Vous aurez remarqué que l'on utilise le terme de fonction et d'opérateur davantage dans le sens physique que mathématique, c'est à dire comme des programmes ayant une complexité de définition dans le langage de calcul choisi, et ayant une complexité de calcul propre.
On recherche un langage de calcul ou langage de programmation, qui soit dense. C'est à dire tel qu'une expression du langage construite au hasard désigne autant que possible un programme valide syntaxiquement, et tel que deux expressions distinctes désignent autant que possible deux programmes distincts sémantiquement, c'est à dire procédant à des de calculs différents.
La donnée atomique est le booléen. La fonction atomique est une fonction booléennes binaires, qui est soit le NAND (le non-et) ou soit le NOR (le non-ou), qui ont chacune la facultés d'engendrer tous les opérateurs booléens d'arité fixe et donc d'engendrer toutes les fonctions bouléennes `n`-aire (pour tout `n` fixe).
Lorsque l'on cherchera a minimiser la complexité de calcul, nous serons amené à considérer des fonctions à plusieurs sorties, permettant ainsi le calcul parallèle.
On note la fonction par `F`, et on note le `n`-uplet de booléens par `X`. Le nombre `n` est un paramètre préalablement fixé désignant la taille de `X`. Pour l'exemple `n"="5`.
Le `n`-uplet de booléens `X` se décompose comme suit :
`X = ( X[0], X[1], X[2], X[3],X[4] )`
`X[i]` est une mémoire contenant un booléen, et l'indice `i` désigne l'adresse relative de cette mémoire. `i` varie de 0 à n-1. Pour alléger l'écriture on notera `X[i]` simplement par `X_i`, ainsi nous avons :
`X = (X_0,X_1,X_2,X_3,X_4)`
Ces `n` mémoires constituent `n` variables booléennes qui correspondent aux `n` entrés dans la fonction `F`. Chacune de ces variables correspond à un élément générateur ajoutés au langage de calcul. Le langage comprend ces n noms de variables (opérateurs d'arité zéro) et comprend des opérateurs booléens capables d'engendrer tous les opérateurs booléans. Ce langage de calcul ou langage de programmation possède déjà la puissance de calcule totale des fonctions booléennes d'arité `n` fixe.
Puis ce langage de calcul ou langage de programmation est augmenté d'autres opérateurs afin qu'il permettent de réduire la complexité des programmes. Et au départ il n'y a pas de distinction entre complexité de définition (complexité de Kolmogorov) dans le langage de calcul choisi, et complexité de calcul propre. La distinction viendra lorsqu'on ajoutera au langage des opérateurs itératifs engendrant plusieurs opérations de calculs.
L'extension du langage permet de définir des programmes produisant le même résulat avec une complexité de définition plus petite, et aussi de définir des programmmes produisant le même résultat avec une complexité de calcul plus petite.
On utilise l'opérateur booléen binaire NAND noté également `"¬et(.,.)"` qui est commutatif et non associatif, et qui engendre tous les opérateurs booléens d'arité fixe. Les programmes sont alors les termes clos du langage suivant :
`{X_0,X_1,X_2,X_3,X_4,"¬et(.,.)"}`
On utilise les caractères `a,b,c,d,e` au lieu des symboles `X_0,X_1,X_2,X_3,X_4` et le caractère `"∗"` au lieu du symbole `"¬et"`. Les programmes sont alors les termes clos du langage suivant :
`{a,b,c,d,e,"∗"}`
Le langage d'opérateurs se transforme en un langage de caractères en mettant en oeuvre la logique polonaise. Les parenthèses et les virgules sont simplement enlevées. Le terme clos ci-dessous se transforme en une chaine de caractères d'alphabet `{a, b, c, d, e, "∗"}`. Le programme devient une chaîne de caractère. Voici un programme mis sous forme de chaine de caractères :
`"¬et"(X_1,"¬et"(X_2,X_3))`
`"∗"(a,"∗"(b,c))`
`"∗"a"∗"bc`
L'évaluation se fait avec une pile de même taille `(P_0,P_1,P_2,P_3,P_4), i"="0` et en lisant la chaîne de caractère à interpréter à l'envers c'est à dire de droite à gauche. Par exemple `"∗"a"∗"bc` :
`i` : nombre d'éléments dans la pile
`P_j` : élément à la `j`-ième place dans la pile sachant que l'on commence par la place n°`0`.
On réserve une pile de même taille `(P_0,P_1,P_2,P_3,P_4), i"="0`
On lit `c` et on l'empile : `P_i"="c, i"="i"+"1`
On lit `b` et on l'empile : `P_i"="b, i"="i"+"1`
On lit `∗` et on effectue le NAND : `i"="i"-"1, P_(i-1)"=¬et"(P_(i-1),P_i)`
On lit `a` et on l'empile : `P_i"=", i"="i"+"1`
On lit `∗` et on effectue le nand : `i"="i"-"1, P_(i-1)"=¬et"(P_(i-1),P_i)`
On retourne le résultat `P_0`.
On va utiliser les symbôles `0` et `1` pour désigner l'élément neutre de l'addition et l'élément neutre de la multiplication. Et donc on va utiliser d'autre symbole pour désigner les booléens, `"vrai"` et `" faux"`.
Il y a deux façons possibles de définir sur les booléens `B={"faux", "vrai"}` une structure de corps `({"faux", "vrai"},"+","∗")`.
En notation programmative, le corps se note `B = ({"faux", "vrai"},"+", 0,"-" ,"∗",1,"÷")` où les arguments sont énumérés dans un ordre précis :
Dans la première façon, le `0` correspond à la valeur logique `"faux"`, le `1` correspond à la valeur logique `"vrai"`. L'addition correspond à l'opérateur `"⇎"` appelé le "ou exclusif". Le produit correspond à l'opérateur `"et"`.
( ) ( ) `x"∗"y = x "et" y`
`x"+"y = "¬"(x"⇔"y)`
`"¬"x = x"+"1`
`"id"` désigne l'opérateur unaire identité `x"↦"x`
Dans la seconde façon, Le `0` correspond à la valeur logique `"vrai"`. Le `1` correspond à la valeur logique `"faux"`. L'addition correspond à l'opérateur `"⇔"`. Le produit correspond à l'opérateur `"ou"`.
( ) ( ) `x"∗"y = x "ou" y`
`x"+"y = x"⇔"y`
`"¬"x = x"+"1`
Les variables booléennes d'entrée `(X_0,X_1,X_2,X_3,X_4)` sont ajoutées au langage de calcul et constitue une extension élémentaire de la structure de corps `B` pour former la structure d'anneau de polynômes `B[X_0,X_1,X_2,X_3,X_4]`.
On définie plusieurs structures :
`NN(X_0,X_1,X_2,X_3,X_4)` L'ensemble des polynômes à `5` variables et à coefficient dans `NN`.
`B(X_0,X_1,X_2,X_3,X_4)` L'ensemble des polynômes à `5` variables et à coefficient dans `B`.
L'anneau de polynômes `B[X_0,X_1,X_2,X_3,X_4]`.
et ces trois structures sont emboitées :
`B(X_0,X_1,X_2,X_3,X_4) = (NN[X_0,X_1,X_2,X_3,X_4])/(x"+"x"="0)`
`B[X_0,X_1,X_2,X_3,X_4] = (B(X_0,X_1,X_2,X_3,X_4))/(x"∗"x"="x)`
---- 25 mai 2019 ----
L'anneau de polynômes `B[X_0,X_1,X_2,X_3,X_4]` est l'ensemble des polynômes à `5` variables et à coefficient dans `B`. Cela incorpore la première règle concernant la caractéristique 2 du corps : `x"+"x"="0`, et l'opposé de `x` est égale à `x`.
Ce corps est de caractéristique `2` c'est à dire que n ous avons : `x"∗"x"="x`, `x"+"x"="0`, et l'opposé ainsi que l'inverse de `x` sont égaux à `x`.
Le programme `F` est un polynôme à `n` variables dans `B` et admet donc une forme normale que l'on obtient en développant à l'aide des propriétés supplémentaires `x"+"x"="0` et `x"∗"x"="x`. Notez que ce développement est d'une complexité de calcul maximale en `2^n`.
On utilise le symbôle `=` pour spécifer une égalité dans l'ensemble des booléens `B`. Et on utilise le symbôle `"≡"` pour spécifer une égalité dans l'ensemble des polynômes `B[X_0,X_1,X_2,X_3,X_4]`.
Un polynôme `F` est totologique lorsque le programme `F` donne un résultat toujours égale à `1`, et dans ce cas, le polynôme de `F` mis sous forme normale est identique au polynôme `1`, ce qui s'écrit comme suit :
`∀X, F(X) = 1 <=> F ≡ 1`
Le polynôme`F` est contradictoire lorsque le programme `F` donne un résultat toujours égale à `0`, et dans ce cas, le polynôme de `F` mis sous forme normale est identique au polynôme `0`, ce qui s'écrit comme suit :
`∀X, F(X) = 0 <=> F ≡ 0`
Du fait de la simplification `x"∗"x"="x`, un monôme correspond à un sous-ensemble de `{X_0,X_1,X_2,X_3,X_4}` et possède donc une représentation unique sur un `5`-uplet de booléens, le i-ième booléen désignant la présence de la i-ième variable dans le monôme.
Un polynôme est une suite de tels monômes triés dans l'ordre (selon l'endianess big-endian). Sa représentation est alors unique et est appelée sa forme normale.
Deux polynômes de forme normale distincte représentent deux programmes calculant des fonctions distinctes.
Deux programmes calculant la même fonction se développent nécessairement en un même polynôme sous forme normal.
L'implémentation du programme `F` consiste alors en une pile de mots de `n` bits triés.
Le polynôme dans certain cas peut se factoriser en partie ou totalement, et la complexité de définition et de calcul s'en trouve réduite. Par exemple considérons le polynôme sont forme normale `X_1"∗"X_2+X_1"∗"X_3+X_2"∗"X_3` de complexité de définition et de calcul égale à `13`. Ce sont les `13` symboles de la définition et les `13` calculs correspondant au `13` symboles. Ce polynome se factorise en `X_1"∗"(X_2+X_3)+X_2"∗"X_3` de complexité de définition et de calcul égale à `9`.
---- 20 mai 2019 ----
L'addition de deux n-uplet se programme avec les opérateurs logiques binaires.
Soit deux n-uplet X et Y, on calcule le n-uplet Z = X + Y en calculant l'addition bit à bit et en transmettant à chaque fois une éventuelle retenue. Ainsi nous avons :
Z0 = X0 w Y0
Z1 = if (X0 et Y0) then ¬(X1 w Y1) else (X1 w Y1)
Nous avons utilisé de façon naturelle une instruction if-then-else. Cette instruction est une opération logique ternaire qui se décompose en opérations logiques binaires de base. Le programme if a then b else 1 correspond au calcul logique (a=>b) et (¬a=>c). Noter alors que le programme if a then b else 1 possède une complexité de calcul plus petite que le calcul (a=>b) et (¬a=>c).
------- 20/06/2012 --------
Deux voix s'ouvrent pour perfectionner le langage et augmenter ainsi sa puissance d'expression, c'est à dire sa capacité à décrire les calculs avec une complexité de Kolmogorov plus petite et aussi avec des complexités de calcul plus petite. Soit on crée d'avantage de structure, de données structurées, d'opérations sur ces données et de méta-opérations sur ces opérartions comme autant de nouveaux modes de composition et qui constitue un embryon de la deuxième voie. Ou bien on force tout de suite à aller plus loin en utilisant un second langage, qui décrit un calcul produisant une expression du premier langage, qui décrit à son tours un calcul calculant F(X).
Le langage décrit un programme, et d'une manière plus
générale il décrit une machine qui va opérer un calcul. Le
méta-langage décrit une machine qui construira une autre machine et qui
va à son tours opérer un calcul.
La variable booléenne est caractérisée par son adresse relative, un
entier compris entre
0 et 30. Cela tient dans un octet (ou caractère). Le dernier bit de l'octet (bit de
signe) peut être
utilisé pour déterminer si c'est une variable d'entré ou un opérateur
constant.
Dés lors le caractère (l'octet) devient l'alphabet du langage, et permet de déterminer
une variable d'entré parmis 128 variables ou bien un opérateur constant
parmis
128 opérateurs. Le langage n'écrit que des références à des
opérateurs. L'opérateur proprement dit est définie ailleurs, dans un autre langage adapté pour
l'interpretation ou la
génération de code C qui sera alors compilé de façon groupé.
Un programme est une liste d'opérateurs constants
et de variables qui doit être close selon l'arité des opérateurs
invoqués.
Le langage d'opérateurs se transforme en langage de caractères en mettant en oeuvre la logique polonaise. Les parenthèses et les virgules sont simplement enlevées. Le programme devient une chaîne de caractère.
On ajoute un caractère nul supplémentaire à la fin de la chaîne de
caractères, jouant le rôle d'un opérateur de bas niveau pour indiquer
la fin du programme.
L'évaluation se fait simplement avec une pile de même taille
{[P0, P1, P2, P3,...], i=0} et en lisant la chaîne de caractère à interpréter de
droite à gauche (voir §10.1).
Prenons le langage suivant :
{f(.), g(.,.), h(.,.), k(.,.), u, v, x, y}
Le langage est perçu ici comme une implémentation informatique qui agit physiquement sur une séquences d'octects, et sémentiquement sur un opérateur selon trois modes concomittant : pour l'executer, le désigner et l'axiomatiser.
Nous mettons en oeuvre la currification. Cela permet de composer un opérateur avec moins d'arguments que ce qui est précisé dans sa définition :
f = x->f(x)
g = (x,y)->g(x,y)
g(a) = y->g(a,y)
g(f) = (x,y)->g(f(x),y)
g(g) = (x,y,z)->g(g(x,y),z)
Noter qu'il n'y a pas ici de différence entre l'application d'une fonction unaire sur un élément et la composition de deux fonctions unaires. Ces deux méta-opérations sont notées pareillement, à l'aide du symbole °, ou par l'absence de symbole en juxtaposant simplements les arguments :
L'associativité de la compositions et la currification permet de mettre en oeuvre la logique polonaise, un langage facile à interpréter, qui n'utilise ni parenthèse ni méta-opérateur, et seulement la déclaration du langage qui précise l'arité de chaque opérateur, et la simple juxtaposition des opérateurs dans un programme. Deux stratégies sont possibles : Les opérateurs s'empilent dans l'ordre des places libres en profondeur d'abord, ou à même niveau d'abord :
En profondeur d'abord : gfxgyu = g(f(x),g(y,u))
A même niveau d'abord : gfxgyu = g(f,x)(g)(yu) = g(f(g(y,u),x)
Une autre approche consiste à évaluer
le méta-opérateur de composition °
selon deux stratégies possibles. L'évaluation de la composition
peut se faire de gauche à droite, ou de droite à gauche en utilisant
les séquences d'opérateurs terminal-closes et le mode harmonique de la
composition
De gauche à droite :
g°f°x°g°y°u = ((((g°f)°x)°g)°y)°u
= (((g(f)°x)°g)°y)°u
= ((g(f(x))°g)°y)°u
= (g(f(x),g)°y)°u
= g(f(x),g(y))°u
= g(f(x),g(y,u))
De droite à gauche :
g°f°x°g°y°u = g°(f°(x°(g°(y°u))))
= g°(f°(x°(g°(y,u))))
= g°(f°(x°(g(y,u))))
= g°(f°(x,g(y,u)))
= g°(f(x),g(y,u)
= g(f(x),g(y,u))
Les deux stratégies aboutissent au même résultat en profondeur
d'abord,
mais l'évaluation
de droite à gauche nécessite d'utiliser un concept vu plus loin que
sont les séquences terminale-closes définie par composition grace au
mode harmonique. La
composition d'un opérateur zéro-aire avec
un autre opérateur est alors définie égale dans ce cas à leur séquence
:
x°f = x,f. Mais il s'agit là d'un choix dont nous discuterons plus loin
et que
nous ne faisons pas à premier abord. Le mode est non-harmonique, la
composition d'un opérateur avec un nombre d'arguments plus grand que
son arité se traduit par une perte d'information comme dans l'exemple
suivant :
f(x,y,u,v)= f(x).
L'évaluation se fait donc de gauche à
droite et est en profondeur
d'abord.
On appel séquence, une liste d'opérateurs. Elle est déjà
utilisé comme liste d'arguments. L'extenssion du langage aux séquences d'opérateurs va constituer une généralisation
homogénéisante du langage.
La séquence possède une liste d'entrés qui est la
réunion mise bout à bout des listes d'entrés de ses opérateurs dans
l'ordre, et possède une liste de sorties qui est la réunion mise bout à
bout des listes de sortie de ses opérateurs dans l'ordre, et possède
donc une arité d'entré qui
est la somme des arités d'entré des opérateurs de la séquence, et une
arité de sortie égale à la sommes des arité de sortie des opérateurs de
la séquence.
On construit les séquences à l'aide d'un méta-opérateur de construction qu'est l'opérateur de séquence noté par la virgule ",".
Le méta-opérateur de séquence est associatif :
La notion d'opérateur se généralise afin de pouvoir posséder plusieurs sorties numérotées dans l'ordre, de telle sorte qu'une séquence d'opérateurs définie également un opérateur. Les opérateurs sont des sortes de neurones avec n entrés et m sorties, et les méta-opérateurs assemblent ces neurones en d'autres neurones en les modifiant par redirection, duplication et raccordement de leurs entrés-sorties.
Un opérateur isolé est identique à une séquence singleton.
x = (x)
La séquence vide correspond à un opérateur d'arité d'entré zéro et d'arité de sortie zéro. ce qui en fait un élément neutre.
f() = f
La virgule "," et la composition "°" sont des méta-opérateurs, des
opérateurs spéciaux qui agissent sur les opérateurs du langage. Il y a
bien deux niveaux de protocole, celui des opérateurs du langage
comprenant les variables d'entrées (opérateurs variables d'arité zéro)
et les opérateurs constants d'arité diverse déclarés dans le langage,
et les différentes sorte de composition de ces opérateurs que sont la
composition "°" et le séquençage ",".
La priorité de la composition est posée plus forte que celle du séquençage ce qui justifie l'écriture g(x,y) au lieu de gx,y et nous avons :
g(x,y) = gxy
g(x,.),y = gx,y
Un programme d'arité de sortie 1, comprenant des séquences, est
toujours simplifiable en supprimant les parenthèses et les virgules et
en notant
la composition par l'absence de symbôle, comme une simple
juxtaposition, qui est alors interprétés en logique polonaise. Un
programme possédant plusieurs sorties se décompose en une séquence de
programme d'arité de sortie 1. Et ce développement n'est pas une
défactorsation, la complexité de calcul n'en n'est pas changée.
Le deuxième niveau de protocole peut être rendu complètement implicite, les symbôles ",", "°", "(" et ")" sont simplement enlevés comme dans les exemples suivants :
g(h,k)(x,y,u,v) = g(h(x,y),k(u,v)) = ghxykuv
g(f,g)(x)(u,v) = g(f(x),g(u,v)) = gfxguv
g(f,g)(x,f,y)(u) = g(f(x),g(f(u),y)) = gfxgfuy
Cette traduction ne modifie pas la complexité du calcul.
On ajoute l'opérateur point pour désigner une entré libre dans la liste des entrés. Le langage de logique polonaise peut alors définir toutes les séquences d'opérateurs (et se restreindre aux seuls termes clos pour assurer l'unicité de la représentation) comme par exemple :
xf.y = x,f(.),y
f.xgfy.uf. = f(.),x,g(f(y),.),u,f(.)
f.g..x = f(.),g(.,.),x
. = id(.)
La composition de deux tel séquences se fait par le biais d'un méta-opérateur "|" dans le même mode de composition mais à un niveau au dessus. On complète ainsi le langage :
On remarquera que la formule, développée ou non, est de même complexité de calcule.
Lorsqu'il y a trops d'arguments, ils sont ignorés. C'est le choix le plus simple. C'est le mode dit non-harmonique.
g(f,f)(x,y,u,v) = g(f(x),f(y)) = gfxfy
Dans un opérateur, ou dans une séquence d'opérateurs,
les entrés doivent être ordonnées et sont
numérotés à partir de 1. Ainsi la séquence f(.),g(.,.),x,f(.) se
notera explicitement <f(1),g(2,3),x,f(4)>. Les crochets <>
sont placés pour préciser qu'une permutation-projection des entrés est
mentionnée dans l'écriture. Aprés composition parallèle
ou série, de nouveaux opérateurs apparaîtront avec des entrés dans un
ordre différents. Une séquence d'opérateurs plus générale avec
des entrés selon une projection-permutation doit être définissable tel
que <f(3),g(1,3)>. Elle se
décompose en une séquence sans permutation-projection composée
par une permutation-projection :
<f(3),g(1,3)> =
(f(1),g(2,3)) <id(3),id(1),id(3)>.
<f(3),g(1,3)> =
(f(.),g(.,.)) <3,1,3>
<f(3),g(1,3)> = (f,g) <3,1,3>
<f(3),g(1,3)> (x,y,u,v) = f(u),g(x,u)
où <3,1,3> = <id(3),id(1),id(3)> et où id représente l'opérateur identité qui prend en argument un booléen et retourne le même booléen. Les permutation-projections sont des séquences d'entrés.
Un opérateurs ou une séquence d'opérateurs possède un rayon d'entré
à partir du quel
les
entrés suivantes sont sûre de ne pas exister. Par convention le rayon
d'entré de la séquence peut être définie comme son entré de numéro le
plus
élevée. Ainsi la séquence <f(3),g(1,3)> à un rayon égale à 3. De
même on définie un rayon de sortie égale au numéro de la plus grande
sortie qui correspond au nombre d'opérateurs présent dans la séquence.
On concoit un autre mode de composition, dans le quel la
séquence vide correspond à un opérateur prenant une infinité d'entrés
et la retournant à l'identique en une inifinité de sorties. son rayon
d'entré et de sortie sont pourtant toujours égal à zéro. Ce mode dit harmonique s'applique aussi aux
autres séquences d'opérateurs comme suit :
( )
= <1,2,3,4...>
rayon d'entré = 0 rayon de sortie = 0
f =
<f(1),2,3,4,5...>
rayon d'entré =
1 rayon de sortie = 1
g =
<g(1,2),3,4,5...>
rayon
d'entré = 2 rayon de sortie = 1
f,g =
<f(1),g(2,3),4,5,6...>
rayon d'entré =
3 rayon de sortie = 2
Ce mode a l'avantage de ne pas tronquer les séquences séries, et donc de ne pas perdre d'information. Et il permet donc de rendre le sense de l'évaluation de la composition indifférent ( de gauche à droite ou de drtoite à gauche). Il permet de définire en logique polonaise, par simple composition, les séquences terminales-close qui sont composées d'une liste d'opérateurs zéro-aire et terminées par un opérateur quelconque. Par exemple :
Et on peut également ajouter l'opérateur point pour désigner une entré libre dans
la liste des entrés :
xf.y = x,f(.),y = <x,f(1),y,2,3,4,5...>
f.xgfy.uf. = f(.),x,g(f(y),.),u,f(.) = < f(1),x,g(f(y),2),u,f(3),4,5,6,7...>
f.g..x = f(.),g(.,.),x = <f(1),g(2,3),x,4,5,6,7...>
. = id(.) = <id(1),2,3,4,5...>
La composition de deux tel séquences se fait par le biais d'un méta-opérateur "|" dans le même mode de composition mais à un niveau au dessus. On complète ainsi le langage :
On remarquera que la formule, développée ou non, est de même complexité de calcule.
Le langage ainsi proposé reste faible, il lui
manque la capacité première de factoriser, de distribuer, d'opérer des
algorithmes de composition parallèle. On introduit la séquence
d'opérateurs avec
composition des entrés en parallèle.
Certe cela ne permet pas de créer des fonctions mathématiques
nouvelles, mais cela permet de créer des algorithmes nouveaux plus
efficace calculant ces mêmes fonctions, en réutilisant des calculs déjà
calculés, sans les recalculer. Ces fonctions sont ainsi programmées
avec
une complexité de calcul plus faible.
Le meta-opérateur de séquençage parallèle noté × distribue les entrés parallèlement sur ces deux opérateurs arguments, et ajoute leurs sorties dans l'ordre. C'est une opération associative. Elle peut être- répetée pour créer une séquence dans laquel les entrés sont parallélisés. Par exemple :
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 à des séquences d'opérateurs d'arités distinctes, les arguments supplémentaires sont ignorés, et dans le mode harmonique, s'ils sont ignorés par tous les opérateurs de la séquences, alors ils sont ajoutés au résultat à la suite en séquence série. Se faisant dans le mode harmonique, l'information n'est pas perdu par composition (même si des composants partiels semblent perde cette information). Ainsi nous avons :
Mode non-harmonique :
f×g×u×f×g
= <f(1),g(1,2),u,f(1),g(1,2)>
rayon d'entré = 2
rayon de sortie = 5
f,g,u,f,g = <f(1),g(2,3),u,f(4),g(5,6)> rayon d'entré = 6 rayon de sortie = 5
(f×g)(x,y,u,v) = f(x),g(x,y)
(f,g)(x,y,u,v) = f(x),g(y,u)
Mode harmonique :
f×g×u×f×g = <f(1),g(1,2),u,f(1),g(1,2),3,4,5,6...> rayon d'entré = 2 rayon de sortie = 5
f,g,u,f,g = <f(1),g(2,3),u,f(4),g(5,6),7,8,9,10...> rayon d'entré = 6 rayon de sortie = 5
(f×g)(x,y,u,v) = f(x),g(x,y),u,v
(f,g)(x,y,u,v) = f(x),g(y,u),v
Il existe donc trois méta-opérateurs auquel on attribut les priorités suivantes de la plus élevé (prioritaire) à la moins élevé :
| Nom |
Symbole | Priorité | Sense |
| Composition | ° | 10 | de gauche à droite si non-harmonique |
| Séquençage paralélle | × | 5 | indifférent |
| Séquençage série | , | 1 | indifférent |
Et le méta-opérateur ° peut être désigné par l'absence de
méta-opérateur comme simple juxstaposition selon la logique polonaise.
Par exemple :
(f×g×h)°(x,y) = f°x,g°x°y,h°x°y = fx,gxy,hxy
(f,f×h,h)°(x,y,u,v) = f°x,f°y,h°y°u,h°v = fx,fy,hyu,hv
Le langage peut contenir les 2 méta-opérateurs séquence parallèle "×" et séquence série ",", puis les deux parenthèses "(" et ")", puis peut contenir une centaine d'opérateurs prédéfinis +(.,.), w(.,.), *(.,.), et(.,.), ou(.,.), =>(.,.), <=(.,.), <=>(.,.), ¬(.), .(.), puis peut contenir 31 variables booléennes d'entrés, X1, X2, X3...X31, puis le méta-opérateur nul de fin de mot.
La séquence parallèle n'est pas qu'une simplification d'écriture, de complexité de Kolmogorov plus courte, elle met en oeuvre aussi une factorisation, de complexité calculatoire plus petite.
g(h×k)(h×k)(h×k)(x,y) = g(h×k)(h×k)(h(x,y),k(x,y))
=
g(h×k)(h(h(x,y),k(x,y)),k(h(x,y),k(x,y)))
=
g(h(h(h(x,y),k(x,y)),k(h(x,y),k(x,y))),k(h(h(x,y),k(x,y)),k(h(x,y),k(x,y))))
= ghhhxykxykhxykxykhhxykxykhxykxy
On simplifie le langage en retirant le méta-opérateur de séquence série puisque g(x,f)(y) = gxfy
et que g(f,x)(y) = gfxy et que finalement x,f = x°f. Il reste un seul méta-opérateur encore visible, qui est ×.
On peut simplifier considérablement le langage en supprimant les parenthèses. La priorité de l'opération × est nécessairement plus forte que celle de la composition, afin de pouvoir définir un opérateur d'arité de sortie égale à 1.
En langage de logique polonaise : g(h×k)(h×k)(h×k)(x,y) = ghhhxykxykhxykxykhhxykxykhxykxy
En langage de logique polonaise factorisé et simplifié, nous avons : g(h×k)(h×k)(h×k)(x,y) = gh×kh×kh×kxy
Pour interpréte,
Une troisième étape consiste à utiliser 2*n littéraux et deux
opérateurs commutatifs multi-aire, et{...}, ou{...}.
Un littéral est la
composition ou non de l'opérateur de négation et d'une variable. Il y a
2*n littéraux propres X0, X1, X2,
X3,... Xn-1, ¬X0, ¬X1,
¬X2, ¬X3,... ¬Xn-1,
auquel on ajoute parfois les deux littéraux impropres que sont 0 et 1.
Les opérateurs et{...} et ou{...} agissent sur un nombre variable
d'arguments, et vérifient les règles de simplification suivantes
et{} = 1
ou{} = 0
et{x} = x
ou{x} = x
Ils sont chacun commutatif c'est à dire que l'ordre des éléments entre crochet peut être librement permuté. Et ils sont chacun associatifs, c'est à dire :
et{et{x1,x2,x3...},y1,y2,y3...} =
et{x1,x2,x3...,y1,y2,y3...}
ou{ou{x1,x2,x3...},y1,y2,y3...} = ou{x1,x2,x3...,y1,y2,y3...}
On ajoute l'opérateur de négation ¬(.) avec les règles de simplifications suivantes :
Une expression booléenne correspond à un ensemble. La négation
correspond au complément de l'ensemble, le et{...} correspond à
l'intersection des ensembles. Le ou{...} correspond à l'union des
ensembles. Les variables
booléennes X0, X1, X2,
X3,... Xn-1 correspondent à des ensembles
inconnus. On ajoute les constantes logiques 0
et 1 qui correspondent respectivement à l'ensemble vide et à
l'ensemble mère unions de tous les autres ensembles concidérés.
Le et{....}
est distributif sur
le ou{....} et réciproquement. C'est à dire :
Les règles de simplification suivante permettent de définir une
forme normale
Une
expression admet une forme unique dite "normale", qui est une
conjonction minimale de
disjonctions de littéraux (et admet une autre forme normale
conjuguée, une
disjonction minimale de conjonctions de littéraux). L'expression est
totologiquement fausse si et seulement si elle
admet comme forme normale ou{}, et l'expression est totologiquement
vrai
si et seulement si elle admet comme forme normale et{}.
| Nom |
Identifiant |
Priorité |
| ¬ | -1 |
20 |
| w |
-2 |
18 |
| => |
-3 |
15 |
| <= |
-4 |
15 |
| <=> |
-5 |
10 |
| * |
-6 |
6 |
| et |
-7 |
6 |
| ou |
-8 |
4 |
| + |
-9 |
2 |
| Langage
d'opérateur |
Logique
polonaise |
| x+y |
+xy |
| ¬x+y |
+¬xy |
| ¬(x+y) |
¬+xy |
| x+y*z |
+x*yz |
| x*y+z |
+*xyz |
| x*(y+z) |
*x+yz |