K° = {a,b,k(.,.)}°
H 
L°-->K°
H(a) = a
H(b) = b
H(f) = x-->h(x,a)
H(g) = h
Le langage comptrend 3 genres de langage que sont, 1- la donnée, 2- le programme, 3- la théorie. L'idée consiste à formaliser ces trois genres de langage petit à petit en construisant à la fois leur mots, leurs transformations et leurs propriétées, qui constituent un exemple d'eux-mêmes, le mots étant une donnée, la transformation étant un programme et la proriété étant une théorie. La construction se fera sans privilègier aucune des trois branches. La discution parcourra une spirale en partant du concept de langage et en passant en revue donnée-programme-théorie-donnée-programme-théorie..., pour ainsi rester toujours en équilibre entre les trois concepts. Mais sans doute, le plus important consistera à n'utiliser en premier dans la construction, que les seuls propriétées topologiques liés aux concepts d'échange d'informations, de transmission, de flux, d'atome, de lieu et de temps. Cela garantira une approche générale, équilibrée, la moins arbitraire, la plus auto-interopérante, et finalement la plus proche de l'intuition explicative.
Le principe d'une quantification de tout échange d'information faisant qu'une transmission se concrétise en un flux d'atomes, nous amène tout naturellement à présenter un programme sous forme d'un graphe telle qu'une machine de Turing, et nous amène à présenter une mémoire comme une succession numéroté de mémoires.
La donnée contient de l'information en quantité finie.
Le langage le plus simple pour exprimer une donnée est le langage d'alphabets {0,1} dit langage binaire, ou bien le langage d'opérateur {0, S(.)} dit langage de Péano. D'un point de vue algorithmique, le langage de Péano est plus simple, puisqu'il met oeuvre la méthode de comptage par bâtons.
Une donnée est un mot d'un langage.
La données ne peut être séparée de son langage, mais peut être traduite d'un langage en un autre, et peut acquerir ainsi une certaine autonomie par rapport au langage. La traduction est un programme qui appliqué à un mot du premier langage produit un mot du second langage. La donnée est toujours exprimée dans un langage de tel sorte qu'il est judicieux d'intégrer une référence au langage à la donnée. Ainsi une donnée possèdera un langage. L'autonomie de la donnée se concrétise partiellement par l'ensemble de ses propriétés qui sont conservées lors de ses traductions. Les propriétés correspondent aux théorie, et les traductions qui sont des transformations appellées morphismes, correspondent aux programmes.
Les mots du langage de Péano sont identifiés aux entiers naturels. Par exemple S(S(S(0))) est identifié à l'entier 3. N désigne l'ensemble des entiers naturels. N ={0,S(.)}°.
Toute donnée peut être codée en un entier par le biais d'un codage de son langage L, c'est une application totalement calculable qui transforme un mot du langage L en un mot du langage N, où N est à la fois le langage de Péano et l'ensemble des entiers naturels. Le codage doit être injectif, c'est à dire que deux mots différents doivent avoir des codes différents. Autrement dit, un codage est une application injective totalement calculable de L vers N.
La donnée peut être stockée, transmise, dupliquée. On introduit ainsi une notion d'espace, qu'est le lieux de stockage, et le canal entre émetteur et destinataire. La transmission n'est pas instantanée, elle se fait donc sous forme d'un flux que l'on quantifie en atomes. La donnée est transmise sous forme d'un flux d'atomes. On introduit ainsi une notion de sens du temps, qu'est l'ordre chronologique des atomes dans la transmission, et une notion de taille des données en nombre d'atomes. Puis la donnée est mémorisée dans l'ordre de sa transmission, dans une succession de mémoire numérotée
Dans un langage de caractères, les caractères constituent les atomes, et dans un langage d'opérateur, les opérateurs constituent les atomes. La taille d'un mot est égale à son nombre d'atomes. Par exemple, les mots "abba" et f(a,s(a)) sont de taille 4.
Les langages de caractères et les langages d'opérateurs vont nous servir de langage de base. Le langage d'opérateurs se plonge dans le langage de caractères correspondant, en appliquant la logique polonaise. Cela revient à ne pas mentionner les parenthèses. Ainsi le mot de Péano S(S(S(0))) se note également SSS0. L'alphabet regroupe les différents atomes. L'aphabet d'un langage d'opérateur est l'ensemble des opérateurs mentionnés dans la présentation du langage. L'alphabet du langage de Péano {0,S(.)} est {0, S}.
La transmission d'une données se fait selon un protocole de bas niveau. Une fonction importante de ce protocole est d'informer le destinataire de la fin de la transmission. Dans un langage de caractère cela se fait par l'envoi d'un atome particulié, un meta caractère "$", indiquant la fin de la transmission. Dans un langage d'opérateur, lorsque le mots transmis est clos, la transmission est nécessairement terminée, et il n'y a pas apriori besoin de méta caractère de fin de transmission.
Par exemple, dans le langage de caractère {a,b}, le flux de caractère "ab" désigne un mots commençant par "ab" mais indique que la transmission n'est pas terminée et que le mot peut contenir éventuellement d'autres caractères suivants. Le flux "abba$" désigne le mots "abba" et indique que la transmission est terminé.
Par exemple, dans le langage {a,b,s(.),f(.,.)} le flux d'opérateurs "fsa" désigne un début de mot f(s(a),.), où le symbôle point désigne une partie non encore transmise du mot. Les symbôles points se trouvent toujours groupés à la fin du mot sur sa droite, et nous informent que la transmission n'est pas terminée et que le mot contiendra d'autres mots qui remplacerons ces points.
Il y a trois types de transmission, ou de flux :
Pour le langage de caractère, le flux fini est un mot, le flux fini infini est un mot dont on est jamais sure qu'il ne s'agisse pas en fait d'un début de mot qui sera complété, et le flux infini est une succession infinie de caractères. Pour le langage d'opérateur, le flux fini est un mot clos, le flux fini infini est un mot non clos dont on est jamais sure qu'il ne ne soit pas complété et achevé plus tard, et le flux infini est une composition infinie d'opérateurs jamais close.
La transmission d'un flux infini de caractères satisfaisant à la syntaxe du langage permet de définir des mots de taille infinie, étendant ainsi le langage au mot infini. Il en est de même pour les flux infini d'opérateurs.
Les flux finis sont noté A*, où A est l'alphabet du langage, et où * désigne l'opération de Kleene. Les flux finis ou infinis calculables d'alphabet A sont noté A**, où ** désigne l'opération de Kleene étendue. Les suites formelles infinies de caractères n'y font pas partie, seuls celles qui sont calculables peuvent en faire partie. La cardinalité de l'ensemble des suites fomelles de caractères est celle du continu. L'ensemble des suites calculables infinies de caractères, est dénombrable et même plus, énumérable, comme le sont les programmes de taille finie.
La calculabilité est une notion relative, c'est à dire qu'elle peut s'étendre si on acquiert la faculter d'évaluer quelques fonctions non calculables, et que son principe s'applique toujours. S'il existe des fonctions non calculables posés comme des procédés effectifs qui nous sont concédés, alors ceux-ci complètent notre capacités de programmation et d'expression, et élargissent notre notion de calculabilité en redéfinissant ainsi nos limites mais certainement pas en les suppriment.
De même pour un langage d'opérateurs tel que L={a,b,s(.),f(.,.)}, le langage des compositions closes finies se note L° où ° designe l'opération de cloture, tandi que le langage des compositions closes finies ou infinies calculables se note L°°, où °° designe l'opération de cloture étendue, il comprend L° et toutes les compositions infinies d'opérateurs terminales-closes (c'est à dire ou toutes les place disponnibles se situe à la droite du mot, et qui sont donc de faite closes puisque la séquence d'opérateur est infinie), et qui sont calculables. Par exemple s(s(s(s(s(s(....)))))) appartient à L°°.
Nous appellerons paramètre, une donnée de taille bornée. Cela signifit que la borne de la taille du paramètre est une information préalablement connue, par l'émetteur ou le destinataire ou par une troisième entité ?.... Le paramètre n'est qu'un paramètre que pour celui qui connait cette information préalable et qui décide de l'exploiter comme tel.
---- 9 Décembre 2012 ----
Dans un langage de caractère, on définie la taille générique, ou quantité d'information générique, d'un mot, comme la quantité d'information minimale exprimée en bits, nécessaire pour mémoriser ce mot sans connaissance préalable autre que l'alphabet de son langage. Elle est égale au nombre de caractère mupltiplier par la quantité d'information générique du caractère. Et la quantité d'information générique du caractère est égale au logarithme en base 2 du nombre de caractères distincts dans l'alphabet du langage. Par exemple les mots "abba" et "aaaa" de langage {a,b,c,d} ont comme taille générique 8 bits. Cela signifie qu'il est nécessaire de disposer d'un octet de mémoire (8 bits) pour mémoriser un tel mot avec comme seul connaissance préalable, l'alphabet {a,b,c,d}.
Dans un langage d'opérateur, la quantité d'information d'un mot est plus petite que celle correspondant à son langage de caractère. Cela est dû au faite que les mots non clos et les séquences de mots sont retirés des possibilités. Le calcul est plus complex et la notion de taille générique est alors moins pertinante.
La données est quantifié en atomes, et une succession finie d'atomes constitue un mot ou un flux, le flux poouvant contenir une succession infinie d'atomes. On définie un pipeline comme étant un tube dans lequel circule un mot ou un flux d'atomes dans un sense unique, qui part d'un point de sortie d'un processus et va vers un point d'entré d'un autre processus.
Le pipeline peut se ramifier produisant des copies du mot ou du flux allant vers des points d'entré d'autres processus.
Le processus est un programme en cours d'exécution. Il contient une mémoire interne, non bornée et initialement vide, capable de mémoriser une donnée de taille finie non bornée, et possède des périphériques d'entré et de sortie qui sont raccordés à l'aide de pipelines à des périphériques d'entré et de sortie d'autres processus, en respectant le sens des pipelines.
Le pipeline regroupe les propriétés spatiales et temporelles d'un flux. Il constitue une mémoire tampon, une file où le premier atome émit sera le premier atome reçu.
Le processus regroupe les propriétés spatiales et temporelles du calcul séquentiel. Il modifit sa mémoire interne, lit sur ses périphériques d'entré et écrit sur ses périphériques de sortie. Le procéssus éxécute son programme de façon séquentiel, c'est à dire que le programme détermine un unique cheminement (ou trace d'éxécution) qui est la liste des actions éxécutées dans l'ordre par le processus, qui change sa mémoire interne, lit les informations des périphériques d'entrées en dévorant les atomes dans l'ordre d'arrivé dans le flux, et écrit des informations sur les périphériques de sortie en engendrant des atomes et en les ajoutant dans l'ordre de leur création dans le flux.
Un programme est une donnée.
Pour exprimer un programme, on peut utiliser le même langage, puisqu'un programme est une donnée. Néanmoins on entend par langage de programmation d'avantage qu'un simple langage décrivant une donnée. Le langage de programmation permet de décrire un programme, précise comment il fonctionne, et contient donc une partie de son implémentation.
Un programme peut être éxécuté par un ou plusieur processus à la fois simultanément ou non ou de façon décalé, soit à n'importe quel moment, dans des contextes différents, le contexte étant les entrés du processus.
On se restreint aux programmes qui ne mettent pas en oeuvre d'éxécutions parallèles physiques (appelé calcul parallèle) mais seulement des éxécutions séquentielles physiques (appelé calcul séquentiel), c'est à dire que son éxécution par un processus suit un unique cheminement (ou trace d'éxécution) qui est la liste de toutes les opérations éxécutées dans l'ordre par le processus. (Cela n'empêche pas l'éxécution parallèle logique, une simulation du calcul parallèle). Cela a pour conséquence que l'on peut remplacer le programme et un contexte (l'ensemble des information transmise par les péripherique d'entré, sur lequel on veut executer le programme) par son cheminement qui se comporte comme un programme sans entré et sans boucle, à part qu'il peut être de taille infinie.
Les opérations élémentaires que peut faire un processus sont de 3 sortes : modifier sa mémoire interne, lire des périphériques d'entrées, et écrire sur des périphériques de sortie.
Le cheminement s'exprime dans un langages de programmation impérative, c'est à dire composé d'action agissant sur la mémoire interne et externe. Il est donc naturel de commencer par le langage de programmation impérative pour explorer les différents langages de programmation possibles.
Dans l'execution d'un cheminement par un processus, il existe un curseur qui indique une position dans le cheminement, l'instruction en cours, et qui est appelé compteur d'instruction, et qui fait partie de la mémoire interne du processus, et qui est incrémenté à chaque instruction du cheminement pour désigner l'instruction suivante.
Le programme est similaire au cherminement et se présente comme une suite finie d'instructions. Il se différencie du cheminement, évidement parcequ'il est fini et possède des entrées, mais substentiellement parcequ'il peut modifier le compteur d'instruction autrement qu'en l'incrémentant. Les instructions agissant sur le compteur d'instruction autrement que part sa poste incrémentation naturel, sont dites instructions de saut ou de boucle.
Le compteur d'instruction désigne l'instruction en cours.
On restreint les instructions de saut modifiant le compteur d'instruction aux seul boucles while (implémentant un mécanisme de pile d'appels while). La possibilité de calcul est toujours celle d'une machine de Turing.
3.1) La topologique des cheminements du programme
Il existe une catégorie de programmes dont on est sûre qu'ils s'arrêtent en un temps fini, parceque quelque soit les mots d'entrés, leur éxecution leur impose un cheminement où toutes les boucles rencontrées sont soumisent à des bornes strictement décroissante et qui s'arrètent lorsque la borne est à zéro. Ils sont appelés programmes primitifs récurcifs. Noté que le processus qui éxecute ce programme peut ne pas s'arréter s'il possède un flux d'entré qui ne se termine pas, l'arret est assuré que s'il n'y a que des mots d'entrés.
Le cheminements
3.3) Langage impératif "Brainfuck" avec des cellules d'un bit.
On définie un langage de programmation dans le cas d'une entré simple et d'une sortie simple. Ce langage est constitué de 7 instructions :
| > | Incrémente le pointeur (le déplace vers la droite d'une cellule). |
| < | Décrémente le pointeur (le déplace vers la gauche d'une cellule). |
| b | Bascule la valeur de la cellule pointée. |
| > | Sortie de la valeur de la cellule pointée |
| < | Entrée d'une valeur dans la cellule pointée |
| [ | Saute à l'instruction après le ] correspondant si la cellule pointé est à 0. |
| ] | Retourne à l'instruction après le [ si l'octet pointé est différent de 0. |
On définie un langage de programmation dans le cas d'une entré simple et d'une sortie simple. Ce langage est constitué de 7 instructions :
| > | Incrémente le pointeur (le déplace vers la droite d'une cellule). |
| < | Décrémente le pointeur (le déplace vers la gauche d'une cellule). |
| b | Bascule la valeur de la cellule pointée. |
| > | Sortie de la valeur de la cellule pointée |
| < | Entrée d'une valeur dans la cellule pointée |
| [ | Saute à l'instruction après le ] correspondant si la cellule pointé est à 0. |
| ] | Retourne à l'instruction après le [ si l'octet pointé est différent de 0. |
Les langages utilisées sont dans un premier temps les langages de caractère et les langages d'opérateur simple.
2.1.1) Les n-uplet de données
Si on considère n données écrites dans n langages L1, L2, L3..., Ln, cela correspond à une donnée écrite dans le langage produit directe L1 L2 L3.... Ln. Le produit directe de langages correspond à l'opération de concaténation et est noté par un caractère blanc.
2.1.2) Les flux de données
On considère également le concept de flux de données. C'est une succession de données, produites par un programme qui peut être sans fin. Cela correspond à une donnée écrite dans le langage L* ou L**, où L désigne le langage d'une donnée, et * désigne l'opération de Kleen et ** désigne l'opération de Kleen étendue. Le concept de flux introduit la notion du temps. Il existe alors 3 type de flux, les flux finis, les flux finis infinis et les flux infinis. Les premiers sont ceux pour lesquels le programme s'arrète au bout d'un temps fini, produisant évidement un nombre fini de données. Les seconds sont ceux donnants un nombre fini de données mais tel que le programme ne s'arrète jamais de tel sorte que l'on ne sache jamais s'il y a d'autres données qui vont suivrent ou non. Les troisièmes sont ceux produisant une suite infinie de données et dont le programme ne s'arrète évidement pas. Il ne s'agit pas d'une suite formelle infinie (la cardinalité de l'ensemble des suites fomelles est celle du continu), mais d'une suite calculable infinie (l'ensemble des suites calculables infinie L** est dénombrable comme le sont les programmes de taille finie).
2.2) Langages composés
On ajoute aux opérations de concaténation, de Kleen et de Kleen étendue, par analogie au langage de caractères régulier, les opérations d'union, d'intersection, de complément et de différence.
9) Le quotientage
On pose des règles de simplification. Elles sont écrites dans un langage enrichie de quelques variables d'arité nulle x,y,z... et de l'opérateur "=" de type propositionnel. Elles sont regroupées dans un ensemble finie T appelé théorie. La théorie réduit la structure, c'est pourquoi on parlera de théorie de la structure, le langage restant libre. Les règles de simplification rendent équivalent des mots entre eux et forment ainsi des classes d'équivalence de mots, une classe par élément, et la structure en est l'ensemble et s'appelle l'ensemble quotient.
L'opération de quotientage consiste donc à ajouter des règles de simplification regroupées en une théorie T, rendant égaux certain mots entre eux, et à construire la structure des classes d'équivalences de mots, la structure engendrée par L réduite par T est notée :
< L / T >
Elle possède comme ensemble sous-jacent, l'ensemble des classes d'équivalence des mots de L°0 selon T, qui constitue une partition de L°0. La relation d'équivalence est définie comms suit : Quelque soit x et y appartenants à L°0, si il existe une démonstration que x = y à partir de la théorie T, alors x est en relation avec y, sinon on fait le choix de la structure la plus libre possible et on considère que x n'est pas en relation avec y, c'est à dire qu'ils désignent deux éléments distincts. En résumé : Pour tout mots x et y appartenants à L°0, x et y sont dans la même classe d'équivalence, si et seulement si : T |— x = y.
Par exemple la structure < a,b,f(.) / f(f(x))=x > possède l'ensemble sous-jacent de 4 éléments suivant :
{{a, f(f(a))...}, {b, f(f(b))...}, {f(a), f(f(f(a))))...}, {f(b), f(f(f(b)))...}}
Chaque éléments est une classe d'équivalence de mots de L°.
Calculabilité :
Cette relation d'équivalence entre mots de L°0, x et y, que l'on note richement par T |— x = y, est calculable, et il existe un algorithme de calcule canonique et général décrit au §20 qui construit toutes les démonstrations possibles faites à partir de T, et qui construit ainsi toutes les propriétés démontrables à partir de T. Cet algorithme énumère toutes les propriétés T-démontrable.
Les propriétés sont écrites dans le langage propositionnel constitué du langage d'opérateur simple (L union {x,y,z...})° et de l'opérateur "=" de type propositionel.
La relation d'équivalence T |— x = y est calculable mais pas totalement, c'est à dire qu'elle peut produire l'infini de Turing. Et dans le cas générale, elle produit l'infini de Turing à chaque fois qu'il n'y a pas de démonstration de x=y à partir de T. Les classes d'équivalence sont alors dites inséparables, on ne peut prouver qu'elles sont distinctes.
L'approche est alors différente. Notre interpreteur est une machine et ne possède qu'une apréhension partielle de la relation d'équivalence : Il n'a intégré qu'un nombre finie de propriété T-démontrable. Son niveau d'apréhension pourra être augmenté, mais restera toujours partiel, car notre interpreteur étant une machine, il ne peut appréhender qu'un nombre finie de données. Dans les cas résolvables, on peut supposer qu'à partir d'une taille suffisament grande, les T-démonstrations n'apportent pas de nouvelles égalitées. Les classes d'équivalences sont alors séparées et la relation d'équivalence est totalement calculable.
Les éléments d'arité non nulle :
La structure < L / T > admet également des classes d'équivalences d'opérateurs d'arité non nulle. Deux opérateurs sont dans la même classe si et seulement si quelque soit leurs opérandes, la classe de leur image est identique. Les classes d'équivalence des opérateurs de <L> constituent les opérateurs de <L / T>. Dans le cas générale ils sont également inséparables, c'est à dire que l'on ne peut prouver que deux tels opérateurs de même arités sont distincts.
On peut répéter l'opération de quotientage, et nous avons : < L / T1 / T2 > = < L / (T1 et T2) > où l'opération logique "et" coïncide avec l'opération d'union.
9.1) La représentation des classes d'équivalences
Pour des raisons pratiques, on cherche une représentation des classes d'équivalence. C'est à dire que l'on cherche une application F totalement calculable définie sur L° qui identifie de façon unique la classe d'équivalence du mot.
C'est à dire que quelque soit m et n deux mots de L°0, et quelque soit u et v deux opérateurs 1-aire de L, et quelque soit r et s deux opérateurs 2-aire de L, nous avons :
F(m)=F(n) <=> T|— m=n
F(u)=F(v) <=> T|— u(x)=v(x)
F(r)=F(s) <=> T|— r(x,y)=s(x,y)
Avec une telle application F, il est facile de déterminer si deux mots x et y désignent le même élément dans <L/T>. Il suffit d'appliquer l'application F et de regarder si F(x)=F(y). F est appelée une application élective. F(x) représente la classe de x, et est appelé un représentant de la classe de x.
F est une transformation homomorphe : Quelque soit un opérateur n-aire de L° appliqué à n mots de L°0, l'image par F est égale à ce que produit l'opérateur évalué par F appliqué aux mêmes opérandes évaluées préalablement par F. Par exemple quelque soit x, y deux mots de L°0, nous avons :
F(g(x,y)) = F(g)(F(x),F(y))
Nous n'avons pas préciser l'ensemble d'arrivé de l'application F. La notion de transformation homomorphe est plus générale que celle d'homomorphisme qui exige que l'ensemble d'arrivé soit une même structure que l'ensemble de départ et qui coïncide (c'est à dire que les images des opérateurs de la structure de départ coïncide avec les opérateurs de la structure d'arrivé). L'ensemble d'arrivé est un langage, et la seul hypothèse sur ce langage tient en ce qu'on lui demande de calculer en un temps fini si deux mots sont distincts ou non. En d'autre terme Le prédicat = doit y être totalement calculable. Ce langage peut être plus général encore que celui que nous décrivons.
Les opérateurs générateurs de <L> sont transformés par F en des opérateurs générateurs de <L / T>. La qualité génératrice d'une séquence d'opérateurs est conservée lors de la transformation F. Par conséquent la structure <L / T> est engendré par les opérateurs F(L) la structure <L / T> est donc égale à la structure <F(L)> que l'on note <L \ F> et qui constitue une concrétisation homomorphe de la structure <L>
Les représentants sont identifiés aux éléments de <L/T> qu'ils représentent. L'ensemble F(L°) est identifié ainsi à <L/T>. F est alors une transformation homomorphe surjective de L° sur <L/T>. Et si les opérateurs générateurs d'arité non nulle sont tous dans des classes distinctes, ils sont transformés en opérateurs d'arité non nulle agissant sur <L/T> et font partie de la présentation de la structure, et l'application F est alors un homomorphisme.
Dans la pratique, l'ensemble d'arrivé d'une fonction élective F est le même que l'ensemble de départ. La fonction F est donc une transformation endomorphe totalement calculable de L°. De plus, dans la pratique, le représentant appartient à la classe d'équivalence qu'il représente, faisant que pour tout mot x de L° nous avons F(F(x))=F(x). La fonction F est donc une transformation endomorphe involutive totalement calculable de L°.
La notion de transformation endomorphe est plus générale que celle d'endomorphisme qui exige en plus que les images des opérateurs de la structure de départ soit invariant.
Structure avec un infini :
Nous ne pouvons pas choisire arbitrairement un réprésentant par classe d'équivalence lorsqu'il y en a un nombre infini, car sans l'axiome de choix, nous ne pouvons pas effectuer une infinité de choix arbitraires. En d'autre terme et d'une manière plus générale cela signifie que nous ne pouvons pas construire de fonctions non calculables, et même d'en supposer l'existence si elle ne nous a pas été donnée par quelqu'un d'autre. Une fonction calculable est décrite par un programme de taille finie dans un langage de programmation de type fini. Et une telle fonction n'est pas obligatoirement totalement calculable, c'est à dire qu'elle peut ne jamais s'arréter et produire l'infini de Turing.
Si nous choisissons une fonction élective non totalement calculable, que représente alors l'infini de Turing ?. Il représente une classe particulière appelé l'infini, un élément particulier de <L / T> appellé l'infini. Et l'hypothèse sur le langage, l'ensemble d'arrivé de F, peut s'affaiblire et ne retenir que le critère de calculabilité (et non de totale calculabilitée) pour le prédicat = lorsqu'il s'applique à au moin un mot infini. Ce langage peut donc être encore plus général. On parlera de langage avec un infini. Un tel langage comprent un mot appelé infini, et le prédicat x=y est totalement calculable pour tout x et y différents de l'infini, et est simplement calculable lorsque x ou y est égale à l'infini et produit alors l'infini de Turing si ils ne sont pas tous les deux infinis.
10) La concrétisation
On complète la structure par une transformation H, appelée fonction d'évaluation, défini sur <L>. Par abus de notation, la fonction H est définie aussi bien sur L° que sur <L> de la même façon. La structure concrétisée se note :
<L \ H>
Des règles de simplifications peuvent apparaître de façon implicite comme une conséquence de l'évaluation. En effet deux mots x et y désignent le même élément si et seulement si H(x) = H(y).
Dans la pratique l'évaluation H respecte le langage de départ L°. On parlera de concrétisation homomorphe. H est un homomorphisme, c'est à dire quelque soit un opérateur n-aire de L° appliqué à n mots de L°0, l'image par H est égale à ce que produit l'opérateur évalué par H appliqué aux mêmes opérandes évaluées préalablement par H. Par exemple quelque soit x, y deux mots de L°0, nous avons :
H(g(x,y)) = H(g)(H(x),H(y))
La liste des opérateurs générateurs a, b, f, g, est transformée en la liste des signifiés que l'on note parfois de même nom en italique a = H(a), b = H(b), f = H(f), g = H(g). Cette liste, avec la propriété d'homomorphisme de H, définit complètement H. Cette définition est récurcive. Si les définitions des opérateurs agissants a, b, f, g, sont calculables alors H est calculable. La construction d'opérateurs agissants a, b, f, g, constituent une concrétisation homomorphe de la structure. L'ensemble dans lequel agissent les opérateurs doit être définie et fait partie de la définition de H. Dans l'exemple suivant nous faisons agire les opérateurs générateurs sur une autre structure <K> :
Le langage L° :
L° = {a,b,f(.),g(.,.)}°
L'évaluateur H :
K° = {a,b,k(.,.)}°
H
H(a) = a
H(b) = b
H(f) = x-->h(x,a)
H(g) = h
Nous avons par exemples :
H(f(a)) = h(a,a)
H(g(a,b)) = h(a,b)
H(g(f(b),b)) = h(h(b,a),b)
H est un homomorphisme entre la structure <L> et la structure <K>. La concrétisation homomorphe correspond à faire opérer les opérateurs générateurs sur une autre structure <K>, de les appeler evaluateur générateur, et d'en fixer leurs définitions. Cela concrétise la structure, et on la note :
<L \ E, a=a, b=b, f=f, g=g>
il se peut que cette structure ne soit plus libre, et qu'il y est des règles d'égalités cachées entre mots. De telles règles sont dites implicites.
On peut répéter l'opération de concrétisation en opérant une seconde transformation G, sur les mots, faisant que deux mots x et y désignent le même éléments si et seulement si G(H(x))=G(H(y)).
<L \ H \ G> = <L \ G°H>
Pour construire une seconde opération de concrétisation homomorphe, il est nécessaire que l'ensemble sous-jacent E de la première opération de concrétisation soit un langage d'opérateur simple. Et supposons par exemple que se langage soit engendré par {u,v(.)}, alors la deuxième concrétisation homomorphe va consister à choisir un second ensemble sous-jacent F et à choisire un élément u dans F, et à choisir une fonction v de F vers F. La double concrétisation se note alors :
L° = {a,b,f(.),g(.,.)}°
E = {u, v(.)}°<L \ E, a=a, b=b, f=f, g=g \ F u=u, v=v>
<L \ <u, v(.)>, a=a, b=b, f=f, g=g \ F u=u, v=v>
10) Quotientage et concrétisation
Si nous partons d'une structure quotient <L / T>, la concrétisation consiste à ajouter une transformation H, appelé évaluation, qui opère sur les classes d'équivalence de <L / T> pour produire les éléments de la structure concrètisée, faisant que deux mots x et y désignent le même élément si et seulement si il existe un mot x1de même classe que x et un mot y1 de même classe que y tel que H(x1)=H(y1).
Les classes d'équivalences sont projetées par H sur l'ensemble sous-jacent E = H(L°). Et les classes projetées qui ne sont pas disjointes sont fusionnée, cela découle de la transitivité de l'égalité. On note la structure concrétisée <L / T : H>
Si nous partons d'une structure concrète <L \ H>, l'opération de quotientage consiste à choisire une relation d'équivalence R sur l'ensemble sous-jacent E = H(L°). La structure quotient se note : <L \ H / R>
Les quotientages et les concrétisations peuvent ainsi se succéder.
7.1) Les structures concrètes
La réfutation de l'axiome du choix nous interdit de construire une fonction en faisant un nombre infini de choix arbitraires, faisant qu'il est impossible de prouver l'existence d'une fonction non calculable, sauf si cette fonction nous est apportée, et dans ce cas cela enrichie notre langage de démonstration et étend notre domaine des fonctions existantes (d'existence prouvable), et si cette fonction est de plus opérationnelle, cela enrichie notre langage de programmation et étend notre domaine des fonctions opérationnelles.
Les applications génératrices possèdent des ensembles images que l'on inclus dans un ensemble mère E plus vaste et plus simple à définire, et qui constitue l'ensemble d'arrivé de toutes les applications génératrices de la structure. Les constantes ne sont pas en restes, elles sont également projetées dans cet ensemble mère. La structure est concrétisé au sense où chaque opérateur générateur est maintenant une application bien définie agissant sur un ensemble mère bien défini.
Une structure <a, f(.), h(.) : E, a, f, h> est dite concrète lorsque l'on a préciser l'ensemble mère E, et définie ses applications génératrices a, f et h agissant sur E avec la même arité (donc d'ensemble d'arrivé E). Et l'application appelé d'évaluation et noté H, de L° vers <L> qui évalue tout mot de L° en appliquant les applications emboitées et produisant ainsi l'élément de <L> qu'il désigne, est bien définie.
De plus, la structure est dite opérationnelle si ses applications génératrices sont opérationnelles. Et dans ce cas, l'opération d'évaluation H est opérationnelle.
Par exemple considérons la structure opérationnelle suivante :
< a, f(.), h(.) : N^2, a = (0,0), f(x) = (p1(x)+1, p2(x)), g(x) = (p1(x), p2(x)+1) >
Dans cette exemple p1 et p2 sont les projections, deux applications de N^2 dans N qui à tout couple (u,v) produit respectivement u et v. Ces deux applications sont implicitement apportées par la structure opérationnelle N^2.
7.2) Les catégorie
Deux structures sont dit apartenire à la même catégorie s'il existe un isomorphisme entre eux deux. C'est à dire une bijection I qui respecte les opérateurs. C'est à dire si a, f(.), g(.,.) sont des opérateurs alors I(f(x)) =
A la structure libre <L> correspond la structure opérationelle canonique < L : L° > dans laquelle les applications génératrices on une définition triviale. Par exemple, la fonction g : (x,y)-->g(x,y) opère sur un couple de mots (x,y) quelconque de L°^2 pour produire un autre mot de L° qui est le mot g(x,y) dans lequel on a substitué x et y par leur valeur. g est une application de L°^2-->L° totalement calculable et son algorithme correspond simplement et exactement à sa définition et à la substitution de son couple de variables d'entré.
