Les structures de fonctions

  1. Introduction
  2. Monoïde
  3. Fonctions unaires
  4. La composition de fonctions
  5. L'appel
  6. Monoïde de fonction agissant sur lui-même
  7. Fonctoïde
  8. Indifférentiation entre Appel et Composition
  9. Fonctoïde associatif

0) Introduction

Une des voies de recherche des structures mères consiste à augmenter l'interopérabilité sans restreindre la généralité, et à considérer toute construction comme la construction d'une fonction calculable. Un des moyens d'augmenter l'interopérabilité est de considérer les éléments comme des fonctions unaires, de rendre l'élément indifférentiables de la fonction sans pour autant en restreindre sa généralité.

1) Monoïde

Un monoïde (M,*) possède 2 axiomes résumés ainsi : l'opération * est interne et associative dans M :

Quelque soit x, y, z appartenant à M nous avons :

Cette structure n'est pas arbitraire, elle correspond à deux concepts clés que sont la composition de fonction unaire et la cloture par composition. La composition de fonction est en effet associative, et la cloture rend la composition interne.

L'associativité indique que les éléments peuvent être identifiés à des fonctions unaires de tel sorte que l'opération coïncide avec la composition de fonctions. Tout monoïde est isomorphe à un monoïde de fonctions qui agit sur lui-même par translation gauche (ou droite), voir Structures fondamentales.

2) Fonctions unaires

On redéfinie le concept de fonction unaire f de manière plus constructive, en ne s'intéressant dans la fonction f qu'aux seuls programmes opérant des constructions. On remplaçe le concept d'ensembles de départ et d'arrivé par un concept plus large de domaines constructifs, assimilables à d'autre fonctions calculables. Par exemple considérons une fonction f définie ainsi :

f : (v(y,x),y)-->(v(x,y),x)

Le domaine de définition de f que l'on note dom(f), comprend tous les mots du langage unifiables avec l'entête de la fonction f. Le domaine se présente ici comme un filtre, et constitue une première fonction dite d'entête fhead, qui est alors composée avec le reste de la fonction appelé fcorps :

f = fcorps ° fhead

fhead : (v(y,x),y)-->(x,y)
f
corps : (x,y) -->(v(x,y),x)

La fonction d'entête est un programme qui appliqué à un élément en dehors du domaine retourne FAIL. Dans l'exemple la fonction f se décompose en une fonction d'entête fhead et en une fonction corps fcorps. Et cette dernière fonction a comme domaine les couples de mots, c'est à dire qu'elle est d'arité 2 et qu'elle ne possède pas de filtre, pas de limite au domaine.

Si on ajoute l'élément FAIL au langage pour former un méta-langage, chaque fonction aura alors un méta-domaine sans limite. Dans ce méta-langage, toutes les fonctions d'arité n ont un meta-domaine égale à l'ensemble des n-uplet de mots du méta-langage. Si x n'appartient pas au domaine de définition de f alors f(x) = FAIL, et inversement si f(x) = FAIL alors x n'appartient pas au domaine de définition de f.

Le langage utilisé n'est pas prédéfinie, et en particulier il peut s'étendre...

Ayant définie à la place des ensembles de départ et d'arrivé, des domaines constructifs, qui sont des objects à la fois plus généraux et plus simples que les ensembles. Cela nous permet de définir sans ambiguité la composition de deux fonctions quelconques indépendament de leurs ensembles de départ et d'arrivé.

Une hypothèse est faite sur la calculabilité, à savoir que la fonction effectue bien le calcul en un temps fini. La fonction possède donc un programme qui se termine toujours en un temps fini.

Le langage joue toujours le premier rôle. La première question est celle de la représentation, comment définire une fonction avec le moins d'arbitraire possible ?, existe-t-il une forme normale ?, et finalement à savoir de façon plus pragmatique quelles sont les conditions strictement nécessaires pour que deux fonctions f et g soient égales ?. Il existe plusieurs niveaux d'égalité.

On dira que deux fonctions sont égales si elles possèdent le même programme.

On dira que deux fonctions sont équivalentes si appliquées à x elles ont même résultat, et ceci quelque soit x.

f <=> g si et seulement si ∀x   f(x)=g(x)

La significaton de ∀x  n'est pas simple, car il n'y a pas de langage prédéfinie, ou plus exactement il y en a un, porté par le contexte, et qui est suceptible de s'étendre. Soit L ce langage. ∀x  désigne tous les mots du langage L, mais pas seulement. Il désigne aussi les mots du langage étendu. Et toutes les extensions du langage sont envisageables. Néanmoins comme les langages en question sont des langages d'opérateurs d'arité fixé, si un opérateur est définie ayant une arité n, dans toutes les extentions possibles de ce langage, l'opérateur en question aura toujours la même arité n.

3) La composition de fonctions

Le rôle de la fonction est de transformer les éléments. Comment noter la succession des transformations d'un élément x ?. Nous allons d'abord utiliser la notation française de la composition de fonction. La notation française (f·g·h)(x) = h(g(f(x))) permet d'écrire de gauche à droite la succession des transformations dans le même ordre : x --> f(x) --> (f·g)(x) --> (f·g·h)(x) d'un élément x transformé par la fonction f, et si on suppose que x appartient au domaine de définition de f noté dom(f), l'élément f(x) est différent de FAIL et peut lui-même être transformé par la fonction g en g(f(x)) et ainsi de suite.... Cela décrit les fonctions comme des transformations se succédant. L'expression (f·g·h)(x) désigne un élément différent de FAIL si x ∈dom(f) et f(x) ∈dom(g) et (f·g)(x) ∈dom(h).

En utilisant l'élément FAIL, l'hypothèse d'appartenir au domaine de définition n'est plus nécessaire. Si l'élément x n'est pas dans le domaine de définition de f, alors f(x) retournera FAIL. La fonction suivante g s'appliquera a l'élément FAIL. Et généralement lorsqu'un des arguments d'une fonction est FAIL, la fonction retourne FAIL.

La notation anglaise utilise l'opérateur de composition ° et s'effectue dans l'ordre inverse, tandis que la notation française utilise le symbole de composition · :

f(g(h(x))) = (f °g°h)(x) = (h·g·f)(x)

4) L'appel d'une fonction

On explicite l'appel d'une fonction f sur l'élément x par une opération que l'on note / selon la notation anglaise, et que l'on note | selon la notation française.

f(x)  =  f / x 
f(x)  =  x | f

De même l'appel peut être noté à la française (x)f ou à l'anglaise f(x). L'ordre d'évaluation implicite est inversé entre la notation anglaise et française.

f(x)(y)(z)  =  ((f/x)/y)/z  =  (x)(y)(z)f  =  x|(y|(z|f))

La notation d'appel à la française et à d'appel l'anglaise ne doit pas être mélangée car une expression telle que (x)(y)(z) aurait deux senses (x/y)/z ou x|(y|z). Aussi on n'utilisera que les appels à l'anglaise.

L'opération d'appel n'est pas associative. En effet, en générale x(y(z)) ≠ x(y)(z), autrement dit x/(y/z) ≠ (x/y)/z

Quelque soit x,y,z appartenant à F nous avons les règles de simplification suivantes :

x/(y/z) = (x°y)/z
(x°y)°z = x°(y°z)

Voyons les différentes expressions qu'il est possibles de construire avec l'opérateur d'appel |, à partir d'une liste d'éléments dans un ordre imposé. Comme on ne se préoccupe pas de l'ordre, que celui-ci est imposé, que l'on envisage pas de permutation, l'hypothèse peut être ramenée à une suite de n éléments identiques (e,e,e...) sur laquelle on envisage toutes les constructions possibles avec un opérateur binaires. Cela consiste a passer en revue les arbres binaires nus ayant n feuilles (c'est à dire n-1 noeuds).

Notation
française
Notation
anglaise
Appel
e|e
e/e
e(e)
(e|e)|e
e|(e·e)
e/(e/e)
(e°e)/e
e(e(e))
e|(e|e)
(e/e)/e
e(e)(e)
((e|e)|e)|e
e|(e·e·e)
e/(e/(e/e))
(e°e°e)/e
e(e(e(e)))
(e|(e|e))|e
e/((e/e)/e)
e(e(e)(e))
(e|e)|(e|e)
(e/e)/(e/e)
e(e)(e(e))
e|((e|e)|e)
e|(e|(e·e))
(e/(e/e))/e
(e°e)/e/e
e(e(e))(e)
e|(e|(e|e))
((e/e)/e)/e
e(e)(e)(e)

Les nombres d'arbres binaires nus, selon le nombre de feuilles, est 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796..... Ce sont les nombres de Catalan notés C(n) :

C(n) = (2n)!/((n+1)!*n!)
C(n) = 2*(2*n+1)/(n+2)* C(n-1)
C(n) ∼ 4^n / (n^(3/2) * sqrt(π))

5) Monoïde de fonctions agissant sur lui-même

Afin d'optenir une plus grande intéropérabilité on considère un monoïde (M,*) que l'on va faire agir sur lui même. Cela signifie que les éléments du monoïde sont à la fois élément et fonction unaire et plus exactement application de M sur M. La formalisation de ce choix se fait en l'explicitant. On définie l'agitateur P comme étant la fonction qui associe à chaque élément du monoïde, une application de M sur M, de tel sorte que quelque soit x,y appartenants à M nous ayons P(x)°P(y) = P(x*y). C'est à dire que la composition ° d'application doit respecter l'opération * du monoïde. La structure se présente alors comme suit :

Monoïde agissant sur lui même (M,*,P)

Le patron de la structure est "Monoïde agissant sur lui même", l'ensemble sous-jacent est M, l'opération interne est *, l'agitateur est P. Noter que P peut être vu comme un opérateur d'appel à l'anglaise, x P y = P(x)(y) désignant l'image de y par la fonction associée à x. C'est pourquoi on notera souvant cette opérateur par /. Le monoïde agissant sur lui même (M,*,/) possède la théorie suivante :

∀x∈M,  ∀y∈M, x*y∈M
∀x∈M,  ∀y∈M, ∀z∈M, (x*y)*z = x*(y*z)
∀x∈M,  ∀y∈M, x/y∈M
∀x∈M,  ∀y∈M, ∀z∈M, x/(y/z) = (x*y)/z

Autrement dit : * est interne, * est associatif, / est interne, * est la composition de l'appel /

--- 6 Décembre 2012 ---

 

Et, afin que l'élément f(x) existe même lorsque x est en dehors du domaine de définition de f, on a ajouté l'élément FAIL appelé petit zéro et que l'on notera aussi par o.

Un langage maximalement intéropérable n'est pas limité, il est par principe libre, et on le maintient libre en reportant toutes les contraintes dans la théories en construction. f(x)  fait parti du langage donc il désigne un élément, même si x n'est pas dans le domaine de définition de f. Dans ce dernier cas f(x) = o. Ainsi f(x) existe toujours. Cela ce fait en ajoutant un axiome qui est en faite une définition, la définition du domaine de f.

∀f,  ∀x,    x ∈ dom(f)  <=>  f(x) ≠ ο

Noter que les deux quantificateurs universelles portent sur le même ensemble, qu'est le monoïde. Cet axiome définie ce qu'est le domaine de f. Elle le définie en donnant le programme de la fonction caractéristque du domaine de f, et comme cela s'applique pour tout élément f, elle donne le programme de la fonction dom, qui appliqué à un élément f produit la fonction caractéristque dom(f), qui appliqué à un élément x produit la valeur logique f(x) ≠ ο. L'axiome du petit zéro se réécrit donc comme la définition de dom :

dom : f --> ( x --> (f(x) ≠ ο))

On peut alors considérer l'opérateur binaire retournant une valeur logique ainsi définie :

x∈f <=> f(x) ≠ ο

On identifie ainsi chaque élément du monoïde non seulement à une fonction mais également à un ensemble, l'ensemble de définition de la fonction. Et l'opérateur constitue une première approche d'une autre définition de la notion d'ensemble dit constructif.

L'axiome du petit zéro se résume en terme de contrainte, qu'à l'existence d'au moins un élément. La présentation de la structure s'enrichie d'un élément supplémentaire qu'est le petit zéro, et la structure devient un monoïde pointé de fonctions (M,°,o). A cette étape là, le choix de o n'a pas de signification particulière, c'est pourquoi la structure s'appelle monoïde pointé de fonctions. La signification est apporté plus tard par l'opérateur et sa définition. La présentation de la structure s'enrichie d'un élément supplémentaire qu'est l'opérateur , la théorie s'enrichie de sa définition qui est x∈f <=> f(x) ≠ ο, et la structure devient un monoïdes d'applications (M,°,o,∈).

6) Monoïde d'applications agissant sur lui-même

Un monoïde d'applications (M,°,o,∈).

Le langage s'enrichie et permet d'exprimer de nouveaux éléments, de nouvelles fonctions. Une classification apparait séparant en deux classes le monoïde : les fonctions standarts qui ne possèdent pas l'élément o dans leur domaine de définition, et les fonctions non-standarts qui possède l'élément o dans leur domaine de définition.

Il existe plusieurs niveaux d'égalité. Deux fonctions sont égales si elles ont un même programme, et elles sont seulement équivalentes si elles ont les mêmes résultats. On construit les classes d'équivalences. Le monoïde quotient (M,°,o)/<=> est encore un monoïde. Et dans ce monoïde, les fonctions équivalentes sont égales. On appellera cette structure un fonctoïde.

6) Fonctoïde

Un fonctoïde (F, o, ) possède 3 axiomes :

La fonction de domaine vide, est appelée le zéro 0, et peut toujours être ajoutée à F s'il n'est pas déjà présent. Nous avons :

∀x∈F,  0(x) n'est pas défini.

On ajoute le petit zéro o pour transformer les fonctions en application, sans savoir quel rôle exactement donner à la fonction o, mais au moins un rôle lui est possible, celui de la fonction de domaine vide. Il est ainsi présenti o=O.

∀f,  ∀x,    x ∈ dom(f)  <=>  f(x) ≠ ο

dom : F --> (F -->{Vrai, Faux})
          f --> ( x --> (f(x) ≠ ο))

7) Indifférentiation entre Appel et Composition

Une règle de simplification pertinente consiste a identifier l'appel et la composition. C'est à dire à poser que quelque soit x,y appartenant à F, x|y = x·y. En faisant cette hypothèse, l'opérateur d'appel devient associatif. L'opérateur de composition prend un sense plus large, x·y désigne l'image de x transformé par y, et désigne également la transformation composée, commençant par x suivie de y. En considérant x dans sa fonction d'élément de départ, nous avons x·f·g = x·(f·g) = (x·f)·g, qui peut également s'écrire avec la notation d'appel à la française (x)(f·g) = (((x)f)g).

Nous avons alors la propriété suivante. Quelque soit f,x,y appartenant à F :

f(x)(y)  =  f(x(y))

qui s'écrit explicitement de l'une des deux façons suivantes :

(f / x) / y  =  f / (x / y)
y | (x | f)  =  (y | x) | f

Le petit zéro est alors égale au zéro o = O. En effet si nous supposions le contraire, alors o étant différent de la fonction vide, admettrait dans son domaine de définition au moin un élément x, et nous aurions o(x) o. Mais l'associativité de l'appel entraine l'égalité suivante O(o(x)) = O(o)(x) = o(x) et comme par définition de O on a O(o(x)) = o on en déduit que o(x) = o ce qui est contradictoire.

8) Fonctoïde associatif

En intégrant cette dernière propriété dans le fonctoïde on obtient un monoïde (F,|) avec la propriété supplémentaire suivante appelée simplification unanime à gauche :

Quelque soit u,v appartenant à F, si quelque soit x appartenant à F on a x|u = x|v alors u=v:
    ∀u∈F  ∀v∈F  ∃x∈F  u=v ou x|u≠x|v

La propriété symétrique de simplification unanime à droite ∀u∈F  ∀v∈F  ∃x∈F  u=v ou u|x≠v|x, est alors également valide. Cette propriété est obtenue par la construction d'un monoïde dual (G, *) obtenu comme l'image de (F,|) par le morphisme φ suivant : φ(x) * φ(y) = φ(y | x), et on démontre que φ est bijectif et constitue donc un isomorphisme. La simplification unanime à droite entraine la simplification unanime à gauche et vis-versa.

---- 4 Décembre 2012 ----

 

 

 

 

 

5) Monoïde de fonctions

Prenons quelques fonctions unaires f, g, h que nous allons utiliser comme générateurs. Puis considèrons la cloture par composition que l'on note <f,g,h>, nous obtenons un monoïde de fonctions (<f,g,h>, ·).

Le monoïde de fonctions (<f,g,h>, ·) agit sur un ensemble ou d'une manière plus générale sur une catégorie qui peut être réduite à la réunion des domaines de définition des fonctions génératrices dom(f) ∪ dom(g) ∪ dom(h).

Les premières structures de fonctions unaires, simples et fondamentales, auront cette symétrie qui fait que que l'élément et la fonction sont indicernables, que l'on ne peut pas savoir si on parle d'une fonction ou d'un élément, que l'élément et aussi une fonction, et que l'on ne peut pas différencier une fonction s'appliquant à un élément d'une composition de fonctions. Le monoïde de fonctions primaire devra agire ainsi sur lui-même.

6) Elément neutre et la fonction identité

La fonction identité noté id, définie par (x-->x), de domaine de définition égale à la catégorie des éléments joue un rôle de ciment. Quelque soit un monoïde de fonction, la fonction identité restreinte à l'union des domaines de définition des fonctions génératrices du monoïde, peut toujours être ajouter au monoïde s'il elle n'est pas déja présente, et constitue alors sont élément neutre. Donc pour un monoïde de fonctions, l'élément neutre de domaine de définition minimal est une unique fonction, qui, si elle n'est pas déja là, peut toujours être ajouter au monoïde de fonction pour produire un monoïde unitaire de fonctions. Il s'agit d'une extension canonique de monoïde de fonction puisque nous ne faisons aucun choix arbitraire. (L'autre extention canonique possible consiste à ajouter s'il elle n'y est pas déja, la fonction identité)

Soit M un monoïde. Existe-t-il un élément neutre ?. Si un élément neutre existe, il est nécessairement unique, car si e1 et e2 sont des éléments neutres alors e1*e2 = e1 = e2. S'il n'existe pas d'élément neutre alors on peut en rajouter un en respectant les 2 axiomes (interne et associatif). L'élément neutre est noté 1, le monoïde obtenue est dit unitaire et possède un troisième axiome :

Il existe un élément neutre noté 1 : 1*x  =  x*1  =  x

C'est une extension toujours possible et unique à isomorphisme près, en conséquence l'ajout de cet élément n'apporte aucune information supplémentaire, ni n'entache la généralité du monoïde. Tout monoïde peut être rendu unitaire de façon unique à isomorphisme près, c'est à dire sans que nous ayons à faire de choix arbitraire autre que la seul volonté de le rendre unitaire. Il s'agit d'une extension canonique.

7) Théorie et langage

 

La théorie du Monoïde utilise un langage qui est décrit par sa présentation (M,*), un langage comprenant une fonction unaire M(.) jouant le rôle d'ensemble sous-jacent, et une fonction binaire *(.,.). Intuitivement, lorsque M(x)=vrai cela signifiera que x appartient à M et lorsque M(x)=faux cela signifiera que x n'appartient pas à M. L'ensemble est définie par une fonction calculable opérant sur la catégorie des éléments. Le paradox de Rusell est remplacé par une problèmatique relative à la calculabilité.

La fonction binaire * appliqué à un couple d'élément (x,y) retourne un troisième élément, qui s'il n'est pas définie, est définie de faite par la construction du terme libre x*y, c'est le pouvoir de construction du langage.

8) Extension de monoïde

Le monoïde (M,*) est une théorie incluse dans un langage et c'est aussi une réalisations mais le plus souvent on fera référence à une réalisation particulière onnue plus précisément, autrement dit qui peut être traduite en une théorie plus riche et dans le même langage mais éventuellement enrichie. La théorie du monoïde (M,*) est composé de 2 axiomes : l'opération * est interne et associative dans M. Une réalisations résulte de constructions antérieurs et peut contenir des propriétés non mentionnées dans la théorie tel que l'existence d'un élément neutre u par exemple ainsi que des éléments en dehors du langage tel que l'élément u et des propriétés les mettant en oeuvre.

L'extension d'un monoïde consiste à ajouter des éléments dans la structure et à compléter la table de multiplication. Lorsque le résultat est encore un monoïde on dit que l'extension est conservative. Une extension conservative d'une théorie T est une théorie T2 tel que l'intersection avec le langage de la théorie T est égale à la théorie T. Ces deux extensions sont les mêmes, seul le point de vue change, la première est vue du coté de la réalisation et la seconde est vue du coté de la théorie.

Implicitement une extension est conservative, et on parlera plutôt d'extension non conservative ou destructrice dans les autres cas.

On ajoute des éléments au monoïde en complétant la table de multiplication et en respectant la théorie du monoïde mais pas nécessairement les propriétés supplémentaires portées par une réalisation particulière. Ainsi un monoïde dont la réalisation possède un élément neutre u, peut être étendu en ajoutant un élément neutre supplémentaire e, faisant que le premier élément neutre u n'est plus un élément neutre dans le monoïde étendu, e*u = u*e = u. c'est une extension de monoïde en un monoïde unitaire mais ce n'est pas une extension de monoïde unitaire.

9) Tout monoïde unitaire est isomorphe à un monoïde de fonctions agissant sur lui-même par translation gauche (ou droite)

Pour enlever le caractère arbitraire de la construction du monoïde de fonctions, on montre que tout monoïde unitaire est isomorphe à un monoïde de fonctions. Cela se fait de manière canonique en faisant opérer le monoïde sur lui-même par translation gauche ou droite.

Soit un monoïde (M,*). Quelque soit l'élément m appartenant à M, la translation droite par m est la fonction (x-->x*m).

On définie la fontion φ, qui appliqué à un élément m de M, va produire la fonction (x-->x*m) correspondant à la translation droite de m :

φ = (m --> (x-->x*m))
φ(m) = (x --> x*m)
φ(m)(x) = x*m

On structure l'image φ(M) en ajoutant l'opération de composition · et on remarque que φ restreint à M est un isomorphisme de (M,*) sur (φ(M), · ). L'injectivité de φ sur M est assurée par la présence de l'élément neutre de M noté 1 et correspondant à la fonction identité noté id appartenant à φ(M), qui possède le domaine de définition englobant tous les autres et qui constitue le ciment du monoïde unitaire de fonctions.

φ(u*v) = φ(u) · φ(v)

(φ(M), · ) est donc un monoïde de fonctions isomophe à (M,*). On dira que φ fait opérer M sur lui-même par translation droite.

Pour retrouver la symétrie originelle, on identifie chaque élément m de M avec φ(m). Cette identification n'est possible que parceque φ restreint à M est un isomorphisme. Dés lors quelque soit m appartenant à M nous avons m = φ(m) = (x-->x·m), et quelques soient u et v appartenant à M, nous ne pouvons pas distinguer si u·v est une composition de deux fonctions ou une application de la fonction v sur l'élément u :

u·v = (x-->x·u)·(x-->x·v) = (x-->x·u·v)
u·v = u·(x-->x·v) = u·v = (x-->x·u·v)
u·v =1·u·v = v(u(1)) =(v°u)(1)

On ne peut pas distinguer si u est une fonction ou un élément, car il est les deux à la foi. De même on ne peut pas distinguer si v est une fonction se composant et s'appliquant, ou si c'est un élément qui obéït à l'opération de produit du monoïde, car il est les deux à la foi. De même pour l'élément u·v. Cela est dû à l'isomorphisme φ restreint à M

10) Langage de programmation impératif

Nos fonctions sont calculables, leur définitions sont donc des programmes, et lorsque le programme ne s'arrète jamais on dira que la fonction retourne l'infinit de Turing, une valeur singulière que l'on ajoutera à notre langage. Le langage de programmation sera inclus dans le langage initiale et formera le sous-langage de définission de nos fonctions unaires.

Une première approche consiste à partir du Brainfuck pour définir notre langage de programmation. Dans un premier temps on conçoit un calcul non parallèle, un processus de calcul série. Le processus comprend à un instant donnée une séquence de termes (U0,U1,U2,...Uk) qui constitue sa mémoire de taille finie mais non bornée (jouant le rôle du ruban pour une machine de Turing), un entier i appelé pointeur de données désignant un terme de la séquence, Ui, (jouant le rôle du curseur désignant une case du ruban), une séquence d'instructions fixées (V0,V1,V2,...,Vn) qui constitue le programme (jouant le rôle de l'automate), et un entier j appelé pointeur d'instruction désignant une instruction de la séquence, Vj, (jouant un rôle miroir du curseur mais pour désigner l'état de l'automate).

Les ressources temps et espaces sont à prendre en compte. Le programmes va utiliser du temps et de l'espace, les opérations occupent du temps et les termes occupent de l'espace.

Puis on va s'éloigner du Brainfuck en choississant un jeux d'instructions plus pratiques de tel sorte que la séquence d'instructions soit finalement un terme complexe d'un langage de programmation plus simple. On intègre la séquence dans le langage, la séquence de séquences est la réunion des séquences. On utlise des variables contenant des entiers i, j, k.... et des variables contenant des termes A,B,C.... On utilise l'opérateur d'affectation .←. ainsi que l'opérateur de condition .≡. retournant 1 ou 0, l'égalité de deux termes désignant l'égalité des mots dans leur forme et non des éléments qu'ils désignent. On utilise les fonctions arithmétiques sur les entiers qui peuvent être réduites à l'incrémentation et la décrémentation. On utilise la composition de termes dans le respect du langage et la décomposition de termes qui peut être réduite à l'extraction de la racine et de la séquence de ses fils. On utilise l'adressage indirecte sur une séquence S que l'on note Si. On utilise la condition if, la boucle for bornée, et la boucle while, qui représentent les 3 étapes majeurs d'enrichissement du langage de programmation.

Ne pouvons nous pas unifier termes et entiers, afin de n'avoir qu'un seul type de variable ? L'entier est définie par le 0 et l'opération successeur 1, de tel sorte que 6 = 1(1(1(1(1(1(0)))))) = 0·1·1·1·1·1·1, et il est aussi désigné par la composition de fonctions unaires 6 = 1·1·1·1·1·1 appelé notation en bâtons. Il est aussi défini en binaire par une composition de fonctions unaires 6 = 1·1·0 en prenant le bon endianess. Il faut néanmoins définir préalablement les élément 0 et 1 de façon adéquate.

....

 

11) La fonction

On privilègie le calcule opéré par la fonction pour définir la fonction elle-même. Et on appelle définition opératoire, la définition qui décrit uniquement le calcul opéré par la fonction sans préciser sur quoi elle s'applique. La fonction opératoire n'a pas de raison d'avoir un domaine de définition restreint, et nous pouvons choisire comme domaine de définition la catégorie des éléments. On choisie une conception de fonction non destructrice d'information, c'est le concept de définition libre qui complète celui de définition opératoire, et qui s'applique là où le terme calculé n'a pas de cadre défini, la fonction fait alors office de construction de nouveaux termes images, et de nouvelles structures images posées libres du fait de l'absence d'hypothèses.

Une fonction possède un domaine de définition qui peut être plus large qu'un ensemble. On ne peut pas considérer l'ensemble de tous les ensembles comme un ensemble à cause du paradox de Russel. Pour contourner cette difficulté on définie le concepte plus large de catégorie. La catégorie des ensembles contiendra tous les ensembles. Néanmoins les catégories ont des coutours plus incertain que ceux des ensembles car elles sont porteuses des paradox de Russel, elles sont d'avantage propositionnelles que objectuelles, d'avantage ondulatoires que corpusculaires. C'est pourquoi lorsque on évoque l'image d'une fonction f, on utilisera rarement l'image totale im(f) = f(dom(f)) qui constitue la plus part du temps une catégorie et non un ensemble, mais l'image d'un ensemble A par f, notée f(A) = f(A ∩ dom(f)) qui est lui-même un ensemble.

La fonction n-aire est une fonction unaire appliquée à des n-uplets d'éléments et dont le domaine est restreint au n-uplet d'éléments. En procédant à cette identification, on altère en rien la généralité mathématique et on simplifie le concepte de fonction en ne considérant que des fonction unaires. Cette simplification entrainerait une plus grande intéropérabilité. Souvent la simplicité entraine l'interopérabilité et reciproquement.

Néanmoins les connaissances que nous avons sur les algorithmes de calcul d'une fonction à plusieurs arguments, à savoir qu'une tel fonctions peut être évalué dans certain cas sans avoir la connaissance de tous ses arguments mais seulements de quelques uns d'entre eux, nous pousse à aller dans une autre direction, de maintenir un concept de fonction à plusieurs arguments, et nous pousse également à donner la possibilité de produire plusieurs résultats parallèlement qui puisse être utilisé comme entrés pour des fonctions différentes, car un calcul peut être mémorisé et réutilisé opérant ainsi un gain de temps et d'espace important par se mécanisme de calcul parallèle.

Les arguments sont appelés entrées de la fonctions (ou du programme) et les résultats sont appelées sortie de la fonction (ou du programme). La fonction vue comme un programme possède plusieurs arguments d'entré et plusieurs arguments de sortie, et est similaire à un neurone. La composition de fonctions devient un réseau de neurones. Il est plus facile de représenter un reseau de neurones par un graphe que par une suite de caractères.

Et une fonction est elle-même un réseau de neurones contenant d'autres fonctions. Peut-ton subdiviser indéfiniment les fonctions en sous fonctions. Assurément non puisque les ressources temps et espaces sont finies, certe non bornées mais finies. Il y a donc des fonctions indivisibles qui ne sont pas constituée d'un réseau de neurones, énumérons les.

 

 

5) Langage de programmation fonctionelle

Une seconde approche consiste à partir de la définition des fonctions récurcives

 

la formalisation de ce langage de programmation

 

Si on ne s'autorise aucune hypothèse autre que l'existance de l'élément e alors

les choix de construction sont relativement limité. Au départ il y a un élément e et la fonction appliqué à x peut selon que la condition c1 est vérifié retourner le terme t1 et que la condition c2 est vérifié retourner le terme t2 et ainsi de suite pour une liste finie de conditions.

 

 

Car l'axiome de choixterme t1 ou un autre terme t2 construit par le même langage. et peut être restreinte qu'a l'ensemble vide, à {e}ou à la catégorie des éléments. Puis ayant construit On peut choisire une fonction parmis :

(x-->e), (x-->e)|{e}, (x-->e)|{e, (x-->e)}, (x-->e)|{e, (x-->x)}..., (x-->(x-->e)), (x-->(x-->x)|{e, (x-->e)})|{e, (x-->x)}....

La liste complètes peut être décrite dans un langage d'opérateurs, et le terme le plus simple semble être (x-->e) ou (x-->e)|{e} qui est égale à (x-->x)|{e} également noté id|{e}. Nous pourrions identifier e à cette fonction : e = (x-->e), et nous ferions le mauvais choix. Car le choix qu'il faut faire est dicté par le principe du langage libre. La fonction doit être libre. dom(e) doit être la catégorie des éléments et quelque soit un élément x, e(x) désignera un élément à priorie distinct de tous les autres, jusqu'a preuve du contraire, que l'on notera e(x). Mais me diriez-vous, comment notons-nous cette fonction, pourquoi ne l'avons nous pas repérée en listant les fonctions que nous pouvions écrire ? Si e n'est pas une fonction dans le langage précédent alors nous l'unifions à la fonction libre correspondante : e = (x-->e(x)). Nous utilsons un opérateur supplémentaire, l'opérateur d'appel, x@e = e(x). Le système nous met des oeuillères et souvent nous bride. Il faut alors savoir se ratacher à la liberté principielle du langage pour transgresser les règles de construction, sortire du sytstème par la création. Le langage est en cela un moyen d'émancipation (et ce qui ne peut être dit n'est pas intelligible).

Le langage de construction de fonctions comprend alors deux opérateurs : l'opérateur de définition de fonction .-->. et l'opérateur d'appel .@. Noter que l'opérateur de définition de fonction unaire prend comme premier argument une variable muette. Cela veut dire une variable qui n'a jamais été utilisé au paravant et qui va se comporter dans le deuxième argument comme un élément rajouté au langage. En cela l'opérateur --> à comme premier argument un élément étrangé au langage et comme second argument un terme du langage augmenté de l'élement étrangé.

dont le premier argument est une variable muette, et le second argument un terme de notre langage augmenté de la variable muette utilisée comme un élément supplémentaire,qui n'est pas en générale associatif x@f = f(x), g(f(a)) ≠ (g(f))(a) (x@f)@g ≠ x@(f@g).

 

 

 

 

 

 

7) Le programme

La programmation impérative va gérer une mémoire constitué par une séquences d'éléments en cours. Le programme nécessaire pour décrire un réseau de neurones comprend 3 types opérations : le séquencement noté + qui permet de construire une séquence, l'application · qui permet d'appliquer les fonctions, et le nommage qui permet de nommer un résultat intermédiaire, représenté par le symbole § suivi d'un nom de variable.

a revoir

x + y + z produit le triplet (x,y,z). (x + y) · z correspont à l'application de la fonction z sur quelques éléments de la séquence en cours. On choisira une convention de tel sorte que l'associativité soit respectée, c'est à dire tel que (x + y) · z = x + (y · z). Cela est possible en prenant les dernier éléments de la séquence comme entrées de la fonction z, et en les remplaçant par la séquence de résultats de la fonction z. et s'il n'y a pas suffisament d'éléments dans la séquence, l'application de la fonction z va produire une fonction. Par exemple si z est d'arité 3, x + y · z désignera la fonction t-->z(t,x,y). Et l'application x · (f + y) sera égale par définition à (x · f) + y. Par exemple x+y·f§e+x+e·g est égale à g(f(x,y),x,f(x,y)).

On a ainsi définie le concept de séquence. La séquence est une liste d'éléments d'arité diverse. La séquence est caractérisé par un couple d'arités, l'arité d'entré qui correspond à l'arité du prremier élément de la séquence et l'arité de sortie qui correspond à la taille de la séquence.

Arité
Exemple
Déscription
(0,0)
ε
Expression symbolique de la séquence vide, Ce n'est pas un élément.
(0,1)
x
Un élément. la séquence contenant un élément est identique à l'élément : (x) = x
(0,2)
(x,y)
Une séquence de deux éléments
(1,0)
x-->ε
Fonction symbolique qui appliqué à un élément retourne la séquence vide.
(1,1)
x-->f(x)
Fonction unaire retournant un élément.
(1,2)
x-->(f1(x),f2(x))
Fonction unaire retournant une séquence de deux éléments.
(2,0)
(x,y)-->ε
Fonction symbolique qui appliqué à une séquence de deux éléments retourne la séquence vide.
(2,1)
(x,y)-->f(x,y)
Fonction binaire retournant un élément.
(2,2)
(x,y)-->(f1(x,y),f2(x,y))
Fonction binaire retournant une séquence de deux éléments.

(x,y) + (z,t) = (x,y,z,t)

Si z est d'arité 0 : (x,y) · (z,t) = (x,y,z,t)
Si z est d'arité 1 : (x,y) · (z,t) = (x,z(y),t)
Si z est d'arité 2 : (x,y) · (z,t) = (z(x,y),t)
Si z est d'arité 3 : (x,y) · (z,t) = w-->(z(w,x,y),t)
Si z est d'arité 4 : (x,y) · (z,t) = (v,w)-->(z(v,w,x,y),t)

 

La séquence composé d'un élément d'arité (a1,b1) et d'un élément d'arité (a2,b2) produit un élément d'arité (a1,b1+b2)

La composition d'un élément d'arité (a1,b1) et d'un élément d'arité (a2,b2) produit un élément d'arité

 

une piles d'éléments numérotés de 0 à n et une pile d'instructions numéroté de 0 à m, et le langage minimaliste utilisé sera un dérivé du brainfuck.

7) Le langage de construction des fonctions

On décrie un processus de construction de toutes les fonctions calculable. On en recherchons les fonctions génératrices et leurs processus d'énumération et on formalise ainsi un langage de construction.

L'approche constructive formelle va ordonner chronologiquement les constructions dans une génèse. Au départ de la génèse, il n'y a ni hypothèse ni construction, et le domaine de définition d'une fonction est soit l'ensemble vide soit la catégorie des éléments. (Noter que la catégorie des éléments est plus vaste que la catégorie des ensembles, car un ensemble est également un élément). Pour qu'il y ait d'autre alternative il faut procéder à des constructions qui seront faites dans les étapes suivantes. Le langage n'est pas augmenté mais on s'autorise d'utiliser des termes de plus en plus complexe à chaque étape de la génèse. La première étape permet de produire les trois fonctions : 0, (x-->0), (x-->x) :

La fonction vide, notée 0, est la fonction dont le domaine de définition est vide, la fonction de définition (x-->0) est constament égale à 0, et la fonction identité est définie par (x-->x).

Délors nous avons construit trois éléments 0, (x-->0), (x-->x), qui peuvent être utilisés pour définir d'autres domaines de définition, ainsi que pour définir éléments par éléments une fonction. La seconde étape permet de produire des fonctions f dans lequel on a retiré un élément u du domaine de définition, des fonctions f dans lequel on a ajouté un élément u au domaine de définition et tel que l'image f(u)=v .

Les fonctions peuvent être définies par un ensemble de couples. Nous avons :

f = {(x,f(x)) / x ∈dom(f) }

Mais la fonction tel que nous la concevons peut contenir une information supplémentaire, une méthode de calcul plus efficace. Il s'agit d'une fonction physique qui comprend l'algorithme de calcul, le programme, en opposition à la fonction mathématique qui ne s'intéresse qu'au résultat. Ainsi la fonction (x-->x) qui est identique à la fonction définie par la catégorie des couples {(x,x)}diffère dans la méthode de calcule implicitement évoquée, la première donne le résultat immédiatement tandis que la seconde va rechercher à l'aide du moteur générant tous les éléments, l'élément x correspondant à l'entré de la fonction. Nous voulons donc formaliser le programme de la fonction et définir ainsi un langage de programmation.

langage de programmation impératif.

Les deux opération précédente peuvent être traduite par les opération de programmations suivantes :

exclus(u) · f

si u alors v

La seconde étape reprend la théorie des ensembles mais en la plaçant dans un cadre plus large des listes à transformation près appelées atomes.

 

La fonction qui produit le singleton est définie par (x-->{x})

La fonction qui produit le couple définie par (x-->(x,x))

 

Le langage, pour créer la fonction id, utilise l'opérateur --> de définition de fonction libre, ainsi qu'une variable muette x représentant l'élément sur lequel la fonction s'applique.

 

Le concept de définition de fonction libre (ou d'une manière plus générale de définition opératoire), se diffère de la définition habituelle de fonction dans les cas ou le terme calculé ne se trouve pas dans un cadre défini, la fonction fait alors office de définition et de construction de termes images et de structures images posées libres du fait de l'absence d'hypothèses. La fontion libre n'a pas de raison d'avoir un domaine de définition restreint. Et nous pouvons choisire pour ces fonctions libres un domaine de définition non restreint égale à la catégorie des éléments.

Par exemple, posons que l'opération * est binaire (c'est à dire que c'est une fonction qui s'applique à deux éléments quelconques pour en produire un troisième) et que m est un élément. Puis définissons la fonction f : x-->x*m. Le contexte contient comme seuls hypothèses que * est une opération binaire et que m est un élément. Le contexte a enrichit le langage de deux opérateurs constants que sont * et m, et a ainsi permis que nous puissions définire librement de façon opératoire la fonction f : x-->x*m. Le domaine de définition de la fonction est la catégorie des éléments. Et l'élément f(f(m)) = (m*m)*m a été construit en appliquant deux fois de suite la fonction f à l'élément m. Vous noterez la différence entre l'expression (m*m)*m qui est un mot du langage {m, *(.,.)} et l'élément correspondant qui est un concept mathématique, le mot désignant l'élément. Et en l'absence d'hypothèse, chaque mot distinct désigne un élément apriorie distinct. Les éléments désignés par aucun mot du langage sont indisibles et donc inopérant pour nous, ou dit d'une autre manière, sont en dehors de notre intelligibilité.

Si le contexte contient comme hypothèses suplémentaire que (M,*) est un monoïde et que m appartient à M, alors le domaine de définition de la fonction x-->x*m est encore la catégorie des éléments. Et on peut identifier les éléments de M à leur translation droite sur M et identifier l'opération * restreinte à M à la composition de fonctions unaires. L'élément f restreint à M est égale à m. Et l'élément f(f(m)) = m·m·m appartient à M. Vous noterez la différence entre l'expression m·m·m qui est un mot du langage {m(.), 1} et l'élément correspondant qui est un concept mathématique, le mot désignant l'élément. Et en l'absence d'hypothèse, chaque mot distinct désigne un élément apriorie distinct. Les éléments désignés par aucun mot du langage sont indisibles et donc inopérant pour nous, ou dit d'une autre manière, sont en dehors de notre intelligibilité.

 

. Et si nous posons un élément e n'appartenant pas à M alors f(f(e)) = e*m*m est un éléments sur lequel nous n'avons pas de connaissance précise autre qu'il est le produit d'un élément quelconque et d'un élément de M, et comme nous n'avons pas de connaissance sur ce produit cela correspond à un couple.

Apriori la définition opératoire de la fonction va déterminer son domaine de définition en fonction d'elle même et des domaines de définition des fonctions dont elle fait appel. On peut restreindre volontairement le domaine de définition, mais dans quel intérêt ?

 

 

7) Le langage

Quelle sont les fonctions calculables que l'on peut définire dans ce contexte constitué d'un monoïde (M, *) et de quelques éléments m1, m2.... de M ? C'est une question de langage car la fonction est définie grace à un langage. Pourtant la notion de calculabilité semble être indépendante du langage..., et pour une bonne raison, c'est qu'elle dépend de l'arithmétique, d'un langage rudimentaire qui contient l'arithmétique.

La réponse consiste à écrire toutes les fonctions calculables à partir de la seul connaissance d'un monoïde et de quelques éléments du monoïdes, et de formaliser un langage permettant cela, le langage de base de l'arithmétique augmenté de quelques objects du contexte.

Le contexte est l'ensemble des hypothèses, un monoïde (M,*) et quelques éléments m1, m2... c'est à dire exactement les quelques axiomes suivant :

Axiome 1 : Il existe un ensemble M
Axiome 2 : Il existe une opération binaire *
Axiome 3 : si x ∈M et y ∈M alors x*y ∈M
Axiome 4 : si x ∈M et y ∈M et z∈M alors (x*y)*z = x*(y*z)

l'axiome 4 peut être rendu plus simple et plus fort, sans influence sur le monoïde, en posant l'associativité sur la catégorie des éléments :

Axiome 4 : (x*y)*z = x*(y*z)

 

 

8) Les fonctions inversibles

Une fonction est inversible sur un ensemble M ssi restreinte à M elle est injectives. L'applicaton d'une fonction injective sur des éléments de M n'entraine aucune perte d'information. Si les fonctions génératrices sont inversibles alors tous les fonctions de la structures sont inversible, et la structure devient un groupe, et possède un quatrième axiome (inverse)

Axiome 4 (inverse) : x * x-1  =  x-1 * x  =  1

Chaque élément x de M admet un symétrique noté x-1 dans M tel que x * x-1 = x-1 * x = 1

 

La composition ° des application affine n'est pas commutative. Pour l'opération de composition on utilise la notation anglaise (f°g°h)(v) = f(g(h(v)))). La notation française v·f·g·h = (h°g°f)(v) = h(g(f(v))) permet d'écrire de gauche à droite la succession des transformations dans le même ordre : v --> v·f --> v·f·g --> v·f·g·h

Lorque deux élément u, v ne commutent pas, on définit un commutateur [u,v] comme ce par quoi il faut composer u ° v pour obtenir v ° u. Nous avons par définission (notation anglaise active) :

[u,v] ° u ° v  =  v ° u

Attention, le commutateur et les coordonnées polaires utilisent les mêmes crochets [,]. Aussi on laisse le soin au contexte de déterminer lequel il s'agit. Le commtateur possède les propriétés suivantes :

[u,v]  =  v ° u ° v -1 ° u -1
[u,v]-1  =  [v,u]
[u, a ° b]  =  [u,

 

le commutateur [A(r,t), A(r',t')] est égale par définition à