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, une recherche de solutions. Et, un des algorithmes les plus simple consiste à chercher au hasard les solutions et à les mémoriser, c'est l'algorithme cumulatif aussi appellé algorithme de 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 marchent.

La fonction mathématique calculable F est définie d'une certaine façon. Et X est une donnée. La donnée comme la fonction est de quantité d'information finie et peut donc être décomposés en quantités booléennes finies. On peut donc les représenter par des n-uplets de booléens.

X peut être concidéré comme un n-uplet de booléens. De même pour F à ceci près qu'il faut convenir d'un système de consruction de F transformant une donnée passive tel que un n-uplet de booléens, en une fonction calculable, un processus de calcul. Et la difficulter reste de choisir un système suffisament générale pour satisfaire à notre exigence d'universalité.

Dans un premier temps, on ne s'intéresse pas à la complexité de calcul de F, et on décompose cette fonction, faisant qu'elle est choisie comme étant une fonction prenant en entré un n-uplet de booléens et retournant en sortie un seul booléen.

Les définitions de X sont choisies de type énumératif. Et les définitions de F sont choisies de type programmatif, c'est à dire que l'on définie le calcul de F. La connaissance de la définission programmative de F et de la définission énumérative de X permettent de faire le calcul machinalement de F(X). Le type énumératif fait évidement partie du type programmatif.

L'algorithme cumulatif comprend une fonction Rand(n,g,i) qui produit un n-uplet de booléens X au hasard à partir d'une graine système g et d'un indice i (c'est une suite de n-uplets au hasard d'indice i), une fonction Bool(F,X) qui retourne un booléen résultat du calcul de F(X), et un démon Run(F,g) qui retourne un flux de couples (i,X)i est l'indice et X une solution de l'équation F(X)=0. Puis on ne se préoccupe pas de l'arrêt du démon. Celui-ci restera à la charge du processus père qui à lancer le démon et qui gèrera son arrêt ou bien à défaut à la charge de l'utilisateur qui pourra tuer le processus.

On pose pour commencer n inférieur à 32 faisant que X tient sur un mots de 32 bits et que la fonction C prédéfinie rand() peut fair l'affaire. Cette restriction permet de concrétiser plus rapidement des essais de programmation. La taille de X est ainsi définie égale à 32 bits. Mais il n'en est pas de même pour F, et cela va nous obliger à choisir une structure de donnée pour F en plus de son langage de programmation, c'est à dire un protocoles de bas niveau pour spécifier sa taille.

3) Langage de calcul et entrés-sorties

On convient d'utiliser le terme de fonction, ou d'opérateur, d'avantage dans le sense physique que mathématique, c'est à dire comme des programmes ayant une complexité de calcul propre. On cherche un langage de programmation pour décrire ces programmes qui soit totalement dense ou autant que possible. C'est à dire tel que, une expression au hasard désigne nécessairement un programme valide syntaxiquement, et tel que deux expressions distinctes désignent autant que possible deux programmes distincts sémantiquement, c'est à dire deux procédés de calculs distincts.

La donnée atomique est le booléen. La fonction atomique possède n entrés booléennes et une sortie booléenne. Lorsque l'on cherchera a minimiser la complexité de calcul nous serons amené à considérer des fonctions à plusieurs sorties, évoquant d'avantage le calcul parallèle. La fonction est composé de fonctions plus petites tel un fractal.

On note la fonction par F, et on note le n-uplet de booléen par X. On choisie comme structure de données pour X, celle d'un n-uplet de booléens, une suite consécutives de bits mémoires tenant sur un mot de 32 bits. n est un paramètres désignant la taille de X inférieur à 32 et qui devra donc être fixé.

Le n-uplet de booléens X se décompose comme suit

X = [ X[0], X[1], X[2], X[3],... X[n-1] ] 

X[i] est une mémoire contenant un booléen, et l'indice i qui désigne l'adresse relative de cette mémoire, varie de 0 à n-1. Pour alléger l'écriture on notera X[i] simplement par Xi, ainsi nous avons :

X = [X0, X1, X2, X3,... Xn-1]

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 opérateur d'arité zéro ajoutés au langage et sont notés comme suit :

X0, X1, X2, X3,... Xn-1

Le langage comprend ces n noms de variables (opérateurs variables d'arité zéro) pour désigner les n arguments booléens qui sont transmis en entré au programme F.

Le langage de programmation est augmenté d'autres opérateurs qui sont choisis pour l'enrichir. L'extention du langage augmente à la fois sa capacité à définir des programmes tel que F, et à définir des programmmes produisant le même résulat mais avec une complexité de l'expression (complexité de Kolmogorov) plus petite, et on verra par la suite, à définir des programmmes produisant le même résulat avec une complexité de calcul plus petite.

4) Langage de calcul avec l'opérateur NAND (noté ¬et)

Langage

On utilise l'opérateur logique binaire nand noté également ¬et(.,.) qui est commutatif et non associatif, et qui engendre tous les autres opérateurs logiques. Les programmes sont alors les termes clos du langage {X0, X1, X2, X3,... Xn-1, ¬et(.,.)}.

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 terme clos ci-dessous se transforme en une chaine de caractères d'alphabet {a, b, c, d..., ★}. Le programme devient une chaîne de caractère. Par exemple, en utilisant a,b,c au lieu de X1,X2,X3 et le symbole au lieu de ¬et, voici un programme mis sous forme de chaine de caractères :

¬et(X1,¬et(X2,X3))

★(a,★(b,c))

★a★bc

Implémentation

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. Par exemple ★a★bc :

On réserve une pile de même taille ([P0, P1, P2, P3, P4], i=0)
On lit "c" et on l'empile : Pi=c, i=i+1
On lit "b" et on l'empile : Pi=b, i=i+1
On lit "" et on effectue le nand : i=i-1, Pi-1 = ¬et(Pi-1, Pi), cela enlève un élément de la pile.
On lit "a" et on l'empile : Pi=a, i=i+1
On lit "" et on effectue le nand : i=i-1, Pi-1 = ¬et(Pi-1, Pi), cela enlève un élément de la pile.
On retourne le résultat P0.

5)  Langage de calcul avec 1, +, *

On peut utiliser les trois opérateurs logiques 1, +(.,.), *(.,.) pour former la structure de corps (Z/2Z,+,*). Le produit est identique à l'opérateur "et". L'addition est identique à l'opérateur "ou exclusif", noté "w" :

x*y = x et y
x+y = x w y = ¬(x<=>y)

La négation de x s'optient en ajoutant 1 : ¬x = x+1

(x + y + z + t) signifie (x w y w z w t), et cela signifie qu'il existe un nombre impaire de valeur égale à 1 parmis {x,y,z,t}

Les variables booléennes d'entrés constituent une extensions élémentaires de la structure de corps (Z/2Z,+,*). Et les expressions booléennes forment alors une structure d'anneau de polynômes (où les monômes sont des conjonctions) :

Z/2Z[X0, X1, X2, X3,... Xn-1]

Le programme F est un polynôme à n variables dans Z/2Z et admet une forme normale dans le corps de caractéristique 2, que l'on obtient en développant à l'aide des propriétés supplémentaires x+x=0 et x*x=x. Le développement est d'une complexité de calcul en 2^n.

F est dit totologique lorsque le programme F donne un résultat toujours égale à 1, c'est à dire lorsque ∀X, F(X)=1. Cela se produit si et seulement si le polynôme de F mis sous forme normale est identique à 1. De même F est dit contradictoire lorsque programme F donne un résultat toujours égale à 0, c'est à dire lorsque ∀X, F(X)=0. Cela se produit si et seulement si le polynôme de F mis sous forme normale est identique à 0.

Un monôme correspond à un sous-ensemble de {X0, X1, X2, X3,... Xn-1} est possède une représentation unique sur un mot de 32 bits. Un polynôme est une suite de tels monômes triés dans l'ordre. Sa représentation est alors unique, et est appellé 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 en une pile triée de mots de 32 bits.

Le polynôme est une expression développée. Dans certain cas cette expression peut être factorisés, et la complexité d'expression (complexité de Kolmogorov) ainsi que la complexité de calcul sont alors réduite.

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.