Langage et calcul

1) Introduction

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.

2) Algorithme cumulatif

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.

2.1) Boolénisation

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`.

2.2) Finitude

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.

2.3) Algorithme Shadock

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`.

3) Langage de calcul et entrés-sorties

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.

4) Langage de calcul avec un unique opérateur générateur `"∗"`

Langage

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(.,.)"}`

Langage simplifié

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`

Implémentation

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`.

5)  Langage de calcul avec deux opérateurs générateurs `+, "∗"` formant un corps

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 :

  1. L'ensemble sous-jacent : `{"faux", "vrai"}`
  2. L'addition : `"+"`
  3. L'élément neutre de l'addition : `0`
  4. La soustraction unaire (l'opposé) : `"-"`
  5. La multiplication : `"∗"`
  6. L'élément neutre de la multiplication : `1`
  7. La division unaire (l'inverse) : `"÷"`

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"`.

(
`{"faux", "vrai"},`
`"⇎",`
`"faux",`
`"id",`
`"et",`
`"vrai",`
`"id"`
)
(
`{"faux", "vrai"},`
`"+",`
`0,`
`"-" ,`
`"∗",`
`1,`
`"÷"`
)

`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"`.

(
`{"faux", "vrai"},`
`"",`
`"vrai",`
`"id",`
`"ou",`
`"faux",`
`"id"`
)
(
`{"faux", "vrai"},`
`"+",`
`0,`
`"-" ,`
`"∗",`
`1,`
`"÷"`
)

`x"∗"y = x "ou" y`
`x"+"y = x"⇔"y`
`"¬"x = x"+"1`

5.1) Polynôme sous forme normale

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 ----

 

 

 

 

 

6)  L'addition de deux n-uplets

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 --------

10.3) La structuration

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é.

Langage

Un programme est une liste d'opérateurs constants et de variables qui doit être close selon l'arité des opérateurs invoqués.

Langage simplifié

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.

Implémentation

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).

10.4) Les langages d'opérateurs en logique polonaise

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.

La currification

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 :

f°x = fx = f(x)
f°f = ff = f(f)
f(f) = z-->f(f(z))

La logique polonaise

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.

Les séquences

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 :

(f,g),h = f,(g,h)

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.

L'opérateur .

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 :

f.g..|xf.y|u = fxgf.y|u = fxgfuy

On remarquera que la formule, développée ou non, est de même complexité de calcule.

Mode non-harmonique

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

Opérateur avec permutation-projection

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.

Rayon d'entré et de sortie

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.

Mode harmonique

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 :

xyuv = x,y,u,v
g = g(.,.)
xyg = x,y,g(.,.)
xygguf = x,y,g(g(u,f(.),.),.)

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 :

f.g..|xf.y|u = fxgf.y|u = fxgfuy

On remarquera que la formule, développée ou non, est de même complexité de calcule.

10.5) La factorisation

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))>

entrés en serie
entré en paralèlle

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

10.4) L'implémentation

Pour interpréte,


D. Mabboux-Stromberg







10.3)  et{...}, ou{...}

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 :

¬¬x = x
¬et{x1,x2,x3...} =  ou{¬x1,¬x2,¬x3...}
¬ou{x1,x2,x3...} =  et{¬x1,¬x2,¬x3...}

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 :

et{ou{x1,x2,x3...},y1,y2,y3...} = ou{et{x1,y1,y2,y3...},et{x2,y1,y2,y3...},et{x3,y1,y2,y3...}...}
ou{et{x1,x2,x3...},y1,y2,y3...} = et{ou{x1,y1,y2,y3...},ou{x2,y1,y2,y3...},ou{x3,y1,y2,y3...}...}

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{}.



















l'équation booléenne composé de chiffre de 1 à n pour désigner les n booléens, et des opérations boolénnes classiques {et, ou,¬, w, <=>, <=, =>, +, *} et de l'emboitement de parenthèses. (Bien entendu cela est tout à fait insuffisant pour exprimer des équations savantes avec une faible complexité de Kolmogorov.)

La fonction Bool(E,X) intérprète l'équation E sur l'entré X. Une compilation est plus apropriée. On va utiliser le compilateur gcc. On va automatiser l'écriture d'un programme C dans lequel une première partie décompresse le n-uplet X de 32 bits sur 32 octects, une seconde partie va effectuer les opérations de l'équation E sur ces 32 octets, et une dernière partie va retourner le résultat. Ce programme sera compilé avec gcc dans la phase initiale du programme Run(E,g,N), puis lancé sur chaque exemple X. La fonction Compil(E) écrit ce programme C.

Le langage d'équation utilisé est relativement simple. C'est un langage d'opérateurs comprenant n opérateurs d'arité zéro, un opérateur unaire droit, et 8 opérateurs binaires de forme syntaxique symétrique. Chaque opérateur zero-aire possède un nom égale à son identifiant de 1 à n, L'opérateur unaire possède le nom "¬", l'identifiant -1 et une priorité 20. Et chaque opérateur binaire possède un nom, un identifiant et une priorité comme suit :

Nom
Identifiant
Priorité
¬ -1
20
w
-2
18
=>
-3
15
<=
-4
15
<=>
-5
10
*
-6
6
et
-7
6
ou
-8
4
+
-9
2

On remarquera que les espace blancs ne sont pas nécessaires. On définie la fonction ischarop(c) qui reconnait les caractères {-62, -84, w, =, >, <, *, e, t, o, u, +}. Le caractère ¬ occupe deux octets de valeurs -62 et -84. Et on utilise la fonction prédéfinie  isdigit(c) pour reconnaitre un chiffre.

L'algorithme consiste en trois traductions et d'une évaluation en logique polonaise.

Une première traduction transforme la chaine de caractères E en une suite de couples (identifiant, priorité) correspondant à chaque opérateur rencontré dans E, et au parenthèse ouvrante d'identifiant -10 et fermante d'identifiant -11. L'identifiant 0 correspond à la fin de la liste, c'est à dire la fin de l'équation. On établit un code de hachage en sommant les valeurs des octets composant le nom de l'opérateur.  On reconnait l'opérateur selon ce code de hachage, et on mémorise l'opérateur selon son identifiant.

Une seconde traduction fixe les priorités et enlève les parenthèses en ajoutant 100 à la priorité des opérateurs se trouvant l'intérieur d'un niveau de parenthèse, et ceci cumulativement. Ainsi si un opérateur est dans un troisième niveau de parenthèse sa priorité est augmenté de 300.

Une troisième traduction transforme la suite en une suite de logique polonaise, comme par exemples :

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

Puis on transcrit la suite de logique polonaise en instructions C.