Le choix de la calculabilité et des langages d'opérateurs va privilegier l'émmergence d'un systèmes d'objects constructibles comme des légos. Et il est alors possible de définir l'ensemble de tous les éléments ainsi constructibles, en levant la contradiction récurcive inhérante à ce genre de définition, par la seul condition d'être constructible. Cet ensemble s'appelle l'univers, il se contient et est énumérable par sa nature.
Les intuitionistes concidèrent inoportun d'étudier des structures gouvernées par un nombre infini de choix arbitraires.
Le raisonnement est une construction sur un langage d'opérateurs. L'aspect déclaratif est regroupé dans le langage qui peut ainsi s'augmenter d'opérateurs variables et d'opérateurs constants à volontées.
Ces opérateurs peuvent être quantifiés soit universellement ou soit existenciellement. Selon le point de vue constructif on peut éliminer le quantificateur existenciel par skolémisation, ce qui a pour effet d'accroitre l'arité de l'opérateur concerné et de les rendre constant. Cela correspond à une extention du langage des opérateurs.
Ce faisant le langage contient des opérateurs variables utilisé pour le raisonnement, c'est à dire quantifiés universellement, et des opérateurs constants, c'est à dire quantifiés existanciellement, mais avant les autres, et constituant ainsi le langage d'opérateurs proprement dit, un langage en perpetuelle évolution au cours du raisonnement.
Les fonctions unaires sont vu comme des programmes ayant une entré. Ils sont énumérables, car on utilise un langage de programmation qui est par définition fini et par ce qu'un programme est par définition de taille finie. Ce principe exclue l'axiome du choix. Une infinité de choix arbitraires ne peut pas être opérée par un programme de taille fini.
Le programme f appliqué à une entré x peut, soit retourner un résultat f(x) différent de FAIL, soit retourner FAIL, soit ne jamais donner de réponse ce qui correspond à l'infini de Turing noté ∞. L'élément FAIL correspond à l'arret du programme sur un échec. Cela signifie sémantiquement que le programme, à un moment précis, échoue dans sa recherche, ou plutôt qu'il conclue qu'il n'y a pas de solution et retourne par conséquent l'information de cette non existance sous la forme de l'élément FAIL.
Dans une certaine mesure, l'élément FAIL peut être considéré comme l'ensemble vide Ø. En effet on peut considérer l'object plus générale, parent de la fonction, qu'est la relation. Une relation R est un graphe orienté. L'image d'un élément x par R est l'ensemble des éléments atteignables à partir de x en empruntant une arrête de R.
R(x) = {y ; xRy}
s'il n'y en a aucun alors R(x) = Ø et cette absence de solution s'apparente au FAIL.
Si on se restreint à un ensemble E c'est à dire que l'on ne retient que les arrêtes partant d'un élément de E pour aller sur un élément de E, alors R est un sous ensemble de E2.
R est constructible s'il existe un énumérateur, c'est à dire un programme, qui énumère toutes les arrêtes de R. On revient à la définition d'un ensemble constructible. Un ensemble est constructible s'il existe un énumérateur qui énumère tous ses éléments.
A partir d'une relation R et de son énumérateur, on construit une fonction canonique R1 qui associe à tout élément la première image apparaissant dans l'ordre d'énumération de R.
Mais une relation R est une fonction si et seulement si elle ne possède pas deux arrêtes ayant le même élément de départ. La seul capacité énumérative de R ne permet pas de programmer un prédicat capable d'affirmer que R est une fonction si cela est. Par contre elle permet de fabriquer un prédicat capable d'affirmer que R n'est pas une fonction si cela est. Ll'algorithme consiste à énumérer tous les couples d'arrètes possibles (ce qui est énumérable) et de vérifier l'unicité de l'élément de départ.
Ainsi certaines questions sont semi-décidable, c'est à dire qu'il existe un algorithme capable de répondre par l'affirmative, mais qu'il nexiste pas d'algorithmes capable de répondre par la négative, la négation ne peut pas être conclue au bout d'un temps fini.
La fonction peut être restreinte à un ensemble de départ A. L'ensemble est par définition énumérable. Dans le cas générale il est énuméré avec redondance par un langage libre tel que par exemple <a,b,h(.),g(.,.)>, et on peut choisir un ordre d'énumération selon la taille puis selon l'ordre lexicographique. L'énumération se ramène donc à une surjection totalement calculable de N vers A.
L'image par f de A que l'on note f(A) = {f(x) ; x∈A} est semi-énumérable, car sont énumération demande une quantité de mémoire non bornée. En effet, comme f peut produire l'infini de Turing, pour ne pas être bloqué, l'énumérateur doit lancer en parallèle le calcul de f sur les éléments de A suivants, et retourner les premiers calculés. Ce faisant, l'énumération étant infinie, cela nécessite une capacité de mémoire illimitée.
Si l'élément FAIL ne fait pas partie de l'image, cela signifie que le programme n'échoue jamais. Mais cela ne signifie pas que le programme donne toujours une réponse. Il peut se bloquer et ne jamais donner de réponse, ce qui se note par l'infini de Turing ∞.
S'il existe un élément x de l'ensemble de départ A pour lequel f(x) égale l'infini de turing, alors on ajoute à l'ensemble d'arrivé B l'élément oracle qu'est l'infini de Turing ∞. Les éléments non calculables par f on alors comme image cet élément rajouté qui est l'infinit de Turing et qui transporte intrinsequement la notion de calculabilité. Avec cette définition de l'ensemble d'arrivé, on peut classifier les fonctions calculables comme suit :
Si on ne s'interesse pas à la complexté des foncitions, il est alors inutile de considérer des fonctions donnant plusieurs résulat en parallèle c'est à dire d'arité de sortie supérieur à 1. Mais un élément est une construction déjà composé en plusieurs sous-éléments, aussi la fonction d'arité de sortie 1 peut être perçu comme une fonction d'arité de sortie supérieur à 1.
La décomposition ultime de l'élément nous ramène au booléen, caractérisé par deux valeurs {true, false}. On dira que la fonction retourne false si elle retourne FAIL, et quelle retourne true si elle retourne une autre valeur que FAIL. Mais si elle ne s'arrête jamais, on dira qu'elle retourne l'oracle ∞, l'infini de Turing.
Une fonction f est interprété comme un prédicat comme suit :
La minimalisation correspond en programmation impérative, à la boucle while.
La minimalisation consiste à recherche la premier valeur n tel que f(n)=true, lorsque n parcours les valeurs entières dans l'ordre 0,1,2,3..... Elle se note, à l'instar de l'instruction for en langage C, par :
n = while(0,S,f)
où 0 désigne la constante élémentaire zéro servant de départ à l'énumération, où S désigne la fonction élémentaire unaire Successeur, motrice de l'énumération, et où f est une fonction calculable unaire quelconque définissant le prédicat calculable unaire. Le résultat est égale à n tel que la valeur logique de f(n) est true et tel que quelque soit l'entier naturel m<n, La valeur logique de f(m) est false.
Par convention, S0(x) = x, et on identifie les entiers naturels aux entiers de Péano, Sn(0) = n.
while est une méta fonction de NxF1xF1 vers N, où N représente l'ensemble des entiers naturel (identifiiés aux entiers de Péano 0, S(0), S(S(0)), S(S(S(0)))....) et où F1 représente l'ensemble des fonctions unaires primitives récurcives.
Il existe une minimalisation dégénérée que constitue la boucle while(true), la boucle infini, utilisée pour effectuer des énumérations infini. Dans le cas générale l'algorithme peut produire un infinit de Turing et interrompre en quelque sorte une telle énumération. Pour englober ce cas, on parlera alors de semi-énumération.
Une semi-énumération est un algorithme produisant une liste de valeurs pouvant être interrompue par l'infini de Turing. La liste peut être infinie ou bien finie avec la présence de l'infini de Turing à la fin, que l'on notera æ. On peut ainsi classer les semi-énumérations selon leur résultat. Deux semi-énumérations ayant le même résultat seront qualifiées de semblables. Par exemple, la suite (2, 8, 6, æ) constitue une semi-énumération de 3 valeurs, l'infinit de Turing n'étant pas concidéré comme une valeur, mais comme l'absence de résultat obtenue en un temps fini, et finalement concidéré comme l'oracle prédisant l'arrêt du processus de semi-énumération. L'éventuelle présence de æ dans une liste semi-énumérable ne peut-être qu'unique et est obligatoirement placé à la fin de la liste, et s'il n'est pas présent la liste est nécessairement infinie.
Il existe deux algorithmes de semi-énumération naturels et particulièrement simples à écrire, appelée image de f, et motrice de (a,g). C'est la motrice qui est a priori plus simple car elle est contenue dans l'image :
La motrice de (a,g) est l'algorithme calculant (a, g(a), g(g(a)), g(g(g(a))),... ). Son progamme impératif est le suivant :
|
l'image de f est l'algorithme calculant (f(0), f(S(0)), f(S(S(0))), f(S(S(S(0)))),... ). Son progamme impératif est le suivant :
Noter que la fusion des algorithmes, en supprimant la gestion du tube, n'apporte pas d'ammélioration comme on peut le voir ci-dessous :
|
Les autres algorithmes possibles de semi-énumération sont plus complexe à exprimer. Ils augmentent le domaine des algorithmes (sans augmenter le domaine des fonctions calculables qui a atteint son maximum), et peuvent dévoiler des algorithme de complexité plus faible. La complexité de l'algorithme (sa duré de calcule) ne doit pas être confondu avec la complexité de son expression, (la taille de son programme). Pour l'instant étudions ces deux algorithmes de semi-énumération qui sont particulièrement simples.
Toute les semi-énumérations peuvent être produite comme l'image d'une fonction calculable, le terme de semi-énumération étant synonyme d'énumération calculable. Ce n'est pas le cas pour les algorithmes moteurs. Les semi-énumération produite par un moteur sont cycliques ou injectives. Car soit elles ne se répètent jamais (cas de l'injectivité), soit elles se répètent et au quel cas elles sont cycliques, puisque le calcul étant basé sur l'unique valeur précédente, celle-ci se répétant, le calcul se répète indéfiniment.
Pour deux semi-énumérations cyclique ou injective qui sont semblable, l'une énumérée par l'image de f, l'autre énumérée par le moteur (a,g), on passe du moteur (a,g) à l'image f par un algorithmes naturel appliquant une boucle for, pour composer g autant de fois que nécessaire et l'appliquer à a :
Les semi-énumérations peuvent s'écrirent de façon abrégé ainsi :
a, g(a), g(g(a)), g(précédent)...
f(0), f(1), f(2)...
On passe de l'image f au moteur (a,g) en se restreingnant à l'Im(f) c'est à dire en s'arrétant à la première répétition fr de f. fr est un élément de l'ensemble ordonné N union{æ}. C'est le premier entier rencontré pour lequel f retourne une valeur déja retournée précédement. Il est définie comme suit : Si f est injective alors fr = æ, sinon il existe n<fr tel que f(n) = f(fr) et quelque soit x<fr et y<fr, f(x) différent de f(y) et de æ.
La détermination de (a,g) en fonction de f se limite au domaine de f restreint aux entiers inferieurs ou égale à fr. On part de l'hypothèse que l'image de f, et la motrice de (a,g) sont semblables.
<=> Pour tout n<=fr, f(n) = gn(a)
<=> f(0)=a, Pour tout n<fr, g(f(n)) = f(S(n))
On pose f -1, la fonction inverse de f restreinte au premier cycle. f -1est définie sur Im(f) : Pour tout n<fr, f -1(f(n)) = n
<=> a=f(0), Pour tout n<fr, g(f(f -1(f(n)))) = f(S(f -1(f(n))))
<=> a=f(0), Pour tout y appartenant à l'Img(f), g(f(f -1(y))) = f(S(f -1(y)))
<=> a=f(0), Pour tout y appartenant à l'Img(f), g(y) = (f°S°f -1)(y)
En conclusion a = f(0), g est égale à f°S°f -1 définie sur Im(f). Cela s'écrit comme suit :
g|Im(f)= f°S°f -1|Im(f)
4) Les programmes semi-énumérants
Les semi-énumérations sont générées par des programmes, et d'une manière plus générale par des machines.
Qu'est-ce qu'une machine ?. La machine n'est pas un objet mathématique, c'est un objet physique. Aussi on choisie un type de machine et on se pose la question plus simple, qu'est-ce qu'un programme dans un cadre plus précis, précisant un langage de programmation ? Mais ce n'est pas la dichotomie du programme, son langage de programmation, qui nous intéresse mais son comportement son aspet dynamique. Aussi la question est-elle qu'est-ce qu'un processus ? le mécanisme d'execution d'un programme, un module executable ?.
Nous allons classifier les processus selon ce qu'ils produisent comme données et selon ce qu'ils utilisent comme données, ou exprimé d'une manière d'avantage informatique, selon le comportement de leurs entrés-sorties.
L'algorithme de semi-énumération se concrétise en un module exécutable, une machine, produisant en sortie un tube, tel un tuyaux pouvant relier deux processus UNIX, qui transporte des entiers et qui peut être dirigé vers une entrée d'un autre module exécutable, la version femelle d'une semi-énumération, un module exécutable ayant besoin comme données d'entré d'une semi-énumération. Ainsi, la semi-énumération mâle est représentable par une fonction vectoriel de dimenssion variable non borné pouvant être infinie, et la semi-énumération femelle est représentable par une fonction d'arité variable non borné pouvant être infinie.
Par exemple, une machine ayant comme entré un entier et ayant comme sortie un tube transportant des entiers, peut être représentée par une fonction vectoriel de dimenssion variable pouvant être infinie f : x-->(f0(x), f1(x), f2(x)...) où x, f0(x), f1(x), f2(x)... sont des entiers. Et une machine ayant comme entré un tube transportant des entiers et comme sortie un entier, peut être représentée par une fonction d'arité variable pouvant être infinie : g : (x0, x1, x2...) --> y où y, x0, x1, x2... sont des entiers.
On ne peut pas concidérer les semi-énumération comme des objets car elles ne sont jamais complètement construites. Elles le sont qu'au bout d'un temps infinie. Alors qu'une donnée élémentaire, un entier, ou un n-uplet d'entiers, ou toute combinaison fini, et sans infini de Turing, construite à partir d'entiers, peut former un objet, une entité complètement construite à un instant donné, et regroupant toutes les données le définissant.
Néanmoins si la semi-énumération ne peut jamais être achevée, transmise complètement, le programme qui la fait, lui, peut être transmis complètement, et constitue un objet, une entité complètement construite à un instant donné.
La machine qui génère une semi énumération en sortie à partir seulement d'objets en entrés, constitue un objet, une entité complètement construite à un instant donné avec les objets de ses entrés, et est construite à partir d'entiers (car tout est codé à partir d'entiers). On le décompose en un programme écrit dans un langage de programmation qui est executé par une machine universelle de Turing, de tel sorte que l'objet complet déterminant une semi-énumération est constitué de plusieurs objets, que sont le programme et ces entrés.
Néamoins cette objets n'est pas de même nature, il se différencie par rapport aux premiers objets dans son comportement vis-à-vis de la condition d'égalité. Les premiers objets sont égaux ssi chaque partie sont égales, se qui se vérifie en un temps fini borné linéairement. Alors que les seconds objets sont égaux si un raisonnement permet de demontrer qu'ils sont égaux, qu'ils produisent la même semi-énumération, apportant ainsi une réponse incomplète faite en un temps non borné. Et ils sont différents si au cours de leur éxécution, apparait en sortie un élément différents dans les deux semi-énumérations, ce qui se fait en un temps non borné.
Peut-t-on concevoir un transfert de donné d'une autre nature encore, d'une nature plus grande et plus incomplète encore ?. comme par exemple une semi-énumération de semi-énumération ?. Non pour ce cas, car une semi-énumération de semi-énumération se ramène en une semi-énumération de couple (n,x) où n correspond au numéro d'une semi-énumération et x correspond à l'entier énuméré dans la nième semi-énumération. Cela correspond à l'énunmération de N2 : (Un programme Q qui semi-énumère des programme P0, P1, P2, ... peut être remplacé par un programme H qui semi-énumère des couples d'entiers (0,P0(0)), (1,P1(0)), (0,P0(1)), (2,P2(0)), (1,P1(1)), (0,P0(2)), (3,P3(0)), (2,P2(1)), (1,P1(2)), (0,P0(3)), ....)
Il faut considérer des semi-énumération d'objets. L'objet complet fini étant plus général qu'un entier, tout en étant de même nature que l'entier. On dira semantiquement que l'objet est entier....
L'énumérateur est le processus de construction des éléments. Dans le cas générale étudié, il énumère une mono-structure A avec redondance par le langage libre sur lequelle est construit la mono-structure A tel que par exemple <a,b,h(.),g(.,.)>, et on peut choisir un ordre d'énumération selon la taille puis selon l'ordre lexicographique. L'énumération se ramène alors à une surjection totalement calculable de N vers A.