6- La calculabilité des ensembles

  1. Image et noyau
  2. Les ensembles énumérables et les ensembles décidables
  3. Les ensembles énumérés en ordre
  4. Les ensembles semi-énumérables et les ensembles semi-décidables
  5. L'ensemble des suites finies respecte l'énumérabilité
  6. La calculabilité des ensembles (2ième lecture)
    1. Les prémisses à la définition d'un ensemble
    2. Images et noyaux
  7. Les ensembles décidables
    1. L'énumération et la semi-énumération
    2. Ensembles décidés, ensembles acceptés (semi-décidés)
    3. L'axiome du choix
  8. Les ensembles semi-décidables
    1. La logique ternaire avec l'infini de Turing
  9. Codage et énumération
  10. Récurrence et énumération
  11. Le principe d'énumérabilité

En mathématique, un des concepts clef est l'ensemble. La théorie des ensembles est rendu non constructive à cause de l'axiome du choix qui est utilisé un peu partout. Nous préférons à la notion d'ensemble, la notion de collection ou de configuration qui est définie à un groupe de permutations près des éléments. Et lorsque la collection est infinie, les permutations concidérés sont des bijections totalement calculables. Il est utile de circonscrire la notion trop vaste d'ensemble au travers les préceptes des fondements de l'informatique vus précédemment et ainsi définire ce qu'est un ensemble constructible.

Dans cette exposé nous n'utiliserons que des applications, c'est à dire des fonctions définies partout sur leur ensemble de départ. La fonction définie seulement sur une partie de l'ensemble de départ n'apporte pas ici de libertés supplémentaires significatives pour le propos.

1) Image et noyau

Il y a deux façons fonctionnelles de définir un ensemble `E` à partir d'autres ensembles. On le définit comme image, ou bien comme noyau, 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). C'est à dire, soit à l'aide d'une application `f` définie sur un ensemble père et dont l'image donne `E`, soit à l'aide d'une application `X` définie sur un ensemble mère et dont le noyau donne `E`.

L'ensemble père que nous utilisons est l'ensemble des entiers naturels.

L'ensemble mère est un ensemble contenant `E`, plus simple que `E`.

Ces deux procédés, images et noyaux, se déclinent respectivement pour définir les ensembles énumérables et les ensembles décidables.

Une application `X` est dite caractéristique lorsqu'elle donne au bout d'un temps fini deux seules valeurs possibles `0` ou `1` aux quels on ajoute une troisième valeur oracle possible appelée l'infini de Turing, `oo`, et qui corespond au cas où le cacul ne s'arrête jamais. L'application caractéristique `X` est totalement calculable si son ensemble image est égal à `{0,1}` et est calculable sans l'être totalement si son ensemble image est égal à `{0,1,oo}`. L'application caractéristique `X` partitionne en trois parties son ensemble de départ :

`Arr(X)={0,1,oo}`
`Dep(X)= X^(-1)(0)+X^(-1)(1)+X^(-1)(oo)`

Noter que le signe `+` correspond à l'opération d'union d'ensembles disjoints.

2) Les ensembles énumérables

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 ----

 

3) Les ensembles décidables

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.

4) Les ensembles énumérés en ordre

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.

5) Les ensembles semi-énumérables

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.

5.1) La minimalisation

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.

6) Les ensembles semi-décidables

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` 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.

 

 

 

4) l'ensemble des suites finies respecte l'énumérabilité

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.

5) La calculabilité des ensembles

" Un ensemble est produit par une machine "

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.

5.1) Les prémisses à la définition d'un ensemble

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.

5.2) images et noyaux

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 Ø.

6) Les ensembles décidables

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.

6.1) L'énumération et la semi-énumération

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 :

Image
Injectivité sur E
Application
E
Oui
Bijection totalement calculable
E
Non
Surjection totalement calculable 
E union {Ø}
Oui
Sous-bijection totalement calculable
E union {Ø}
Non
Sous-surjection totalement calculable  
E union {æ}
Oui
Bijection calculable
E union {æ}
Non
Surjection calculable 
E union {Ø,æ}
Oui
Sous-bijection calculable
E union {Ø,æ}
Non
Sous-surjection calculable  

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.

6.2) Ensembles décidés, ensembles acceptés (semi-décidés)

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.

6.3) L'axiome du choix

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.

7) Les ensembles semi-décidables

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.

7.1) La logique ternaire avec l'infini de Turing

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.

x
y
(x et y)
(x et> y)
(x <et y)
0
0
0
0
0
0
1
0
0
0
0
æ
0
0
æ
1
0
0
0
0
1
1
1
1
1
1
æ
æ
æ
æ
æ
0
0
æ
0
æ
1
æ
æ
æ
æ
æ
æ
æ
æ

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é :

x
¬x
0
1
1
0
æ
æ

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.

8) Codage et énumération

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 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.

8.1) Mini code

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-->Na 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)

8.2) Code point

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

8.3) Code définie récurcivement

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

9) Récurrence et énumération

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(.,.)}°

10) Le principe d'énumérabilité

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

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 "