5- Les fondements de l'informatique, et l'énumérabilité

1) Introduction

L'exercice consiste à plonger dans l'infiniment petit en décrivant en détaille toutes les opérations élémentaires qui doivent être faites pour effectuer un calcul par une machine. D'où le besoin de définir ce qu'est une machine, ce qu'est une opération élémentaire, jusqu'à quel niveau faut-il la diviser et la quantifier, et comment en créer un langage, qui puisse permettre de piloter une machine. Puis cela consiste à en tirer les conséquences mathématiques, en effectuant une analyse des procédés linguistiques utilisés et des structures mathématiques associées.

Nous appelons fonction calculable, les fonctions qui peuvent être calculées par un ordinateur (tel qu'on le conçoit actuellement) auquel on a enlevé toute limite de temps de calcul et toute limite de quantité de mémoires périphérique, mais dont le programme est de taille finie.

La notion de calculabilité est plus vaste que celles des seuls calculs dont l'arrêt est sûr. Un calcul qui ne s'arrête jamais reste calculable en quelque sorte puisque faisant l'objet d'un calcul, même s'il faut se placer à la fin des temps pour s'assurer que le calcul ne s'arrête jamais.

Si `f(x)` se lance dans un calcul sans fin, cela constitue un bug au sens famillier, et on considère que la fonction `f` n'est pas définie en `x`. Mais on peut considérer cette valeur comme un résultat possible, un oracle, puisqu'il faut se placer à la fin des temps pour être sûr que ce résultat se produise, auquel cas il constitue un élément à part entière, et cet élément que l'on attribut au calcul sans fin s'appel l'infini de Turing `oo`.

2) La machine de Turing

Alan Mathison Turing, mathématicien britannique (Londres 1912 - Wilmslow Cheshire 1954) formalise un ordinateur rudimentaire appelé machine de Turing. Sa mémoire périphérique est une suite de caractères sur une bande indéfinie avec une position initiale (jaune). Les caractères font partie d'un alphabet finie d'au moins 2 caractères, comprenant le caractère blanc Ø. Cette bande est parcourue par un curseur, une tête de lecture/écriture (triangulaire). La machine possède un nombre fini d'états non terminaux numérotés de `1` à `n`, avec deux états supplémentaires dit terminaux, l'état final acceptant nommé `"END"` et l'état final refusant nommé `"FAIL"`. (Dans le cas général, la machine de Turing peut avoir `0`, `1` ou plusieurs état finaux répartis en deux catégories distinctes, les états acceptants et les états refusants) La machine exécute un programme fixé qui est un automate. L'automate est un graphe fléché liant les différents états de la machine. Chaque flèche a 3 étiquettes. L'automate passe d'un état à un autre si le caractère lu sous le curseur correspond à la première étiquette de la flèche. L'automate est déterminé, c'est à dire qu'à chaque caractère lu, il ne propose qu'une et une seule transition d'état possible. À chaque transition d'état, l'automate précise deux actions à exécuter ; l'écriture d'un caractère sous le curseur qui est la deuxième étiquette de la flèche, suivi du déplacement du curseur d'une case à droite ou à gauche sur la bande selon la troisième étiquette (d ou g). L'automate possède un état initial, `1`, et deux états terminaux `"END"` et `"FAIL"`. La données initiales d'entrées, `x`, est constituées d'un nombre fini de caractères sur la bande, le caractère blanc Ø occupe toutes les autres places disponibles sur la bande. La machine démarre en plaçant son curseur à la position initiale et en se mettant à l'état initial. La machine de Turing `M` s'arrête lorsque son automate atteint un état final. Si la machine ne s'arrête jamais alors le résultat est l'infini de Turing, ce qui se note `M(x)=oo`. Si l'état final est `"END"` le résultat est l'élément `y` écrit sur le ruban, ce qui se note `M(x)=y`, parcontre si l'état final est `"FAIL"` le résultat est `"FAIL"` ce qui se note `M(x)="FAIL"`.

La machine de Turing est entièrement définie par son automate qui s'appelle un programme. Le programme s'identifie à l'automate qui s'identifie à la machine. Soit un programme `M` et une donné `x`, le calcul de `M` appliqué à `x` correspond à la suite des actions exécutées par la machine `M` sur l'entré `x`. Autrement dit, on met la machine à son état initial, on écrit la donnée `x` sur son ruban, et on lance le calcul. Le résultat est noté sous forme fonctionnelle `M(x)` et trois cas peuvent se produirent :

  1. Soit le calcul `M(x)` se terminer sur l'état `"END"`, et le résultat est la valeur `y` écrite sur le ruban, ce qui se note `M(x)=y`.
  2. Soit le calcul `M(x)` se terminer sur l'état `"FAIL"` et le résultat est `"FAIL"`, ce qui se note `M(x)="FAIL"`.
  3. Soit le calcul `M(x)` ne se termine jamais auquel cas l'évaluation est `oo`, ce qui se note `M(x)=oo`.

Les machines de Turing définissent les applications calculables de `W->Wuu{"FAIL",oo}`

L'infini de Turing `oo` n'est pas à proprement parlé une réponse, puisqu'il faut se mettre à la fin des temps pour pouvoir enregistrer cette réponse. Néanmoins les mathématiques, fussent-elles élémentariennes, ont cette abstraction qui leur permettent de se placer à la fin des temps comme une hypothèse parmis d'autres.

La machine de Turing possède deux limitations :

3) Formalisation des machines de Turing

Le programme ou l'automate comprenant `n` états non terminaux peut se formaliser en une application de :

       `{1,2,3...,n}×A`                 `->`    `{"END","FAIL",1,2,3...,n}×A×{d,g}`
(Etat-non-terminal, Caractère-lu)       ` |->`       (Etat-suivant, Caractère-écrit, Déplacement)

L'ensemble `{1,2,3...,n}` représente la liste des états non terminaux,
L'ensemble `{"END","FAIL",1,2,3...,n}` représente la liste des états,
L'ensemble `A` représente l'alphabet utilisé comprenant le caractère blanc `ø`. Dans l'exemple `A = {a,b,ø}`,
L'ensemble `{d,g}` représente les déplacements possibles de la tête de lecture/écriture.
L'état `1` désigne l'état initial.
L'état `"END"` désigne l'état final acceptant.
L'état `"FAIL"` désigne l'état final refusant.

Le programme devant être de taille fini, le nombre d'états est fini.

Le nombre de programmes de `n` états non terminaux et utilisant un alphabet de `m` caractères, est :

`(2m(n+2))^(mn)`

Considérons l'ensemble `W` de toutes les données de tailles finies possibles que l'on peut écrire sur la bande. Ces données peuvent être énumérés. Ce faisant, l'ensemble des données `W` peut être identifié à `NN`.

Selon la philosophie intuitionniste, il n'y à rien au delà de l'infini, c'est pourquoi `NN` contient tout.

4) Les fonctions calculables et l'opinion de Church

D'après la célèbre opinion de Church, aucune machine n'a un domaine de fonctions calculables supérieur à celui d'une machine de Turing. Il s'agit d'une opinion et non d'une thèse car les machines font parties du monde physique et non du monde mathématique. En effet, cette opinion ne peut pas constituer un énoncé mathématique puisqu'elle ne présuppose pas de ce qu'est une machine. En revanche, pour chaque langage de programmation, qui formalise un type de machine, l'opinion de Church-Turing se décline en un théorème qui peut alors être démontré le cas échéant.

L'opinion de Church pris dans sa totalité peut être considérée comme une loi physique si l'on considère les machines au sens large comme des systèmes physiques. Et la physique actuelle ne semble pas contredire cette loi…

La fonction est un objet mathématique, la calculabilité est une propriété physique.

5) L'automate à deux piles et l'automate à deux compteurs

Un automate à deux piles a la même portée de calcul qu'une machine de Turing. En effet, un automate à deux piles peut simuler une machine de Turing, en faisant en sorte que grosso modo la partie du ruban située à gauche de la tête de lecture soit enregistrée dans la première pile, et la partie du ruban située à droite de la tête de lecture soit enregistrée dans la seconde pile.

Mais plus étonnant encore, les machines à deux compteurs ont également la même portée de calcul qu'une machine de Turing. Selon le même principe, la donnée de la première pile est simplement mémorisée sous forme d'un entier (premier compteur), et de même pour la seconde pile (second compteur).

6) Le langage de donnés

La donnée est une suite finie de caractères sur le ruban de la machine de Turing (voir §2). La taille de la donnée est le nombre de cases consécutives sur le ruban nécessaire pour couvrir de façon connexe la case initiale et tous les caractères autres que le caractère blanc.

Le pouvoir d'expression de ces suites finies de caractères est le même que celui que nous utilisons pour écrire ce présent document, ainsi que pour écrire toute théorie mathématique, et il ne nécessite qu'un alphabet fini d'au moins 2 caractères. C'est pourquoi on utilise quelque fois `{0,1}` comme alphabet où le `0` correspond au caractère blanc.

La donnée `x`, ainsi que le résultat du calcul `M(x)` lorsque celui-ci se termine en un temps fini sur un état acceptant, ne sont pas typés, et sont donc des suites finies de caractères avec une position singulière qu'est la case initiale.

On peut les typer en adoptant un langage, et en modifiant notre façon de voir, faisant que cette suite de caractères soit perçue comme une donnée structurée, une donné typée que l'on appellera élément. Notez que ce typage fait partie d'un contexte extérieur à la donnée qui n'est pas contenu dans la donnée elle-même, mais qui est posé comme un choix supplémentaire indépendant pouvant être fait aussi bien avant qu'après le choix de la donnée, et qui est le choix d'un langage de donné. La données n'est pas modifiée, seul son interprétation change.

Puisque nous sommes libre de choisir le langage, on choisie le langage qui s'accole le mieux à l'objet de nos recherches, et ce langage est le langage mathématique lui-même, soumis à quelques principes élémentariens que nous allons décrire. Nous reformaliserons ainsi un langage de construction d'éléments, dit langage de donnée.

Les choix de construction des éléments sont ceux que nous utilisons dans notre mathématique. Un élément est une classe d'équivalence de représentants appartenant à `W`. Et on voit alors réapparaître le concept d'univers des constructions possibles, `W"/="`, le quotient par la relation d'équivalence `=` qui est la relation d'équivalence définie par la théorie en cours :

`x"="y    <=>    Self⊢x"="y`

`W"/="` est le méta-ensemble de tous les éléments envisageables que nous avions évoqué au chapitre 2- Philosophie et construction. Car tout doit pouvoir s'écrire de façon finie sur le ruban d'une machine de Turing.

Mais, les éléments étant des classes d'équivalence de représentants, pour qu'une fonction `f` de `W⇢W` soit une fonction de `W"/=" ⇢ W"/="`, il faut qu'elle respecte la relation d'équivalence `=`, à savoir que, si `u, v` sont deux représentants d'un même élément ce qui se note par `u"="v` alors nous devons avoir `f(u)"="f(v)`, ce qui s'obtient en unifiant bon nombres d'éléments entre eux.

Les élémentariens ne font que calculer, et n'envisage comme élément que des éléments faisant l'object d'un calcul, donc devant être écrivables sur le ruban d'une machine de Turing.

7) L'infini de Turing `oo` et le `"FAIL"` élémentarisés

Puisque nous sommes libre de choisir notre langage et que celui-ci doit pouvoir tout dire, on introduit deux éléments nouveaux que sont l'infini de Turing `oo` et le `"FAIL"`. Ces deux éléments pouvant maintenant être écrit sur le ruban d'une machine de Turing, ils peuvent être utilisé à autre chose comme tout élément, mais un certain nombre de contraintes leur sont imposées du fait des charges particulières qu'ils exercent.

Les contraintes imposées sont que l'infini de Turing `oo` désigne exactement les calculs sans fin, et que le `"FAIL"` désigne exactement les calculs se terminant sur l'état `"FAIL"`. Et cela a une conséquence sur la définition d'une machine de Turing, ou plus exactement, la définition d'une machine de Turing dans laquelle on utilise l'infini de Turing `oo` et le `"FAIL"` comme des éléments pouvant être écrit sur le ruban, diffère de celle de la machine de Turing originelle dans laquelle ni l'infini de Turing `oo` ni le `"FAIL"` ne sont des éléments écrivables sur le ruban de la machine.

Les machines de Turing définissent maintenant les applications calculables de :

`Wuu{"FAIL",oo}->Wuu{"FAIL",oo}`

On ajoute comme contrainte supplémentaire le fait que la composition série de deux machines de Turing doit produire une machine de Turing. Cela est le cas, si toute machine de Turing appliquée à `oo` retourne `oo` et si toute machine de Turing appliquée à `"FAIL"` retourne `"FAIL"`.

Quelque soit `f`, une application calculable de `Wuu{"FAIL",oo}->Wuu{"FAIL",oo}` et quelque soit une donnée appartenant à `Wuu{"FAIL",oo}` nous devons avoir :

  1. Le calcul de `f(x)` est sans fin, si et seulement si il s'évalue en l'infini de Turing `f(x)=oo`
  2. Le calcul de `f(x)` se termine sur l'état `"FAIL"` si et seulement si `f(x) ="FAIL"`
  3. `f(oo)=oo`
  4. `f("FAIL")="FAIL"`

Le moyen simple de mettre en place ces `4` règles supplémentaires consiste à tester systématiquement chaque entré et chaque sortie des programmes à l'aide d'une instruction supplémentaire qui, si la donnée est `oo`, lance une boucle sans fin, et si la donnée est `"FAIL"`, va sur l'état `"FAIL"`, et sinon ne fait rien. En terme informatique cela s'appelle un aspect. Les machines de Turing de `Wuu{"FAIL",oo}->Wuu{"FAIL",oo}`, par définition, possèdent cet aspect.

8) Notations élémentaire et ensembliste des fonctions

L'ensemble des fonctions de `A` vers `B` se note `A⇢B`. L'ensemble des applications de `A` vers `B` se note `A->B`. Ainsi nous avons :

`(A->B)  sub  (A⇢B)`

Une fonction calculable `f` possède une définition comprenant un ensemble de départ noté `Dep(f)` et un ensemble d'arrivée noté `Arr(f)`, ceci afin de pouvoir les dénombrer, ou bien, afin de pouvoir les ordonnées en fonction d'un ordre défini sur l'ensemble de départ et d'un ordre définie sur l'ensemble d'arrivé.

Chaque fonction, `f`, possèdant un ensemble de départ noté `Dep(f)` et un ensemble d'arrivée noté `Arr(f)`, appartient à l'ensemble `Dep(f)⇢Arr(f)`.

On définie l'image de `f` noté `Im(f)` comme étant l'ensemble des images de `f` :

`Im(f)=f(Dom(f))`
`Im(f) sub Arr(f)`

`Dom(f) = f^(-1)(Arr(f))`
`Dom(f) sub Dep(f)`

La fonction `f` est une application si et seulement si `Dom(f) = Dep(f)` c'est à dire ssi elle est définie partout sur son ensemble de départ.

On utilise deux notations, l'une élémentaire telle que `f(x)``x` est un élément, l'autre ensembliste telle que `f(E)` `E` est un ensemble et où `f(E)` représente l'ensembles des images des éléments de `E` pour lesquels `f` est définie. Dans cette notation ensembliste on autorise les contractions d'écriture remplaçant par exemple `f({x})` par `f{x}`.

Pour la notation élémentaire des fonctions, on adopte le mécanisme d'inférence de type. Ainsi, si dans une théorie l'expression `f(x)` apparaît en notation élémentaire, cela signifie que `x` appartient à l'ensemble de départ de `f` c'est à dire que la théorie en question inclus la propriété `x in Dep(f)`. Notez que l'inférence de type, sur l'expression `f(x)`, ne dit pas que `x` doit appartenir à `Dom(f)` mais seulement à `Dep(f)`.

Parcontre pour la notation ensembliste, nous avons par convention `f(E)=f(E nn Dep(f))`, ce qui n'entraine aucune inférence de type. Les ensembles de départ et d'arrivé se comporte comme une restriction faisant que :

`f(E) = f(E nn Dep(f)) nn Arr(f)`

9) Les fonctions sont étendues en des applications

Dans notre approche calculable, la fonction n'est pas un objet pratique. En effet, étant donné une fonction `f` et un élément quelconque `x` appartenant à son ensemble de départ, l'expression `f(x)` peut ne rien désigner et consituer une erreur. Et cela se produit lorsque `x` n'est pas dans le domaine de définition de `f`. Pour palier à cela, on étend la fonction `f` en une application notée `f^(App)(x)` définie sur le même ensemble de départ, en attribuant une image n'appartenant pas à l'ensemble d'arrivé de `f`, aux éléments de l'ensemble de départ de `f` qui sont hors du domaine de définition de `f`.

Notez que pour une fonction calculable, le nombre de tels images doit être fini et correspond aux différents états terminaux refusant que peut posséder une machine de Turing.

L'avantage de cette convention est que si `x` appartient à l'ensemble de départ de `f`, alors `f^(App)(x)` désigne toujours un élément, et si cet élément appartient à l'ensemble d'arrivé de `f`, alors il fait parti de l'image de `f` sinon il n'en fait pas parti et dénote l'echec de l'évaluation de `f(x)`.

Autrement dit, le domaine de définition de la fonction `f` que l'on note `Dom(f)` regroupe tous les éléments `x` de l'ensemble de départ de `f`, et tel que l'évaluation de `f^(App)(x)` soit dans l'ensemble d'arrivé de `f` :

`Dom(f)={x" / " f^(App)(x) in Arr(f)}`

Souvent on attribura comme image aux éléments de l'ensemble de départ hors du domaine de définition, les seuls éléments `"FAIL"` et `oo`, à condition bien entendu que ces éléments ne figurent pas dans l'ensemble d'arrivé de `f`, car auquel cas, la fonction devient une application, c'est à dire qu'elle est définie partout sur son ensemble de départ. L'application considérée `f^(App)`, étendant `f`, possède le même ensemble de départ `Dep(f) = Dep(f^(App))`, mais son ensemble image `Im(f^(App))` comprend des éléments supplémentaires qui sont les valeurs d'échec de la fonction que l'on rencontre au moins une fois en appliquant `f` à un élément de son ensemble de départ, et ainsi son ensemble d'arrivé `Arr(f^(App))` comprend des éléments supplémentaires qui sont des valeurs d'échec de la fonction qui ont été choisies arbitrairement (toujours en nombre fini pour une fonction calculable). Nous avons :

`Im(f^(App))=f(Dep(f))`
`Im(f^(App)) sub Arr(f^(App))`
`Arr(f) uu Im(f^(App)) sub Arr(f^(App))`

L'ensemble `Arr(f^(App))-Arr(f)` regroupe les éléments images dénotant l'échec de l'évaluation de `f`.

L'ensemble `Im(f^(App))-Arr(f)` regroupe les éléments images dénotant l'échec de l'évaluation de `f` que l'on rencontre au moins une fois en appliquant `f` à un élément de son ensemble de départ. `{f ^(App)(x) " / " f{x}=Ø}`.

Les fonction calculables

Une fonction calculable `f` possède une définition plus complète que la simple description d'un calcul, comprenant comme pour toutes les fonctions, un ensemble de départ noté `Dep(f)` et un ensemble d'arrivée noté `Arr(f)`, ceci afin de pouvoir les dénombrer ou de les ordonnées en fonction d'un ordre défini sur l'ensemble de départ et d'un ordre défini sur l'ensemble d'arrivé. Mais plus encore concernant les fonctions calculables, afin de réduire la portée de la proposition "`f` est une relation fonctionnelle" et qu'elle n'entraine pas que la quasi-totalité des éléments soient égaux entre eux, comme on le verra plus-tard.

On utilisera la même notation `A⇢B` pour désigner l'ensemble des fonctions de `A` vers `B` et l'ensemble des fonctions calculables de `A` vers `B`. Et on laissera au contexte le soin de lever l'ambiguité. De même pour l'ensemble des applications calculable de `A` vers `B` que l'on notera pareillement `A->B`.

Tout ce qui est calculable doit pouvoir s'écrire sur le ruban de la machine de Turing, c'est pourquoi nous ne considérons que des ensembles inclus dans `Wuu{"FAIL",oo}` avec une relation d'équivalence relatant l'égalité entre éléments, c'est à dire que deux représentants sont équivalents ssi ils représentent le même élément.

Une fonction `f` est dite calculable si et seulement s'il existe une Machine de Turing (ne possédant qu'un seul état terminal d'échec `"FAIL"`) qui la calcul. Et il y a différents modes enviseageables selon que l'`oo` et le `"FAIL"` sont présents ou non dans l'ensemble d'arrivé de `f`. Les résultats `"FAIL"` et `oo` désignent l'echec du calcul sauf si le `"FAIL"` ou `oo` font parti de l'ensemble d'arrivé au quel cas ils ne sont pas considérés commme des échecs du calcul mais comme une réponse particulière courcircuitant les créneaux habituelles.

---- 15 Août 2016 ----

 

 

 

 

L'introduction de ces deux éléments permet de traiter les fonctions calculables comme des applications calculables. Une fonction calculable `f` de `A` vers `B` où l'ensemble `B` ne contient ni `"FAIL"` ni `oo`, s'étend biunivoquement en une application calculable, notée `f^(App)`, de `A` vers `B uu {"FAIL",oo}`, ce qui se note par :

`A⇢B    =    A->B uu {"FAIL",oo}`

Ainsi par convention `f(x)` pourra désigner ces valeurs `"FAIL"` ou `oo` qui ne sont pas dans son ensemble d'arrivé.

`Im(f) = {f(x) " / " f(x) in Arr(f)}`
`Dom(f) = {x " / " x in Dep(f) " et " f(x) in Arr(f)}`
`Im(f^(App)) = {f(x)}`

Rappelez-vous que dans toute proposition où se trouve écrit l'expression `f(x)` cela signifie grâce à la définition de la fonction et à l'inférence de type que `x in Dep(f)`, et grace à la définition de la fonction calculable `f`, que `f(x) in Arr(f)uu{FAIL, oo}`.

Les fonctions dites calculables respecteront nécessairement les contraintes propres aux machine de Turing.

  1. Toute fonction calculable appliquée à un élément `x` appartenant à son ensemble de départ qui n'appartient pas à son domaine de définition, retournera comme résultat soit l'élément `"FAIL"` n'appartenant pas à l'ensemble d'arrivé ou soit l'élément `oo` n'appartenant pas à l'ensemble d'arrivé.
  2. Toute fonction calculable appliquée à l'élément `"FAIL"` retournera `"FAIL"`.
  3. Toute fonction calculable appliquée à l'élément `oo` retournera `oo`.

Autrement dit pour tout fonction calculable `f` de `Wuu{"FAIL",oo}-> Wuu{"FAIL",oo}` et pour tout élément `x` appartenant à `Wuu{"FAIL",oo}`, nous avons :

  1. `x in Dep(f)-Dom(f)   <=>  (f(x) = "FAIL" " et " "FAIL" !in Arr(f)) " ou " (f(x) = oo " et " oo !in Arr(f))`
  2. `f("FAIL") = "FAIL"`
  3. `f(oo) = oo`

On introduit l'élément `oo`, appelé l'infini de Turing, comme la projection d'un calcul sans fin, sur la fin des temps. Cela permet de donner une valeur à un calcul sans fin. Ainsi une fontion calculable `f` appliquée à une donnée `x` et qui se lance dans un calcul sans fin, s'évalue par l'infini de Turing ce qui se note par `f(x)=oo`. La fonction produit ainsi une valeur `oo` appartenant à l'ensemble d'arrivé ou non selon quelle dénote une réussite ou un echec du calcul, mais cette valeur n'est pas produite en un temps fini. La seul restriction que l'intuitionniste met, c'est que lorsque le calcul ne s'arrête pas en un temps fini, le résultat n'est rien d'autre que l'infini de Turing noté `oo` et n'apporte aucune autre information supplémentaire. Ainsi, si celle-ci est définie comme valeur posssible appartenant à l'ensemble d'arrivé, alors tout calcul `f(x)` sans fin aboutie à cette `oo` est fait que `x in Dom(f)`, et inversement, si celle-ci n'appartient pas à l'ensemble d'arrivé, alors tout calcul `f(x)` sans fin aboutie à cette `oo` est fait que `x !in Dom(f)`.

Pour chaque fonction calculable `f` nous avons `Im(f^(App)) sub (Arr(f) uu {"FAIL",oo})` Car nous avons systématiser l'extention des fonctions calculables en des applications calculables grâce aux deux seuls images `"FAIL"` et `oo`.

 

 

-------------------------------------

 

6) Les relations binaires

Parceque notre analyse consiste à diviser tout problème complexe en parties plus simples (voir chapitre Philosophie et construction), il est opportun de bien connaître l'usage des graphes orientés et biparties, qui peuvent être vus comme des relations binaires et aussi comme des prédicats binaires. Ceci afin de pouvoir bien mener l'art de la subdivision des problèmes.

Une relation `R` de l'ensemble `A` vers l'ensemble `B` est une partie de `A×B`. La relation binaire `R` peut être vue comme ; un ensemble de couples, un prédicat binaire, un graphe. Et chacune de ces vues correspond à une notation :

Ensemble
Prédicat
Graphe
La relation `R` possède un arc
partant de `x` et aller sur `y`
`(x,y) in R`
`R(x,y)`
`xRy`
La relation `R` ne possède pas d'arc
partant de `x` et aller sur `y`
`(x,y) !in R`
`¬ R(x,y)`
`¬ xRy`

On définie la relation inverse de `R` que l'on note `R^(-1)` comme suit :

`xR^(-1)y <=> yRx`

On définie la composition de deux relations `R, S` que l'on note `RS` comme étant tous les liens possibles composé d'un lien de la première relation suivi d'un lien de la seconde relation :

`xRSy <=> EEu, xRu " et " uRy`

On définie l'ensemble image de `x` que l'on note `R{x}`, comme étant l'ensemble des éléments `y` tel que `xRy`. Et on définie de l'ensemble des antécédants de `y` que l'on note `R^(-1){y}`, comme étant l'ensemble des éléments `x` tel que `xRy`.

`R{x} = {y " / " xRy}`
`R^(-1){y} = {x " / " xRy}`

On définie de même l'ensemble image d'un ensemble `X` que l'on note `R(X)`, et l'ensemble des antécédants d'un ensemble `Y` que l'on note `R^(-1)(Y)`.

`R(X) = {y " / " EEx in X, xRy}`
`R^(-1)(Y) = {x " / " EEy in Y, xRy}`

La composition de relations permet de construire des schémas.

Une relation peut posséder différentes propriétées `P` qui sont transitives c'est à dire qui se conservent par composition c'est à dire telles que si `P(R)` et `P(S)` alors `P(RS)`. On trouve d'abord les propriétées classiques ; fonctionnelle, applicative, injective, surjective, que nous reformulons de manière plus adaptés aux relations binaires générales. La propriété d'injectivité désigne une partie des sommets d'un graphe dans laquelle deux arcs n'aboutissent jamais sur un même sommet. La propriété de surjectivité désigne une partie des sommets d'un graphe dans laquelle tous les sommets de la partie en question sont atteints par des arcs aboutissants .

Ses deux propriétés peuvent s'appliquer pour l'ensemble de départ en inversant le sens des arcs et dans ce cas on les appellera fonctionnalité (symbole `"⦂"`) et fluidité (symbole `"<"`). Et on dira applicative si à la fois fonctionnel et fluide (symbole `"="`) .

Les relations fonctionnelles sont les fonctions. Les relations applicatives sont les applications. Les relations fluides sont les sorties.

Ses deux propriétés peuvent peuvent aussi s'appliquer pour l'ensemble d'arrivé et dans ce cas on les appellera injectivité (symbole `"⦂"`) et surjectivité (symbole `">"`). Et on dira bijective si à la fois injective et surjective (symbole `"="`).

Les applications injectives sont les injections. Les applications surjectives sont les surjections. Les application birjectives sont les bijections.

Etant donné une relation de `A` vers `B`, on symbolise ces propriétés à l'aide de deux symboles, le premier symbole (`"⼀"` relation , `"⦂"` fonction, `"<"` sortie, `"="` application) et le second symbole (`"⼀"` pas de propriété, `"⦂"` injectif, `">"` surjectif, `"="` bijectif).

Départ
Arrivé
Symbole
Description
de la relation
Description de la
relation inverse
`"⦂"`
`"<"`
`"⦂"`
`">"`
0
0
0
0
`A" ⼀⼀ "B`
Relation
Relation
0
0
0
1
`A" ⼀> "B`
Relation surjective
Sortie
0
0
1
0
`A" ⼀⦂ "B`
Relation injective
Fonction
0
0
1
1
`A" ⼀= "B`
Relation bijective
Application
0
1
0
0
`A" <⼀ "B`
Sortie
Relation surjective
0
1
0
1
`A" <> "B`
Sortie surjective
Sortie surjective
0
1
1
0
`A" <⦂ "B`
Sortie injective
Fonction surjective
0
1
1
1
`A" <= "B`
Sortie bijective
Surjection
1
0
0
0
`A" ⦂⼀ "B`
Fonction
Relation injective
1
0
0
1
`A" ⦂> "B`
Fonction surjective
Sortie injective
1
0
1
0
`A" ⦂⦂ "B`
Fonction injective
Fonction injective
1
0
1
1
`A" ⦂= "B`
Fonction bijective
Injection
1
1
0
0
`A" =⼀ "B`
Application
Relation bijective
1
1
0
1
`A" => "B`
Surjection
Sortie bijective
1
1
1
0
`A" =⦂ "B`
Injection
Fonction bijective
1
1
1
1
`A" == "B`
Bijection
Bijection

Les propriétées transitives que peuvent posséder une relation sont inombrables. Voici un exemple. La propriété de parité désigne une partie des sommets d'un graphe dans laquelle tous les sommets de la partie en question sont atteints par un nombre paire d'arcs aboutissants (cela peut donc être aucun). Et cette propriété peut s'appliqué à l'ensemble de départ en inversant les arcs (on l'appelera une relation-paire) ou à l'ensemble d'arrivé (et on dira qu'elle est paire). Cette propriété est bien transitive. La composition de relation-paires produit une relation-paire, et la composition de relations paires produit une relation paire.

Autre propriété transitive importante, la calculabilité. La composition de deux fonctions calculables produit une fonction calculable.

Puis on adopte la notation globalisante pour désignant un ensemble de relation. Ainsi par exemples, l'ensemble des relations de `A` vers `B` se note `A" ⼀⼀ "B`, l'ensemble des surjections de `E` vers `F` se note `E" => "F`.

Et l'on peut désigner un ensemble de compositions de relations Ainsi par exemple, l'ensemble des compositions composée d'une fonction surjective de `A` vers `B` et d'une sortie injective de `B` vers `C` , se note `A" ⦂> "B" <⦂ "C`

D'autre part, un ensemble `E` peut être interprété comme une propriété ; vrai si `E` est non vide, et fausse si `E` est l'ensemble vide.

----------------------

 

 

 

 

----

Si l'ensemble d'arrivé ne contient pas l'élément `oo` cela signifie que quelque soit `x` appartenant à l'ensemble de départ de `f`, le calcul de `f(x)` est sûr de s'arréter en un temps fini, ce qui se note `AAx,   f(x)!=oo`. On dira dans ce cas que `f` est d'arrêt sûr.

En d'autre terme, une application calculable dont l'ensemble d'arrivée ne comprend pas `oo` est d'arrêt sûr. tandis que cela n'est pas certain pour une fonction calculable.

A ce stade, lorsque la fonction calculable n'est pas définie en x cela signifie que `f(x)=oo`. Autrement dit une fonction calculable

On dira dans ce cas que l'application calculable `f` est d'arrêt sûr. Une application calculable `f` est d'arrêt sûr si et seulement si `oo !in Im(f)`. Une application calculable `f` n'est pas d'arrêt sûr si et seulement si `oo in Im(f)`.

Si l'ensemble d'arrivé contient l'élément `oo` cela signifie qu'il peut exister des valeurs `x` telle que le calcul de `f(x)` ne s'arrète jamais.

Et inversement si l'ensemble d'arrivé ne contient pas l'élément `oo` cela signifie que quelque soit `x` appartenant à l'ensemble de départ de `f`, le calcul de `f(x)` est sûr de s'arréter en un temps fini, ce qui se note `AAx,   f(x)!=oo`. On dira dans ce cas que l'application calculable `f` est d'arrêt sûr. Une application calculable `f` est d'arrêt sûr si et seulement si `oo !in Im(f)`. Une application calculable `f` n'est pas d'arrêt sûr si et seulement si `oo in Im(f)`.

L'ensemble de départ d'une application calculable `f` se partitionne en deux parties que sont :

  1. Les calculs finis : `f^(-1){Arr(f)-{oo}} = {x " / " f(x)!=oo}`
  2. Les calculs sans fin : `f^(-1){oo}= {x " / " f(x)=oo }`

Dans ces expressions, on n'a pas spécifié à quel ensemble appartient `x` car l'utilisation de l'application `f` sur `x`, par un appel élémentaire mettant en oeuvre l'inférence de type, répond à cette question. L'inférence de type fait que `x` appartient à l'ensemble de départ de `f`.

 

 

 

 

 

 

L'image de `f` que l'on note `Im(f)` est l'ensemble des images des éléments du domaine de définition de `f`. Nous avons :

`Im(f) " inclus dans " Arr(f)uu{"FAIL"}`
`Im(f)=f(Dom(f))`
`Dom(f) = f^(-1)(Im(f))`
`Dom(f) " inclus dans " Dep(f)`

L'ensemble de départ d'une fonction calculable `f` se partitionne en trois parties que sont :

  1. Les calculs finis réussis : `{x " / " f(x) in Arr(f) " et " f(x)!=oo}`
  2. Les calculs finis échoués : `{x " / " f(x) !in Arr(f) " et " f(x)!=oo}`
  3. Les calculs sans fin : `{x " / " f(x)=oo }`

Dans ces expressions, on n'a pas spécifié à quel ensemble appartient `x` car l'utilisation de la fonction `f` sur `x`, par un appel élémentaire mettant en oeuvre l'inférence de type, répond à cette question. L'inférence de type fait que `x` appartient à l'ensemble de départ de `f`.

L'introduction de l'infini de Turing `oo` permet de donner une valeur à un calcul sans fin.

Dans l'univers intuitionniste, tous les ensembles sont énumérables, et il n'existe rien au delà de l'infini de Turing. Autrement dit, une fonction `f` qui appliquée à `x` ne donne pas de réponse en un temps fini, ce qui se note par `f(x)=oo`, produit l'élément `oo` au bout d'un temps infini, et aucune information supplémentaire.

Ainsi, si l'ensemble d'arrivé contient l'élément `oo` cela signifie qu'il peut exister des valeurs `x` telle que le calcul de `f(x)` ne s'arrète jamais. Une fonction calculable `f` est totalement calculable si et seulement si `oo !in Arr(f)`. Notez que dans ce cas la fonction n'est totalement calculable que sur son domaine de définition. Ailleur elle peut n'être que calculable.

Ainsi, si l'élément `"FAIL"` fait parti de l'ensemble d'arrivé, celui-ci ne signifie plus l'echec du calcul mais un résultat particulier, et la fonction est alors définie partout et constitue une application. Formellement, l'echec du calcul signifie qu'il produit un élément en dehors de son ensemble d'arrivé.

 

 

 

 

 

 

...

 

 

Les intuitionnistes n'ont pas créés de notation spécifique pour désigner ces ensembles énumérables. Ils utilisent les mêmes notations que celles utilisées en mathématique classique (utilisant l'axiome du choix), en laissant au contexte le soin de lever l'ambiguité. Ainsi :

L'expression `ccP(E)` désigne l'ensemble des parties énumérables de `E`

L'expression `A->B` désigne l'ensemble des applications calculables de `A` vers `B`. Si `oo !in B` alors l'expression `A->B` désigne l'ensemble des applications calculables d'arrêt sûr de `A` vers `B`

L'expression `A->(Buu{oo})` désigne l'ensemble des applications calculables d'arrêt sûr de `A` vers `Buu{oo}` et désigne aussi l'ensemble des fonctions calculables de `A` vers `B`. Si l'élément `oo` n'appartenant pas à l'ensemble d'arrivé, celui-ci va cumuler le rôle de l'élément `FAIL`.

L'expression `A->(Buu{"FAIL"})` (où `oo !in B`) désigne l'ensemble des application totalement calculables de `A` vers `Buu{FAIL"}` et désigne aussi l'ensemble des fonctions calculables d'arrêt sûr de `A` vers `B`.

L'expression `A->(Buu{"FAIL",oo})` désigne l'ensemble des application calculables de `A` vers `Buu{"FAIL",oo}` et désigne aussi l'ensemble des fonctions calculables de `A` vers `Buu{oo}`, et désigne aussi l'ensemble des fonctions calculables de `A` vers `B`. Notez que dans ce dernier cas, l'élément `oo` comme l'élément `"FAIL"` n'appartiennent pas à l'ensemble d'arrivé, et donc joue tous les deux le rôle de l'élément `FAIL`.

Les entiers naturels `NN` jouent un rôle particulier parcequ'on les a choisi pour servir d'identifiant. Un identifiant est canoniquement représenté par un entier naturel, car cette structure est jugée pour être la plus simple de toute. Elle met en oeuvre un procédé de récurrence simple. Mais il pourrait en être autrement. On peut utiliser toute autre structure tel un langage libre en mettant en oeuvre la règle de réccurence généralisée impliquant l'ensemble des générateurs du langage en question.

 

Les données sur le ruban de la machine de Turing peuvent être codées par les entiers naturels. Ce faisant, tout programme peut être perçu comme calculant une application de `NN` sur `NN`. L'ensemble des parties de `NN` est remplacé par sa version énumérable, qui est l'ensemble des parties énumérables de `NN`, et qui correspond simplement à l'ensemble des programmes. En effet tout programme déterminant une image énumérable inclus dans `NN` et donc déterminant une partie énumérable de `NN`.

L'ensemble des réels `RR` est remplacé par sa version énumérable, l'ensemble des suites de Cauchy énumérables, qui sont les suites à coefficient dans `QQ` convergeantes proposées par le mathématicien français Augustin Louis Cauchy pour définir `RR`, mais en se restreingnant qu'aux suites dont les termes sont énumérables, c'est à dire calculable par un programme de taille finie. Et comme l'ensemble des programmes est énumérable, l'ensembles des suites programmables l'est également.