Un des concepts clefs pour aborder les mathématiques est le concept d'ensemble. La théorie des ensembles est rendue non constructive par l'axiome du choix qui est utilisé abondament pour traiter de l'infini. Nous préférons à la notion d'ensemble, la notion de collection (et peut être même mieux encore, la notion de configuation) qui est définie à un groupe de permutations près des éléments. Et lorsque la collection est une énumération sans fin, les permutations considérées sont alors des bijections calculables. Il est utile de circonscrire la notion trop vaste d'ensemble au travers des préceptes plus terre-à-terres provenant des fondements de l'informatique vus précédemment et ainsi définir ce qu'est un ensemble énumérable à l'aide du concept d'application calculable.
Pour définir la calculabilité, il nous faut pouvoir construire les éléments que nous utilisons, de la même façon que nous devons pouvoir construir toutes les démonstrations. Cela a pour conséquence de rendre fini la quantité d'information de chaque élément, comme cela est le cas pour chaque démonstration. Cette restriction limite-t-elle les mathématiques ? Il semblerait que non, car à quoi bon chercher au delà, en concevant des objets inatteignables, possèdant une quantité d'information infinie, sachant que le système de démonstration est par principe limité à un mécanisme fini, ne conçevant que des démonstrations finies ?. Un élément ayant une quantité d'information infinie dans un univers de démonstrations ne possèdent que des quantités finies d'information, se traduira nécessairement par une redondance théorique. C'est le point vue élémentarien, et qui rejoint celui-des intuitionistes dans l'affirmation qu'il n'y a rien au delà de l'infini, et qui justifie que le calcul sans fin soit désigné par un unique symbole, `oo`, l'infini de Turing.
Les ensembles énumérables que nous évoquons sont inclus dans des ensemble à la fois plus vaste et plus simple que sont les structures libres. Et la calculabilité se définie à l'aide de ces structures libres.
Il y a deux façons fonctionnelles de définir un ensemble `E` à partir d'autres ensembles. On le définit soit comme image ou bien soit comme noyau c'est à dire l'image réciproque de l'élément neutre (ou d'un élément singulier s'il n'y a pas d'élément neutre).
On le définit soit à l'aide d'une application `f` partant d'un ensemble père `NN` et allant sur un ensemble mère `bbbM`, et dont l'ensemble image est `E` :
`E "⊆" bbbM`
`f"∈"(NN"→"M)`
`f(NN) =` Im`(f) = E`
Ou bien soit à l'aide d'une application `X` définie sur un ensemble mère `bbbM` et dont le noyau donne `E` :
`E "⊆" bbbM`
`X"∈"(bbbM"→"bbbM)`
`EEm"∈"bbbM, X^-1(m)=E`
Notez que l'expression `(A"→"B)` désigne l'ensemble des applications de `A` vers `B`.
Notez que l'expression `X^-1(m)` utilise la notation étendue aux ensembles dont la définition est :
Notez dans cette expression l'inférence de type sur `x`. L'élément `x` étant utilisé comme entrée de la fonction `X`, possède un type par définition restreint à l'ensemble de départ de `X`. Autrement dit `x"∈"`Dép`(X)`.`X^-1(m) = {x "/" X(x)"="m}`
L'ensemble père que nous utilisons souvent est l'ensemble des entiers naturels `NN` qui représente l'infini potentiel en quelque sorte, c'est à dire la capacité d'ajouter toujours un nouvel élément, comme peut le faire le démonstrateur au cours d'une démonstrations.
L'ensemble mère est un ensemble contenant `E`, plus simple que `E`. Et cet ensemble doit constituer la base des constructions. On choisira une structure libre composée d'opérateurs générateurs de différentes arités, telle que par exemple :
`bbbM = "<"a,b,h"(.)",g"(.,.)>"`
Puis, l'expression `EEm "∈" bbbM` évoquée plus haut, doit avoir une signification plus précise que celle décrite par la logique du premier ordre. Elle doit affirmer que l'élément `m` est calculable, c'est à dire qu'il existe une définition de `m` comme étant égale à une composition d'opérateurs générateurs de `bbbM`, ce qui est assurement vrai étant donné la définition de `bbbM`. Mais c'est mieux en le disant pour bien circonscrire ce qu'est l'ensemble mère `bbbM`.
Ces deux procédés, images et noyaux, appliqués à des applications calculables, vont respectivement définir les ensembles énumérables et les ensembles décidables.
Mais avant d'aller plus-loin, il nous faut bien expliquer la distinction entre une application et un programme.
Un programme `sff`, noté ici avec une lettre en police droite, est une machine qui prend en entrée un élément `x` d'un ensemble mère `bbbM_1` puis exécute un calcul. Et deux cas peuvent se produire. Soit le calcul ne s'arrête jamais, ce qui se note `sf"f"(x)"="oo` l'infini de Turing. Ou bien soit le calcul s'arrête en produisant comme résultat un élément `y` d'un autre ensemble mère `bbbM_2`, ce qui se note `sf"f"(x)"="y`.
Le méta-élément `oo`, appelé l'infini de Turing, désigne un comportement particulier du programme, le fait de ne pas s'arrêter. Notez que cette valeur utilisée comme valeur de retour `oo` est un oracle car dans le cas général, il faut se placer à la fin des temps pour être sûr de ce résultat.
Lorsqu'un programme, quelque soit l'élément d'entrée sur lequel il s'applique, donne toujours une réponse en un temps fini, il est dit « d'arrêt sûr ».
Le programme `sff` possède un ensemble mère de départ et un ensemble mère d'arrivé qui peut être complété d'un méta-élément `oo` si le programme n'est pas d'arrêt sûr. Et on utilise les mêmes notations que pour les fonctions :
Arr`(sff) = bbbM_2`
Arr`(sff) = bbbM_2+{oo}`
Le programme `sff` s'applique à un élément de `bbbM_1` et retourne un élément de `bbbM_2` pour des raisons propres à son algorithme.
L'ensemble des programmes de `bbbM_1` vers `bbbM_2` se note `bbbM_1"⇴"(bbbM_2"+"{oo})` et comprend les programmes d'arrêt sûr et ceux qui ne le sont pas. Chaque programme noté avec une lettre en police droite `sff` de `bbbM_1"⇴"(bbbM_2"+"{oo})` calcule une application notée avec la même lettre mais en police normal `f` de `bbbM_1"→"(bbbM_2"+"{oo})`. L'application `f` se définie ainsi : `AAxAAy, ``f(x)"="y <=> sf"f"(x)"="y`. Notez que le quantificateur `AAx` porte sur l'ensemble de départ de `f` et donc signifie exactement `AAx"∈"bbbM_1`, et que le quantificateur `AAy` porte sur l'ensemble d'arrivé de `f` et donc signifie exactement `AAy"∈"(bbbM_2"+"{oo})`.
---- 23 mai 2018 ----
L'ensemble des programmes d'arrêt sûr, de `bbbM_1` vers `bbbM_2`, se note `bbbM_1"⇴"bbbM_2`. Chaque programme de `bbbM_1"⇴"bbbM_2` calcule une application dite calculable de `bbbM_1"→"bbbM_2`, et toutes les applications calculables de `bbbM_1"→"bbbM_2` se construisent ainsi.
De même qu'il y a deux façons de définir un ensemble, comme image ou comme noyau, il y a deux types de programme, le semi-énumérateur et le semi-prédicateur :
Tout prédicateur `sf"X"` partitionne son ensemble de départ en deux parties :
Arr`(sfX) = {0,1}`
Dép`(sfX) = sf"X"^-1(0) + sf"X"^-1(1)`
`sf"X"^-1(0)` est l'ensemble des éléments refusés par `sf"X"`.
`sf"X"^-1(1)` est l'ensemble des éléments acceptés par `sf"X"`.
`sf"X"^-1(oo)` est l 'ensemble des éléments indéterminés par `sf"X"`.
Tout semi-prédicateur `sf"X"` partitionne son ensemble de départ en trois parties :
Im`(sfX) = {0,1,oo}`
Dép`(sfX) = sf"X"^-1(0) + sf"X"^-1(1) + sf"X"^-1(oo)`
`sf"X"^-1(0)` est l'ensemble des éléments refusés par `sf"X"`.
`sf"X"^-1(1)` est l'ensemble des éléments acceptés par `sf"X"`.
`sf"X"^-1(oo)` est l 'ensemble des éléments indéterminés par `sf"X"`.
---- 23 mai 2018 ----
La formule est par définition de taille finie. Le programme l'est également. On verra que chaque formule constitue en soi un programme. Mais le programme a une qualité supplémentaire, il peut produire des formules de taille non bornée. C'est en cela que le programme étend la formule à l'infini potentiel.
Une énumération bijective de `E` est un programme d'arrêt sûr qui définit une bijection de `NN"↔"E`. Autrement dit en faisant abstraction de la complexité finie du programme, c'est une bijection totalement calculable.
Une énumération de `E` est un programme d'arrêt sûr qui définit une surjection de `NN"↠"E`. Autrement dit en faisant abstraction de la complexité finie du programme, c'est une surjection totalement calculable.
Une semi-énumération de `E` est un programme de `NN` vers `E` dont l'arrêt n'est pas sûr et qui définit une surjection `NN"↠"(E"+"{oo})` où l'élément `oo`, est l'infini de Turing, la valeur de retour lorsque le programme ne s'arrête jamais. (Notez que cette valeur de retour`oo` est un oracle car dans le cas général, il faut se placer à l'infini des temps pour être sûr de ce résultat). Autrement dit en faisant abstraction de la complexité finie du programme, c'est une surjection calculable.
La programmation va nous indiquer comment à partir d'une semi-énumération, programmer une énumération, puis programmer une énumération bijective. Ainsi il n'y aura pas de différence entre les ensembles semi-énumérables, les ensembles énumérables et les ensembles énumérables bijectivement.
Un ensemble `E"⊆" bbbM` est décidable si et seulement si il existe un programme d'arrêt sûr qui définie une surjection de `M"↠"{0,1}` tel que `M(E) "=" {1}` et `M(bbbM"-"E) "=" {0}`
Un ensemble `E"⊆" bbbM` est semi-décidable si et seulement si il existe un programme dont l'arrêt n'est pas sûr et qui définie une surjection de `M"↠"{0,1,oo}` tel que `M(E) "=" {1}` et `M(bbbM"-"E) "=" {0,oo}`, où l'élément `oo`, est l'infini de Turing, la valeur de retour lorsque le programme ne s'arrête jamais. Notez que cette valeur de retour`oo` est un oracle car dans le cas général, il faut se placer à l'infini des temps pour être sûr de ce résultat.
La programmation va nous indiquer comment à partir d'une semi-acceptation, programmer une énumération, Ainsi il n'y aura pas de différence entre les ensembles énumérables, les ensembles demi-décidable. Puis La programmation va nous indiquer comment à partir de deux énumérations complémentaires programmer une acceptation. Ainsi il n'y aura pas de différence entre les ensembles énumérables de complément énumérables et les ensembles décidables.
Par définition, un ensemble `E` est énumérable si et seulement s'il existe un programme qui énumère `E`. C'est à dire un programme de `NN` vers `E` qui soit surjectif c'est à dire qui atteint tous les éléments de `E`, et qui soit totalement calculable c'est à dire d'arrêt sûr. Si on n'a pas cette dernière condition alors le programme est dit semi-énumérant `E`.
S'il existe un programme qui semi-énumère `E` alors on peut construire un programme qui énumère E par le procédé de minimalisation :
Une application `f` énumére `E` ssi pour chaque entier `n`, le calcul `f(n)` abouti en un temps fini à un élément de `E` et telle que l'image de `f` est égale à `E`. Autrement dit, `f` est une surjection totalement calculable de `NN↠E`. Lorsque `n` parcourt tous les entiers, `f(n)` parcourt au moins une fois tous les éléments de `E`. On peut alors désigner les éléments de `E` par des entiers en utilisant un procédé inverse, en choisisant pour chaque élément `x` de `E`, le premier entier `n` tel que `f(n)=x`. Cette application inverse s'appel le codeur ou l'identificateur, c'est une injection totalement calculable de `E↪NN`.
Enumérer signifie coder et identifier les éléments par des entiers à l'aide d'un procéder totalement calculable.
L'opération permettant de passer de l'énumérateur au codeur et inversement doit pouvoir se programmer simplement dans un langage de programmation approprié.
En effet, il est pertinent de chercher un langage de programmation dans lequel cette opération soit simple à écrire, car il s'agit d'une opération informatique fondamentale.
Un ensemble `E` est énumérable si et seulement si il existe une application `f` qui énumère `E`.
Une application `f` énumére `E` ssi pour chaque entier `n`, le calcul `f(n)` abouti en un temps fini à un élément de `E` et telle que l'image de `f` est égale à `E`. Autrement dit, `f` est une surjection totalement calculable de `NN↠E`. Lorsque `n` parcourt tous les entiers, `f(n)` parcourt au moins une fois tous les éléments de `E`. On peut alors désigner les éléments de `E` par des entiers en utilisant un procédé inverse, en choisisant pour chaque élément `x` de `E`, le premier entier `n` tel que `f(n)=x`. Cette application inverse s'appel le codeur ou l'identificateur, c'est une injection totalement calculable de `E↪NN`.
Enumérer signifie coder et identifier les éléments par des entiers à l'aide d'un procéder totalement calculable.
L'opération permettant de passer de l'énumérateur au codeur et inversement doit pouvoir se programmer simplement dans un langage de programmation approprié.
En effet, il est pertinent de chercher un langage de programmation dans lequel cette opération soit simple à écrire, car il s'agit d'une opération informatique fondamentale.
---- 28 mai 2016 ----
Un ensemble `E` est dit décidable dans un ensemble mère si et seulement si il est le noyau d'une application totalement calculable définie sur l'ensemble mère. `E` est décidable dans un ensemble mère si et seulement si il existe une application qui décide pour chaque éléments de l'ensemble mère s'il appartient ou non à `E`. Décider une question signifie calculer en un temps fini la réponse oui ou non. `E` est décidable dans un ensemble mère si et seulement si il existe une application caractéritique définie sur cette ensemble mère qui appliqué à chaque élément calcule en un temps fini la valeur caractéristique de l'élément qui vaut `1` si cet élément appartient à `E`, ou `0` si cet élément n'appartient pas à `E`.
Une application caractéristique `X` décide `E` dans son ensemble mère ssi `X` est totalement calculable dans l'ensemble mère, et que l'image réciproque de `1` est égale à `E`. L'ensemble `E` est décidable dans un ensemble mère ssi il existe une application caractéristique `X` définie sur l'ensemble mère qui décide `E`. On peut alors désigner les éléments de `E` comme les éléments de l'ensemble mère décidés par `X`. Décider signifie choisir par un procédé totalement calculable.
Etant donné une application `X` décidant `E` dans un ensemble mère énuméré par `f`, on peut définir une énumération `g` de `E` de la façon suivante : `f` énumère tous les éléments de l'ensemble mère `f(0), f(1), f(2),..., f(n),...` et à chaque itération on calcule en un temps fini la valeur caractéristique `X(f(n))` qui lorsqu'elle est égale à `1`, désigne `f(n)` comme un élément qui appartient à `E`, et qui est ajouter dans l'énumération de `g`. Nous avons ainsi construit un énumérateur `g` totalement calculable. En conclusion : Les ensembles décidables dans un ensemble mère énumérable sont également énumérables.
La programmation de `g` à partir de `f` et de `X` doit pouvoir s'écrire simplement dans le langage de programmation.
L'énumération d'un ensemble induit une relation d'ordre totale qu'est l'ordre de l'énumération première des éléments. On peut toujours ordonner l'énumération afin que celle-ci ne répète aucun élément tant que tous n'ont pas été énumérés une première fois. Dans le cas infini, l'énumération devient alors une bijection.
Cette opération ordonnant une énumération, transformant une énumération infinie en énumération bijective, doit pouvoir s'écrire simplement dans le langage de programmation.
Etant donné une application `f` énumérant `E`, l'énumération induit un ordre totale sur `E` représenté par l'énumérateur ordonnée `F` et par le prédicat de l'ordre `O"(.,.)"` également totalement calculable, définit comme suit : Quelque soit `x,y` appartenant à `E`, l'expression `O(x,y)` signifie que `x` est énuméré avant `y`, ou autrement dit que le code minimal de `x` est plus petite que celui de `y`.
La programmation de l'ordre `O` à partir de l'énumération ordonnée `F` doit pouvoir s'écrire simplement dans le langage de programmation.
Etant donné une application `g` énumérant en ordre l'ensemble mère, et une application `f` énumérant en ordre une partie `E` de cet ensemble mère. `f` respecte l'ordre d'énumération de `g`, ssi lorsque `f` énumère `x` avant `y` alors `g` énumère `x` avant `y`. On dira que `E` est énuméré par `f` de façon monotone. La application qui associe chaque code minimal `f^(-1)(x)` au code minimal `g^(-1)(x)` est strictement croissante.
Si `E` est énuméré de façon monotone alors le complémentaire l'est également. En effet soit `f` énumérant en ordre `E`, et `g` énumérant en ordre l'ensemble mère. Et supposons que `f` respecte l'ordre d'énumération de `g`. On peut alors construire une énumération en ordre `h` du complémentaire de `E` en énumérant en parallèle `g` et `f`, mais en prenant soin d'évaluer le `f` suivant que lorsque `g` a atteint un élément égal au dernier élément atteint par `f`, et en ajoutant dans l'énumération `h` tous les éléments atteint par `g` qui ne coïncide pas avec l'élément atteint par `f`. L'énumération `h` ainsi obtenue est bien totalement calculable et respecte l'ordre d'énumération de `g`.
Cette opération calculant une énumération en ordre et monotone du complémentaire doit pouvoir s'écrire simplement dans un langage de programmation.
Un ensemble `E` est semi-énumérable ssi il existe une application `f` qui semi-énumère `E`.
Une application `f` semi-énumére `E` ssi pour chaque entier `n` le calcul `f(n)` soit abouti à un élément de `E`, ou soit n'abouti pas et donne l'infini de Turing, et telle que l'image de `f` couvre `E`. Autrement dit `f` est une application de `NN->Euu{oo}` couvrant `E` c'est à dire telle que `E sub f(NN)`.
Semi-énumèrer signifie convertir les entiers par un procéder calculable, mais pas forcement totalement calculable, en éléments de `E` ou en l'infini de Turing.
A partir d'une application `f` qui semi-énumère `E`, on peut construire une application `g` qui énumère `E`, en appliquant un procédé de minimalisation à `f` : On calcule en parallèle `f(0), f(1), f(2), ..., f(n)`, pour un nombre de valeurs `n` toujours croissant, en lançant en parallèle à chaque fois un calcul supplémentaire `f(n+1)` après l'exécution d'une instruction de calcul sur chaque application `f(0), f(1), f(2), ..., f(n)`, puis dés qu'un des calculs abouti à un résultat, il est énuméré. Cela nécessite une mémoire non limitée en taille tel que constituée par le ruban d'une machine de Turing. Les valeurs `f(n)` sont énumérées dans l'ordre chronologique de leur aboutissement, associant ainsi à chaque entiers `k` une valeur `g(k)` qui correspond intuitivement à la `k`-ième valeur la plus rapidement calculée dans l'ensemble des calculs `{f(0), f(1), f(2),...,f(n)...}` avec un handicap qui est application de `n`. On suppose donc qu'il existe une quantification dans le langage : Toutes les instructions élémentaire du langage de programmation prisent une par une doivent toujours être résolvable en un temps fini. Sans cette règle on ne peut pas programmer un tel calcul parallèle.
La minimalisation permettant de transformer une semi-éumération en une énumération, a pour conséquence que le domaine des ensemble énumérable est identique au domaine des ensembles semi-énumérables. Parcontre si on s'interdit la minimalisation dans la construction des ensembles, c'est à dire si on se bride en choisissant un langage de programmation plus faible ne permettant pas la minimalisation, alors le domaine des ensembles semi-énumérable apparait comme étant plus grand que le domaine des ensembles énumérables.
Un ensemble `E` est dit semi-décidable dans un ensemble mère si et seulement si il est le noyau d'une application calculable, mais pas necessairement totalement calculable, définie sur l'ensemble mère. `E` est semi-décidable dans un ensemble mère si et seulement si il existe une application caractéristique qui semi-décide pour chaque éléments de l'ensemble mère s'il appartient à `E`. Semi-décider une question signifie calculer l'éventuelle réponse oui en un temps fini, mais où l'éventuelle réponse non n'est pas assuré d'être optenue en un temps fini. `E` est semi-décidable dans un ensemble mère si et seulement si il existe une application caractéristique qui appliqué à chaque élément de l'ensemble mère, soit fait un calcul qui ne s'arrête jamais et qui ne donne pas de réponse ce qui se note par l'infini de Turing `oo` et qui signifie que l'élément n'appartient pas à `E`, soit fait un calcul qui se termine en un temps fini et retourne la valeur caractéristique de l'élément qui vaut `1` si cet élément appartient à `E` ou `0` si cet élément n'appartient pas à `E`.
Une application caractéristique `X` décide `E` dans son ensemble mère, ssi `X` est calculable totalement dans l'ensemble mère et que l'image réciproque de `1` est égale à `E`. L'ensemble `E` est décidable dans un ensemble mère ssi il existe une application `X` définie sur l'ensemble mère qui décide `E`. On peut alors désigner les éléments de `E` comme les éléments de l'ensemble mère décidés par `X`. On dit aussi que `X` est une application caractéristique de `E` totalement calculable définie sur l'ensemble mère. Décider signifie choisir par un procédé totalement calculable.
Etant donné une application `X` décidant `E` dans un ensemble mère énuméré par `f`, on peut définir une énumération `g` de `E` de la façon suivante : `f` énumère tous les éléments de l'ensemble mère `f(0), f(1), f(2),..., f(n),...` et à chaque itération on calcule en un temps fini la valeur caractéristique `X(f(n))` qui lorsqu'elle est égale à `1`, désigne `f(n)` comme un élément qui appartient à `E`, et qui est ajouter dans l'énumération de `g`. Nous avons ainsi construit un énumérateur `g` totalement calculable. En conclusion : Les ensembles décidables dans un ensemble mère énumérable sont également énumérables.
La programmation de `g` à partir de `f` et de `X` doit pouvoir s'écrire simplement dans le langage de programmation.
Une machine de Turing semi-décide E dans un ensemble mère, ssi, appliquée à un élément de l'ensemble mère, elle calcule la valeur caractéristique de l'élément qui vaut 1 si cet élément appartient à E, et 0 ou l'infini de Turing si cet élément n'appartient pas à E ou plus exactement appartient au complémentaire de E dans l'ensemble mère.
Une application caractéristique X semi-décide E dans un ensemble mère, ssi X est calculable, mais non nécessairement totalement calculable, et que l'image réciproque de 1 est égale à E. L'ensemble de départ de X est l'ensemble mère. L'ensemble d'arrivé de X est {0,1,
}. L'infini de Turing est groupé avec 0, de telle sorte que X peut toujours être qualifié de application caractéristique. E est semi-décidable dans un ensemble mère, ssi il existe une application X définie sur l'ensemble mère, qui semi-décide E. X est une application caractéristique de E, calculable, mais non totalement calculable. Semi-décider, signifie choisire un ensemble d'élément par un procédé calculable, mais non totalement calculable.
Si dans un ensemble mère, E et son complémentaire sont tous deux semi-décidables alors ils sont tous deux décidables. Cette opération doit également pouvoir s'écrire simplement dans un langage de programmation.
Par contre, à partir d'une application caractéristique X qui semi-décide E dans un ensemble mère énumérable, il n'y a pas de moyen de construire une autre application caractéristique qui décide E. Le procédé précédent permet seulement de construire une application f qui énumère E, mais certainement pas de construire une application qui énumère le complément de E, ce qui rendrais E décidable. La démonstration se fait par l'absurde. Supposons que tous les ensembles semi-décidables soit décidables. Si nous regardons de plus près X, une application caractéristique qui semi-décide E, nous voyons une application de l'ensemble mère vers {1,0,}qui caractérise trois sous-ensembles que l'on nomment respectivement E,F et G. Intuitivement E désigne l'ensemble des éléments choisis par X, F désigne l'ensemble des éléments rejetés par X, et G désigne l'ensemble des éléments qui n'ont ni été choisis ni été rejetés par X. Symétriquement on voit que F est semi-décidable. Donc selon l'hypothèse, les ensembles E et F étant semi-décidables, ils sont décidables, et il existe alors un procédé totalement calculable qui détermine si la application X appliqué à un élément e de l'ensemble mère, produit un résultat en un temps fini ou non, ce qui est impossible d'après le théorème de Godel, dés lors que l'ensemble mère est suffisamment grand pour coder tous les entiers.
A partir d'une application caractéristique X qui semi-décide E dans un ensemble mère énumérable, on peut construire une application `g` qui énumère `E`, en appliquant un procédé de minimalisation à `X°f` où f est une application qui énumère l'ensemble mère : On calcule en parallèle X(f(n)), pour un nombre de valeurs 1,2,...n,... toujours croissant, en lançant en parallèle à chaque fois un calcul supplémentaire X(f(n+1)) après l'exécution d'un nombre limité d'instructions application de n, et ceci sans attendre les éventuels résultats des calculs X(f(n)) antérieurs. Cela nécessite une mémoire non limitée en taille tel que constituée par le ruban d'une machine de Turing. Les valeurs X(f(n)) sont comptées dans l'ordre chronologique de leur aboutissement, associant ainsi à chaque entiers k une valeur g(k) = f(n) qui correspond intuitivement aux k-ième élément de E le plus rapidement calculable dans l'ensemble des calculs {X(f(0)), X(f(1)), X(f(2)),...,X(f(n))...}avec un handicap donné, application de n.
C'est pourquoi les ensembles semi-énumérables ne se distinguent des ensembles énumérables que si l'on s'interdit le procédé de minimalisation. Ces deux opérations de minimalisation doivent également pouvoir s'écrire simplement dans un langage de programmation.
Etant donné une application `f` énumérant `E` et étant donné un ensemble mère, on peut définir sur l'ensemble mère une application caractéristique `X` de la façon suivante : Pour un élément `x` de l'ensemble mère, on le compare à l'énumération `f`. Si `x` appartient à `E`, alors `f` en un temps fini va énumérer `x` à la n-ième valeur, `f(n) = x`, et l'on fixera la valeur de `X(x)` à `1`. Si `x` n'appartient pas à `E`, alors `f` ne produira jamais `x`, et la application `X` appliquée à `x` ne donnera pas de résultat en un temps fini, donc donnera comme résultat l'infini de Turing. Nous avons ainsi construit une application caractéristique calculable, mais non totalement calculable.
La programmation de `X` à partir de `f` doit pouvoir s'écrire simplement dans le langage de programmation.
En conclusion : Les ensembles énumérés sont semi-décidables dans tous les ensembles mères.
L'ensemble des suites finies d'entier est énumérable. Pour s'en rendre compte, il suffit de considérer la application totalement calculable qui décompose un entier strictement positif en son produit de puissance de nombre premier, associant de façon biunivoque un entier strictement positif avec une suite finie de puissances entières.
On en déduit que l'ensemble des suites finies d'éléments d'un ensemble énumérable est également énumérable.
On dira de manière plus savante que la propriété d'être énumérable pour un ensemble se transmet par l'opération de produit en suite finie. Cela signifie que si l'ensemble A est énumérable alors l'ensemble A* des suites finies d'élément de A, est également énumérable.
Il existe un algorithme d'énumération des suites finies plus rapide que la décomposition en produit de puissance de nombre premier. Et, c'est cet algorithme qui doit pouvoir s'écrire simplement dans un langage de programmation.
Cette phrase signifie que à la base de tout ensemble constructifs se trouve une machine. Et comme notre vision est limitée, on suivra l'opinion de Church. Nous définissons les ensembles par des machines de Turing. Et c'est pourquoi notre étude de l'objet ensemble va aboutir à une nouvelle façon de construire des machines de Turing, et donc des programmes informatiques.
Qu'est ce qu'un ensemble ? comment le définir de manière dynamique ? c'est à dire en répondant aux questions à quoi ça sert ? qu'est-ce que on peut en faire ?.... Pour cela, on va réintroduire les opérateurs nécessaires à sa définition au sein même de l'objet, réunifiant l'aspect objectuel et l'aspect dynamique. Les définitions sont l'énumération et l'acceptation, et les opérateurs sont calculables puisque que l'on s'intéresse aux seuls ensembles constructifs. Considérez les opérateurs comme des procédures effectives, des machines en quelque sorte.
Pour définir un ensemble E, Il nous faut déja un ensemble père qui est à la base de toute énumération, et plus exactement à la base de la récurrence de l'énumération, et qui est l'ensemble des entiers naturels N. Et il nous faut un ensemble mère M englobant l'ensemble E, qui joue le rôle de carrière, un ensemble trés vaste offrant toutes les possibilités de constructions d'éléments qui seront choisis pour constituer notre ensemble E. L'ensemble mère est plus simple que E car on l'étend à cette fin. Il est définie par des procédés de construction effectifs, librement composés, et forme donc une structure libre, un langage libre qui est par principe énumérable. L'énumérabilité de l'ensemble mère découle de l'effectivité de sa construction. En d'autre terme une procédure effective, une machine, va construire l'ensemble mère et va induire de fait une énumération des éléments de l'ensemble mère.
Tout d'abord il est nécessaire de distinguer la notion de fonction de celle d'application. Une fonction de A-->B, au sense stricte du terme, est défini sur un sous ensemble de A appelé domaine de définition, et lorsque son domaine de définition est égale à son ensemble de départ A alors la fonction constitue une application. Toute fonction f de A-->B est étendue canoniquement en une application de A-->(B ∪ {Ø}) où l'image de x est égale à Ø pour tous les élément x en dehors du domaine de définition de f.
On note P(A), l'ensemble des sous ensembles de A. Soit f une fonction de A-->B. Nous étendons cette fonction à l'ensemble des sous-ensembles et nous y définissons une fonction réciproque f-1 comme suit :
Les ensembles images : On étend canoniquement la fonction f aux sous ensembles de A produisant des sous ensembles de B de la façon suivante : Pour un sous ensemble X de A, f(X) est un sous ensemble de B regroupant les images de chaque éléments de X par f. C'est à dire si X 
P(A), alors f(X) = {f(x)/ x X}. Avec cette défintion, l'application f de A-->B est surjective si et seulement si f(A) = B.
Les ensembles noyaux : On définie une fonction réciproque noté f-1 de P(B)-->P(A) comme suit : Pour un sous ensemble Y de B, f-1(Y) est un sous ensemble de A regroupant tous les éléments x de A qui possède une image dans Y. C'est à dire si YP(B) alors f-1(Y) = {x / f(x) Y}. Avec cette définition, la fonction f de A-->B possède comme domaine de définition f-1(B). Et f est injective sur un sous ensemble Y de B si et seulement si 
y Y, f-1(y) est un singleton ou l'ensemble vide Ø.
Un ensemble décidable E est définie par trois fonctions énumérante m, f, g de N-->M totalements calculables et par une application caractéristique X de M-->{0,1} totalement calculable, appelée prédicat. On préfère exprimer les trois fonctions sous forme de trois applications m, f, g de N-->(M ∪ {Ø}) totalements calculables :
L'ensemble mère M est un ensemble plus vaste et plus simple contenant E, telle une structure libre, produit par un langage d'opérateurs d'arités fixés.
L'ensemble père N est l'ensemble des entiers naturels. Il est utilisé comme ensemble de départ pour les fonctions énumérantes m, f, g. Les fonctions énumérantes sont définies sur des sous-ensembles infinie de N. Une fonction énumérant E est une application de N-->(E ∪ {Ø}) totalement calculable dont l'image est E ou (E ∪ {Ø}). L'image inverse de l'élément Ø est égale à l'ensemble des entiers pour lesquel la fonction énumérante n'est pas définie.
On appel un prédicat, une application dont l'ensemble d'arrivé est constitué des deux valeurs logiques {0,1}. Les fonctions caractèristiques sont des prédicats. Un prédicat décidant E est une application de M-->{0,1} totalement calculable tel que appliqué à un élément quelconque de E, la fonction retourne 1, et appliqué à un élément quelconque du complémentaire de E dans M, la fonction retourne 0.
L'énumération d'un ensemble E est une application f de N-->(E ∪ {Ø}) totalement calculable dont l'image contient E. On dit que f énumère E. On dit que E est énumérable.
La semi-énumération d'un ensemble E est une application de N-->(E ∪ {Ø, æ}) calculable dont l'image contient E. Lorsque le calcul ne s'arrête jamais le résultat est l'Infinit de Turing que nous représentons par le symbôle æ. æ n'appartient pas à E, cela traduit le fait qu'un calcul qui ne s'arrète pas ne produit pas d'élément de E. On dit que f semi-énumère E. On dit que E est semi-énumérable.
L'élément æ correspondant à l' Infinit de Turing, transporte avec lui des notions de calculabilité, de tel sorte qu'il suffit de préciser s'il appartient à l'image d'une application calculable pour déterminer ci-celle-ci est totalement calculable ou non.
L'application énumérante ou semi-énumérante f, peut avoir comme image E ou (E ∪ {Ø}) ou (E ∪ {æ}) ou (E ∪ {Ø,æ}), et peut être injective ou non. Les différents cas de figure sont regroupés dans le tableau suivant. On appel bijection une application biunivoque, et surjection une application qui couvre complètement son ensemble d'arrivé. On appel sous-bijection une fonction qui restreinte à son domaine de définition est une bijection, et sous-surjection une fonction qui restreinte à son domaine de définition est une surjection :
f-1(æ) L'image inverse de l'élément æ est appelé le noyaux de non calculabilité. Si le noyaux de non calculabilité est énumérable alors l'application f peut être rendu totalement calculable par une opération série en commençant par calculer le noyaux de non calculabilité puis f. Et alors f serait totalement calculable, ce qui contredirait l'hypothèse, l'existance d'image æ. Aussi le noyau de non calculabilité est nécessairement non énumérable.
Si le noyaux de non calculabilité est semi-énumérable alors l'application f peut être rendu totalement calculable par une opération parallèle : On effectue en parallèle l'application f et l'application semi-énumérant le noyaux de non calculabilité de f. Forcement un des deux calculs s'arrètera en un temps finie et retournera la réponse. Et donc l'application f est totalement calculable, ce qui contredit l'hypothèse, l'existance d'image æ. Aussi le noyau de non calculabilité est nécessairement non semi-énumérable.
L'ensemble E est décidé par une application X totalement calculable de M-->{0,1} tel que quelque soit un élément z de l'ensemble mère M, le calcul X(z) retourne en un temps fini une réponse 1 ou 0 selon que z appartient oui ou non à E. On dit que X décide E, On dit que E est décidable.
L'ensemble E est accepté (ou semi-décidé) par une application calculable X de M-->{0,1,æ} tel que quelque soit un élément z de l'ensemble mère M, si z appartient à E, le calcul X(z) retourne en un temps fini une réponse 1, et si z appartient au complémentaire de E dans M, le calcul X(z) retourne soit 0, soit ne s'arrête jamais donnant l'Infini de Turing représenté par le symbole æ. Dans cette définition de l'acceptation (ou de la semi-décidabilité), 0 et æ sont regroupés dans le même cas, cela traduit le fait qu'un calcul qui ne s'arrète pas n'accepte pas l'élément qui lui est soumis. On dit que X accepte E, que X accepte chaque élément de E, ou que X semi-décide E. On dit que E est semi-décidable.
Il est nécessaire ici d'ouvrir une paranthèse pour préciser ce que représente l'Infini de Turing dans la théorie des ensembles. De la même façon que l'on définit la notion de fonction calculable nous pouvons définir la notion d'ensemble calculable.
L'infini de Turing représente ce qui n'est pas calculé par la fonction calculable et qui doit alors être choisie par la fonction mathématique, qui se présente délors comme une extension, de la fonction restreinte à son domaine de totale calculabilité c'est à dire les éléments x tel que f(x) s'effectue en un temps fini. Et ce choix, même s'il est constant, n'est pas calculable, car au cours du calcul ce choix n'est jamais fait, il est fait après un temps infini, donc il est fait d'une certaine façon avant, comme un oracle.
Qu'est-ce qui permet de définir une fonction non calculable ?, ou en tout cas qui est nécessaire à sa construction mathématique ?. C'est l'axiome du choix qui stipule qu'il est possible de poser une infinité énumérable de choix arbitraire parmis un ensemble de plusieurs possibilités. En effet si on effectue parmis l'ensemble M une infinité de choix arbitraires, un choix pour chaque entier n, on construit une fonction mathématique non nécessairement calculable de N-->M. C'est la définition même d'une fonction mathématique de N-->M. Et cette définition nécessite l'axiome du choix qui n'est pas un axiome anodin puisque aucune machine de Turing ne peut faire ce que fait cet axiome. L'axiome du choix est similaire à l'hypothèse de l'infini, et il peut-être contesté.
Si l'on réfute l'axiome du choix, on introduit une sorte de quantification des fonctions : Les fonctions quantiques sont celles totalement calculables. Les autres fonctions sont exclus.
Un ensemble semi-décidable E est définie par deux fonctions énumérantes m, f, de N-->M totalements calculables et par une application X de M-->{0,1, æ} calculable, ou æ représente l'infinit de Turing. Cette application est un prédicat de logique ternaire. On préfère exprimer les deux fonctions sous forme de deux applications m, f, de N-->(M ∪{Ø}) totalements calculables :
L'énumération de E par f ne permet pas de réfuter en un temps fini l'appartenance à E d'un élément x n'appartenant pas à E. C'est cette faiblesse qui caractèrise les ensembles semi-décidables. Les ensembles semi-décidables dans un ensemble mère énumérable, sont énumérables par le procédé de minimalisation (voir §3).
Un prédicat semi-décidant E est une application de M-->{0,1,æ} calculable telle que appliqué à un élément quelconque de E, la fonction retourne 1 en un temps fini, et appliqué à un élément quelconque du complémentaire de E dans M, la fonction retourne soit 0 ou ne s'arrête jamais et vaut l'Infinit de Turing représenté par le symbôle æ.
Quels opérations pouvons-nous opérer sur ces fonctions énumérantes et ces prédicats pour en fabriquer d'autres ? Les opérations opérant sur les prédicats sont par définition les opérations logiques, et constitue une partie autonome de la programmation.
Les prédicats calculables retournent des valeurs logiques 0 ou 1, ou bien lorsque le calcul ne s'arrète pas, retourne l'Infinit de Turing noté æ. Nous obtenons une logique ternaire {0,1,æ}. Mais la valeur æ est particulière, elle transporte une notion de calculabilité. Les opérateurs que l'on va définir dans cette logique ternaire, auront un comportement vis à vis de cette valeur qui dévoilera un genre de calculabilité, c'est à dire en premier lieu s'il sont calculable ou pas, et en second lieu un genre d'algorithme qui leur seront propre.
En logique binaire, les opérateurs logiques sont engendrés par une composition d'opérateur parmis {¬, et}, où ¬ désigne l'opérateur de négation d'arité 1, et et désigne l'opérateur de conjonction d'arité 2. Qu'en est-il en logique ternaire avec l'infini de Turing ?.
Dans cette logique ternaire, il existe trois opérateurs de conjonction, la conjonction série droite notée et>, la conjonction série gauche, notée <et, et la conjonction parallèle notée et, qui comme leur nom l'indique, procèdent par un calcul en série de gauche à droite ou de droite à gauche ou procèdent par un calcul en parallèle, de leurs arguments, et dans les trois cas intérompt le calcul en retournant 0 lorsque un premier résultat rencontré dans le temps est 0.
Tous les autres opérateurs de conjonction d'arité 2 ne sont pas calculables. C'est à dire que à partir de l'opérateur de conjonction d'arité 2, définis en logique binaire, toutes ses extensions à la logique ternaire autres que ces 3 opérateurs {et, <et, et>}, ne sont pas calculables. Pour s'en rendre compte, on les passe en revue, et on voit de façon évidente qu'ils ne sont pas calculables, c'est à dire qu'il n'existe aucun algorithme capable de les calculer.
En logique ternaire, l'opérateur de négation étant d'arité 1, il ne peut pas se différencier en algorithme de calcul parallèle ou série. il est noté par le même symbole ¬. Et possède comme table de vérité :
En faite, il n'y a pas de choix. Nous avons nécessairement ¬æ = æ. Car sinon l'opérateur ¬ ne serait pas calculable. Et nous avons toujours la règle de simplification ¬(¬x) = x.
On voit dans ces exemples simples comment le comportement de l'opérateur sur la valeur æ va dévoiler le genre de son algorithme de calcul série ou parallèle. Et cette classification en différents genres d'algorithme se fait au niveau le plus élevé, puisque les hypothèses faites sont les plus faibles que l'on puisse posées.
Dans cette logique ternaire, il existe trois opérateurs de disjonction, la disjonction série droite notée ou>, la disjonction série gauche, notée <ou, et la disjonction parallèle notée ou, qui comme leur nom l'indique, procèdent par un calcul en série de gauche à droite ou de droite à gauche ou procèdent par un calcul en parallèle, de leurs arguments, et dans les trois cas intérompt le calcul en retournant 1 lorsque un premier résultat rencontré est 1.
Nous remarquons que les disjonctions sont engendrées par les 4 opérateurs {¬, et, <et, et>}d'une façon analogue à la logique binaire :
¬(x et y) = ¬x ou ¬y
¬(x ou y) = ¬x et ¬y¬(x <et y) = ¬x <ou ¬y
¬(x <ou y) = ¬x <et ¬y¬(x et> y) = ¬x ou> ¬y
¬(x ou> y) = ¬x et> ¬y
Nous pouvons répondre à la question et dire que tous les opérateurs en logique ternaire sont engendrés à partir des 4 opérateurs suivants : ¬, et, <et, et>. Néanmoins il s'avère que les opérateurs logiques séries <et, et> sont des dégénérescences de l'opérateur logique parallèle et. Ils n'apportent aucune information et ne font que réduire la capacité d'expression. La logique ternaire nous apprend simplement qu'il faut implémenter le et parallèle.
Un ensemble constructif se définie toujours dans un ensemble mère plus vaste et plus simple servant de carrière. Et quoi de plus générale comme carrière qu'un langage L d'opérateurs d'arité fixé ?. Prenons par exemple le langage suivant :
L = {a,b,s(.),u(.,.)}
Ce langage engendre par compositions closes d'opérateurs un ensemble mère M. Le signe ° désigne la cloture par arbre clos de compositions des opérateurs :
M = L°
M = {a, b, s(a), s(b), u(a,a), u(b,a), s(s(a)), u(s(b),a)...}
L'ensemble mère M peut être choisie ainsi comme une structure libre définie sur un langage L d'opérateurs d'arité fixée. Mais davantage encore, le langage L va non seulement engendrer M et donc énumérer M, mais il va aussi engendrer et donc énumérer l'ensemble des suites finies d'éléments de M que nous notons M* selon l'opération de Kleene.
On remarque alors une injection de M* vers L*, les suites d'éléments de M correspondent à des suites d'éléments de L. Noter bien la différence entre L° et L*. Dans le premier cas on a un langage d'opéateurs d'arité fixé, et dans le second cas on a un langage de caractères.
L° = {a, b, s(a), s(b), u(a,a), u(b,a), s(s(a)), u(s(b),a)...}
L* = {a, b, s, u, aa, ab, as, au, ba, bb, bs, bu, saa, sba, uabs, bsuu...}
Et l'injection entre M* et L* consiste à enlever les parenthèses (chaque élément de L étant considéré comme un caractère) :
b --> b
a,b --> ab
s(b) --> sb
a,s(s(b)) --> assb
s(a),b,u(a,b) --> sabuab
L'opération inverse utilise la logique polonaise qui consiste à empiler les opérateurs en respectant leur arité et en remplissant dans l'ordre la liste des arguments libres. Par exemple :
suasb --> s(u(a,s(b)))
bsa --> b, s(a)
uu --> u(u(.,.).)
as --> a, s(.)
Le point désigne alors les arguments laissés libres qui se situe toujours en fin de liste. C'est un opérateur d'arité zéro qui pourra être ajouté au langage L.
Nous allons définir une fonction F de codage de M, c'est à dire une application injective de M-->N. Puis nous allons définir un codage optimal, une bijection totalement calculable, simple à calculer, de M*/a-->N où a doit être un opérateur d'arité zéro du langage L, et où M*/a désigne l'ensembles des suites finies d'éléments de M modulo la concaténation à droite avec l'opérateur a.
On associe à chaque opérateur élémentaire un codage successif en prenant soin de commencer par 0 pour un opérateur d'arité zéro:
a=0, b=1, s=2, u=3
On peut alors calculer un code pour chaque mot de M, de la façon suivante : On transforme le mot de M en une chaine de caractère de L* en enlevant les parenthèses. Par exemple :
s(u(a,s(b))) = suasb
Puis on code cette succession de caractères par le développement en base n, où n est le nombre d'opérateurs élémentaires de M c'est à dire le nombre d'éléments de L. On effectue la somme de chaque code d'opérateur multiplié par une puissance de n correspondant à sa place dans la succession. Par exemple
s(u(a,s(b))) = suasb
F(s(u(a,s(b)))) = F(s)*40 + F(u)*41 + F(a)*42 + F(s)*43 + F(b)*44 = 398.
F(s(u(a,s(b)))) = 2*40 + 3*41 + 0*42 + 2*43 + 1*44 = 398.
Le sens du développement n'est pas choisi au hasard. Les caractères de droites ont les puissances les plus grandes. Cela est nécessaire pour que l'ajout de l'opérateur a en fin de mot ne change pas le code.
Et lorsque le mot n'est pas clos, on le clos avec autant d'opérateur de code 0 que nécessaire. Par exemple :
uuu = u(u(u(.,.),.),.)
uuu = u(u(u(a,a),a),a)
uuu = uuuaaaa
L'opération inverse F-1consiste à décomposer un entier en base n, où n est le nombre d'élément de L, et à reconstituer l'emboitement des opérateurs selon le codage de chaque opérateur et selon la logique polonaise, pour retrouver le mot de M corrrespondant. On voit que l'on a définie une fonction énumérante F-1de N-->M qui est une sous-bijection totalement calculable.
On note M* l'ensemble des suites finies d'éléments de M. On note M*/a l'ensemble des suites finie d'élément de M modulo la concaténation à droite avec l'opérateur a. C'est à dire que dans M*/a on a par exemple :
( ) = (a) = (a,a) = ....
(b) = (b,a) = (b,a,a) = ....
(a, s(b)) = (a, s(b),a) = (a, s(b),a,a ) = ....
On étend le codage aux suites finies d'éléments de M modulo la concaténation a droite avec a. Et on obtient ainsi la bijection cherché F-1 : N-->M*/a, une bijection totalement calculable, et simple à calculer. Voyez dans l'exemple suivant :
L={a,b,s(.),u(.,.)} n = |L| = 4 a=0, b=1, s=2, u=3
Code |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
En base n |
0 |
1 |
2 |
3 |
10 |
11 |
12 |
13 |
20 |
21 |
22 |
23 |
30 |
31 |
32 |
33 |
Renversé |
0 |
1 |
2 |
3 |
01 |
11 |
21 |
31 |
02 |
12 |
22 |
32 |
03 |
13 |
23 |
33 |
Mot |
a |
b |
s |
u |
ab |
bb |
sb |
ub |
as |
bs |
ss |
us |
au |
bu |
su |
uu |
Complétion avec des a |
a |
b |
s |
uaa |
ab |
bb |
sb |
uba |
asa |
bsa |
ssa |
usaa |
auaa |
buaa |
suaa |
uuaaa |
Suite |
a |
b |
s(a) |
u(a,a) |
a,b |
b,b |
s(b) |
u(b,a) |
a,s(a) |
b,s(a),a |
s(s(a)) |
u(s(a),a) |
a,u(a,a) |
b,u(a,a) |
s(u(a,a)) |
u(u(a,a),a) |
Code |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
En base n |
100 |
101 |
102 |
103 |
110 |
111 |
112 |
113 |
120 |
121 |
122 |
123 |
Renversé |
001 |
101 |
201 |
301 |
011 |
111 |
211 |
311 |
021 |
121 |
221 |
321 |
Mot |
aab |
bab |
sab |
uab |
abb |
bbb |
sbb |
ubb |
asb |
bsb |
ssb |
usa |
Complétion avec des a |
aab |
bab |
sab |
uab |
abb |
bbb |
sbb |
ubb |
asb |
bsb |
ssb |
usaa |
Suite |
a,a,b |
b,a,b |
s(a),b |
u(a,b) |
a,b,b |
b,b,b |
s(b),b |
u(b,b) |
a,s(b) |
b,s(b) |
s(s(b)) |
u(s(a),a) |
On ajoute l'opérateur point pour désigner un argument libre. L* désigne les suites finies de caractères de L, et il désigne également les suites finies de mots dont le dernier mots n'est pas nécessairement clos mais terminal clos c'est à dire où les arguments libre sont placés à gauche de l'expression. Le code point procède de la même façon que le mini code mais en prenant l'opérateur point pour l'opérateur ayant le code 0. On obtient ainsi une fonction de codage bijective de ( (L ∪ {.})° )*/. --> N.
Par exemples :
L={a,b,s(.),u(.,.)} |L ∪ {.}| = 5 . = 0, a=1, b=2, s=3, u=4
F( s(u(a,s(b))) ) = 3*50 + 4*51 + 1*52 + 3*53 + 2*54 = 1673
F( u(.,s(a)) ) = 4*50 + 0*51 + 3*52 + 1*53 = 204
F( u(.,.),a ) = 4*50 + 0*51 + 0*52 + 1*53 = 129
F( s(b) ) = 3*50 + 2*51 = 13
F( .,a ) = 0*50 + 1*51 = 5
Le code précédent est définie selon un algorithme impératif (constitué de boucles for). On peut construire un code selon une procédé récursif, épousant la récursivité de la construction des mots.
voir Implémentation des langages d'opérateurs
La récurrence est un procédé utilisé pour construire des démonstrations. Elle est définie comme suit :
Soit un prédicat P de N-->{0,1}. Intuitivement cela signifie que à chaque entier x, la propriété P(x) peut être vrai ou fausse. Si nous avons P(0) et que pour tout n appartenant à N on a P(n) => P(n+1), alors cela entraine que pout tout n appartenant à N on a P(n).
Dans notre optique constructive, ce n'est pas la démonstration que nous construisons mais l'objet. La récurrence devient une énumération, l'énumération des entiers x tel que P(x). Cette énumération se fait par un moteur, écrit de façon sous entendu, par :
{0,1,2,3...}
Ou plus formellement par :
<0, x-->s(x)>, où s(x) = x+1.
Ou plus simplement par :
{0, s(.)}°, où s est un opérateur unaire. Les entiers sont définis comme étant les mots de {0, s(.)}°
L'énumération peut parcourir non seulement les entiers mais parcourir des arbres c'est à dire énumérer une structure libre. Dans la suite, N pourra être également une structure libre énumérable, un langage d'opérateurs d'arité fixée. Il s'en suit une notion de récurrence plus générale, un procédé définie comme suit :
Soit un langage d'opérateurs d'arité fixée, par exemple M = {a,b,s(.),u(.,.)}°. Soit un prédicat P de M-->{0,1}. Intuitivement cela signifie que à chaque mot x de M, la propriété P(x) peut être vrai ou fausse. Si la propriété P est vrai pour toutes les constantes élémentaires de M, c'est à dire dans l'exemple, si nous avons P(a) et P(b), et si pour tous mots x, y appartenant à M on a, pour toutes les fonctions élémentaires de M, c'est à dire ici s et u, on a P(x) => P(s(x)) et (P(x) et P(y) ) => P(u(x,y)), alors cela entraine que pout tout x appartenant à M on a P(x).
La récurrence est une énumération, l'énumération des mots x tel que P(x). Cette énumération se fait par un moteur, écrit de façon sous entendu, par :
{a,b,s(a),s(b),u(a,a),u(a,b),u(b,a),u(b,b),s(s(a)),s(s(b)),s(u(a,a)),s(u(b,a))...}
Ou plus formellement par :
<a,b, x-->s(x), (x,y)-->u(x,y)>
Ou plus simplement par :
{a,b,s(.),u(.,.)}°
Le principe d'énumérabilité affirme que tous ce que produit les mathématiques humaines en un temps fini, et même infini, est énumérable, et donc peut être transcrit en utilisant que des objets énumérables. On décline ce principe pour quelque cas cruciaux :
L'ensemble des parties P(N) n'est pas dénombrable. Parcontre l'ensemble des parties semi-décidable de N est dénombrable et énumérable. En effet, une partie semi-décidable de N est définie par une fonction calculable qui l'énumère ou par un fonction caracteristique calculable qui l'accepte, et dit autrement, par une machine de Turing qui l'énumère ou qui l'accepte. Et les machines de Turing sont énumérable, les fonctions calulables de N-->(N union {æ}) sont énumérables, les prédicats calculables de N-->{0,1,æ}sont également énumérables.
On note R(N) l'ensemble des parties semi-décidable de N.
C'est la machine universelle de Turing M qui définie implicitement un langage de programmation. Quelque soit un programme P et une entré x. La machine de Turing qui l'execute est M(P,x). Et on note plus simplement P(x)= M(P,x) en sous-entendant M c'est à dire en sous-entendant la définition d'un langage de programmation.
On définit un programme G dit "énumérateur de programmes" qui énumère tous les programmes possibles. L'ensembles des programmes est alors obtenue par :
{G(0),G(1),G(2)....}
Pour un programme numéroté par i et une entré x, la machine de Turing qui l'éxecute est M(G(i),x) que l'on note également G(i)(x).
On définie pour chaque programme P un sous-ensemble de N définie par {x / P(x)=1}et que l'on note P en laissant au contexte le soin de lever l'ambiguité à savoir si c'est un programme P ou bien une partie de N dont la fonction caractristique est P.
G énumère tous les programmes et donc énumère toutes les parties semi-décidables de N. G est une surjection de N-->R(N).
Parcontre on ne peut pas en dire autant de l'ensemble des parties décidables de N.
Pour décrire la calculabilité des ensembles il faut étudier une des opération clef qu'est la minimalisation
Une machines que l'on bride en s'interdisant ce procédé de minimalisation, ne possède plus le même domaine de calculabilité que celui d'une machine de Turing, et perd la possibilité de toujours pouvoir énumérer le complément d'une partie qu'elle a elle-même énumérée. Pour ces machines ou programmes sans procédé de minimalisation, il apparait alors deux notions distinctes que sont la semi-énumérabilité et l'énumérabilité qui a alors ici un sens différent. Pour ces machines ou programmes sans procédé de minimalisation, la semi-énumérabilité ne garantie pas la possibilité de semi-énuméré le complémentaire, parcontre l'énumérabilité garantie l'énumérabilité du complémentaire. Voir le chapitre " 6- La calculabilité des ensembles "