|
 |
Sommaire :
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 programme sur un ordinateur tel qu'on le conçoit actuellement mais dans lequel on a enlevé toute limite de temps de calcul et toute limite de quantité de mémoires périphérique initialisée à zéro, et avec comme seul contrainte que le programme doit être de taille finie c'est à dire contenu dans une quantité de mémoire 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 un programme `M` appliqué à une donnée `x` se lance dans un calcul sans fin `M(x)`, cela constitue un bug au sens famillier, et on considère généralement que la fonction calculée par `M` n'est pas définie en `x`. Mais on peut faire autrement. On peut considérer ce comportement, le calcul sans fin, comme un méta-résultat, un oracle, puisqu'il faut se placer à la fin des temps pour être sûr que ce résultat se produise. Auquel cas, ce meta-résultat constitue bien un nouveau méta-élément. Et ce méta-élément qui désigne le calcul sans fin, et qui en constitue son résultat d'une certaine façon, s'appel l'infini de Turing `oo`.
Alan Turing, mathématicien britannique (Londres 1912 - Wilmslow 1954) formalise un ordinateur rudimentaire appelé machine de Turing. Sa mémoire périphérique est une suite de cases, chacune contenant un caractère, sur une bande indéfinie dans les deux sens, avec une case initiale (en jaune sur le dessin) sur laquelle est positionné une tête de lecture-écriture (en forme de triangle sur le dessin) qui peut se déplacer de case en case à droite comme a gauche. Les caractères font partie d'un alphabet fini d'au moins 2 caractères, comprenant le caractère blanc, noté par le symbole ¢.
La machine possède un nombre fini d'états non terminaux numérotés de `1` à `n`. L'état `1` est appelé l'état initial. Et on ajoute un état terminal noté `0`.
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 bien à gauche sur la bande selon la troisième étiquette (`">"` ou `"<"`).
La donnée initiale d'entrée, `x`, est constituée d'un nombre fini de caractères sur la bande en tenant compte de la case initiale, le caractère blanc ¢ occupant toutes les autres places disponibles sur la bande.
La machine démarre en plaçant sa tête de lecture-écriture sur la case initiale et en se mettant à l'état initial. La machine de Turing `M` s'arrête lorsque son automate se trouve sur l'état final `0`. Si l'état final est atteint, le résultat est l'élément `y` écrit sur le ruban, ce qui se note `M(x)"="y`. Si la machine ne s'arrête jamais alors le résultat est l'infini de Turing, ce qui se note `M(x)"="oo`.
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ée `x`, le calcul de `M` appliqué à `x` correspond à la suite des actions exécutées par la machine `M` sur l'entrée `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 deux cas peuvent se produirent :
Le calcul se terminer et le résultat est la valeur `y` écrite sur le ruban.
Le calcul ne se termine jamais auquel cas on dira que le résultat est `oo`, l'infini de Turing.
Notons `W` l'ensemble de toutes les données brutes de tailles finies possibles que l'on peut écrire sur la bande. Les programme transforment les éléments de `W` en éléments de `W+{oo}`. L'éléments `oo` est un méta-élément associé à un comportement spécifique du programme qui consiste à ne jamais s'arrêter. L'infini de Turing, `oo`, n'est pas à proprement parler 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 parmi d'autres. Le programme répond `oo` si et seulement il ne se termine jamais.
La machine de Turing possède deux limitations importantes qu'il convient de rappeler :
Le programme (ou l'automate) comprent `n` états non terminaux, et il se formalise en une application finie de :
`{1,2,3...,n}"×"A -> A"×"{">","<" }"×"{0,1,2,3...,n}`
Cette appliquation prend en entrée un numéro d'état non terminaux et un caractère, puis retourne en sortie, le caractère qui doit être réécrit par dessus, le sens du déplacement d'une case qui doit être effectuer, et le nouvelle état.
Dans l'exemple illustré au paragraphe précédent, nous avons l'alphabet `A = {"a","b","¢"}` où le symbole `"¢"` désigne le caractère blanc.
`(1,"b")|->("a","<",2)`
`(1,"¢")|->("a",">",2)`
`(2,"a")|->("a","<",1)`
`(2,"b")|->("b","<",2)`
`(2,"¢")|->("¢",">",0)`
aab bab bbb bba bba _bba bba
Légende :
Ensemble des états non terminaux. Alphabet utilisé comprenant le caractère blanc `"¢"`. Ensemble des déplacements possibles. État initial. État final.. Ruban contenant aab avec la tête de lecture positionnée sur le premier a.
Le nombre de programmes de `n` états et utilisant un alphabet de `m` caractères, est donc :
`(2m(n+1))^(mn)`
On peut donc associer ainsi de façon biunivoque à chaque entier un programme de machine de Turing.
La succession des opérations faites par la machine de Turing s'appel un calcul. Une fonction calculable est une fonction prenant en entré une donnée écrite sur le ruban et qui, soit ne s'arrête jamais et retourne le méta-élément `oo`, ou soit s'arrête et retourne le résultat écrit sur le ruban.
Mais, la notion de calculabilité ainsi décrite se limite à ce qui peut être écrit sur le ruban. Elle ne permet pas de définir la calculabilité des fonctions opérant sur des ensembles d'éléments qui n'ont pas de représentation écrivable sur le ruban.
Tout ce qui peut être dit par l'Homme est écrivable sur un ruban de machine de Turing. Les élémentariens disent qu'il est inutile de concevoir des objets indisibles possèdant une quantité d'information infini. Car les fondements des mathématiques, s'appuyant sur la mécanique classique, sont déjà assez incertain et donc assurement faux dans ces hypothèses extrêmes.
Pour définir la calculabilité, les élémentariens construisent des éléments calculables qui constituent la fondation de leurs mathématiques, et qui permet de résoudre toutes les contradictions inhérentes aux systèmes logiques d'ordre supérieur.
Une approche simple et classique qui empreinte cette voie, consiste à formaliser les programmes de machine de Turing en des programmes prenant en entrée un entier naturel et s'ils s'arrêtent, retournant en sortie un entier naturel. Cela se fait par exemple en se restreignant à un type de donnée écrite sur le ruban, et en ajoutant à tous les programmes des instructions supplémentaires qui vérifient si le résultat est du bon type et qui sinon se lançe dans un calcul sans fin.
Délors tout programme prend en entrée un entier naturel et s'il s'arrête, retourne en sortie un entier naturel, et s'il ne s'arrête pas, retourne en sortie le méta-élément `oo`, l'infini de Turing, qui désigne un comportement spécifique du programme qu'est le calcul sans fin. D'autre part tout programme est un entier naturel (voir chapitre 3). Le choix d'une telle codification des programmes va définir une structure sur les entiers naturels, appelée la structure de calcul, et mettant en oeuvre la notion de calculabilité. cette structure est munie du méta-élément `oo` et de l'opérateur binaire `U` d'application.
L'opérteur `U"(.,.)"` se note également implicitement par appel fonctionnelle, c'est à dire que `x(y)` signifie `U(x,y)` et désigne le résultat ou méta-résultat du calcul du pogramme `x` appliqué à l'entier `y`. De même `y(x)` signifie `U(y,x)` et désigne le résultat ou méta-résultat du calcul du programme `y` appliqué à l'entier `x`.
`U(x,y) = x(y)`
L'opérateur `oo` se comporte par définition comme suit :
`AAx "∈" NN, x(oo)"="oo"`
`AAx "∈" NN, oo(x)"="oo`
`oo(oo)"="oo"`
Pour chaque définition d'un codage des programmes, ou autrement dit pour chaque définition de `U`, la structure de calcul `(NN, oo, U"(.,.)")` se décline en un système de calcul.
Il existe un algorithme de calcul biunivoque qui permet de passer d'un entier à un couple d'entiers, et donc un entier peut être perçu comme un couple d'entiers. Autrement dit, nous avons l'identité suivante :
`(x,y) = (x(x+1))/2+y`
Et réciproquement :
`n=(p_1(n) ,p_2(n))`
Se faisant, un programme `M` peut être appliqué à un couple d'entiers.
`M(x,y) = M((x(x+1))/2+y)`
Et réciproquement un programme `M` appliqué à un entiers `n` peut produire un couple d'entiers :
`M(n) =(p_1(M(n)),p_2(M(n)))`
Le même programme `M` est perçu différemment selon le type de données choisi pour son entrée et pour sa sortie.
L'opérateur `oo` obét à la règle suivante :
`AAx"∈"NN, (x,oo)=(oo,x)=(oo,oo)=oo`
Il est possible de programmer une machine de Turing dite universelle, `U`, qui prend en entrée un couple d'entiers, comprenant un entier `m` désignant un programme, et un entier `x`, et qui calcule `m(x)`. Notez que `U(m,x)"="oo` si et seulement si `m(x)"="oo`. Nous avons donc :
`U(m,x)=m(x)`
La conception d'une telle machine ne pose pas de difficulté particulière. Il reste néanmoins que sa programmation dans un langage rudimentaire d'automate rerste très fastidieuse.
Le programme `U` correspond alors à l'opérateur binaire d'application dans la structure de calcul `(NN,oo,U"(.,.)")`.
Alan Turing démontre par l'absurde qu'il n'existe pas de programme `P` capable de déterminer en un temps fini si un programme `m` sur une entrée `x` va donner un résultat en un temps fini ou non. Un tel programme ne peut pas exister. Car s'il existait, alors tous les programmes pourrait être transformés en programme d'arrêt sûr, et se faisant, nous pourrions alors calculer et déduire des propositions contradictoires comme nous allons le voir ci dessous en utilisant le procédé de la diagonale de Cantor :
Démonstration par l'absurde : Supposons qu'un tel programme `P` existe. Alors pour tout programme `m` et toute entrée `x`, nous avons :
`P(m,x)"="0 <=> m(x)"="oo`
`P(m,x)"="1 <=> m(x)"≠"oo`
On s'intéresse au programme `f` définie comme suit :
`f(x) = P(x,x)`
Nous appliquons le programme `f` à lui-même `f` :
`f(f) = P(f,f)`
Donc
`f(f) "=" 0 <=> P(f,f)"="0 <=> f(f)"="oo`
Et cela est contradictoire !.
Le fondement de la logique est la programmation. Pour toutes théories, l'ensemble de ses déductions est énumérable. Et donc si la théorie est suffisament riche pour contenir un système de calcul (c'est à dire en terme logique si elle contient l'arithmétique) alors elle ne peut pas énumérer l'ensemble des propositions indémontrables car sinon elle pourrait tout prédire en un temps fini, et en particulier si un programme s'arrête ou non en un temps fini. En conséquence l'ensemble des propositions non décidables par la théorie n'est pas énumérable et donc ne peut pas être vide, et la théorie est donc incomplète.
Considérons un sous-ensemble `A` de `NN`.
`A` est dit semi-énumérable, s'il existe un programme `F` tel que `A"="F(NN)` ou bien `A"+"{oo}"="F(NN)`. Notez que cette dernière expression signifie que `F` n'est pas d'arrêt sûr. On dit que `F` est un semi-énumérateur de `A`.
`A` est dit énumérable, s'il existe un programme `F` tel que `A"="F(NN)`. Notez que cette expression signifie que `F` est d'arrêt sûr. On dit que `F` est un énumérateur de `A`.
`A` est dit énumérable biunivoque, s'il est énuméré de façon biunivoque, c'est à dire s'il existe un programme `F` tel que :
`A"="F(NN)`
`AAxAAy, F(x)"="F(y) => x"="y`
On dit alors que `F` est un énumérateur biunivoque de `A`,
`A` est dit énumérable croissant, s'il est énuméré dans l'ordre c'est à dire s'il existe un programme `F` tel que :
`A"="F(NN)`
`AAxAAy, x"<"y => F(x)"<"F(y)`
On dit que `F` est un énumérateur croissant de `A`,
Le procédé de minimalisation fait qu'il est possible de transformer un semi-énumérateur `F` en un énumérateur `G` et aussi de le transformer en un énumérateur biunivoque et aussi de le transformer en un énumérateur croissant.
Le procédé de minimalisation consiste à lancer un calcul en parallèle dont le parallélisme s'accroit pour couvrir progressivement tout `NN`. Le programme `H` lance le calcul de `F(0),F(1),F(2),...` en parallèle progressivement sans attendre le résultat des calculs `F(x)` lancés, et dès qu'un tel résultat apparait, `H` compare un compteur interne initialisé à zéro avec son entré et si égale retourne le résultat sinon incrémente ce compteur interne et attend qu'un autre résultat surgisse tout en continuant de lancer en parallèle des calculs `F(x"+"1)`. Le procédé de minimalisation nécessite une quantité de mémoire non bornée qui correspond au ruban indéfini de la machine de Turing. Puis on perfectionne ce procédé en ne mémorisant que les résultats distincts, ce qui programme un énumérateur biunivoque. Puis on perfectionne ce procédé en ordonnant les résultats, ce qui programme un énumérateur croissant.
C'est pourquoi il n'y a pas de distinction entre ces 4 types d'ensembles {semi-énumérable, énumérable, énumérable biunivoque, énumérable croissant} et qu'ils ne forment donc qu'un seul type d'ensemble dit simplement énumérable.
---- 1 Aout 2018 ----
On se restreint à un type de machine de Turing prenant en entré un entier puis retournant un entier ou soit `"FAIL"` ou soit l'oracle `oo`. Si la machine retourne une données qui n'est pas un entier alors ce résultat (reconnaissable par une machine de turing) est considéré comme `"FAIL"`.
Dans cette démarche constructive les premier éléments construit sont les entiers
Soit `G` un énumérateur de tous les sprogrammes. Il existe une surjection `varphi` de l'ensemble des programmes `G(NN)` vers l'ensemble des parties énumérables de `NN`.
`varphi : ((G(NN) ↠ ccP(NN)),(G(x) |-> G(x)(NN)))`
Après avoir choisi un énumérateur de tous les sprogrammes, `G`. Tout entier `x` désigne une partie énumérable d'entiers qui est `G(x)(NN)`.
Lorsque `F(NN)=A` on dit que `F` est d'arrêt sûr car il ne produit jamais `oo`.
On appel un ensemble énumérable l'ensemble image d'un programme
La machine comprend un ruban composer de chiffres décimaux, c'est à dire d'entiers compris ente `0` et `9`, et comprend une tête de lecture positionnée sur la case initiale.
Le langage impératif inspiré du brainfuck est composé de 7 symboles : `"<>+-[]⋅"`
Déplace la tête de lecture d'une case sur la gauche. Déplace la tête de lecture d'une case sur la droite. Incrémente l'octet sous la tête de lecture. Décrément l'octet sous la tête de lecture. Saute à l'instruction après le `]` correspondant si l'octet sous la tête de lecture est à zéro. Retouren à l'instruction après le `[` correspondant si l'octet sous la tête de lecture est différent de zéro. Termine le programme
Et il y a une règle syntaxique à respecter : Les parenthèses `[ ]` doivent être emboités.
Les élémentariens disent que tout ce qui peut être dit par l'Homme est écrivable sur un ruban de machine de Turing et qu'il est inutile de concevoir des objets indisibles possèdant une quantité d'information infini. Les fondements des mathématiques s'appuyant sur la mécanique classique sont déjà faible et donc assurement faux dans ces hypothèses extrêmes.
Pour définir la calculabilité, les élémentariens construisent des éléments calculables qui constituent la fondation de leurs mathématiques, et qui permet de résoudre toutes les contradictions inhérentes aux systèmes logiques d'ordre supérieur.
Deux approches possibles sont à envisager. L'une consiste à formaliser les programmes de machine de Turing en des objets plus simples, des fonctions de `NN->NN+{oo}`, et de construire les mathématiques élémentariennes à partir de ces seuls fonctions et des quelques orpérations supplémentaires nécessaires à la mise en oeuvre de la programmation par récurrence. L'autre approche consiste à augmenter le langage de la machine de Turing en ajoutant des caractères à l'alphabet et a changer en même temps son principe de fonctionnement en intégrant des fonctionnalités nouvelles, pour rendre directement écrivable sur le ruban de la machine, tout ce que le mathématicien peut dire.
Puis, en y regardant de plus près, la première approche se subdivise en 3 approches. Car elle est soit trop développée ou soit pas assez développée. Elle privilègie l'ensemble `NN`, et c'est à la fois un avantage et un inconvenient. On envisage donc deux autres approches. L'une reviendra au plus élémentaire de la programmation qu'est le langage de programmation de la machine de Turing ou un équivalent inspiré du Brainfuck, une machine comparable à celle de Turing mais avec un langage de programmation impératif le plus ridimentaire qui puisse exister. L'autre approche considérera non pas `NN` comme structure première mais les structures libres de type énumérable.
Afin d'exploiter pleinement la puissance de raisonnement apportée par le concept de machine de Turing, nous allons construire quelque un langage mathématique en complétant de besoin l'alphabet `A`, ainsi que la définition même des machines de Turing, en même temps que nous explorerons la notion de calculabilité appliquée aux fonctions et aux ensembles.
Une donnée brute comprend ce qui est écrit sur le ruban d'une machine de Turing, c'est à dire une suite de caractères d'alphabet `A` comprenant qu'un nombre fini de caractères autres que le caractère blanc ¢, auxquelles nous ajoutons les deux méta-éléments `FAIL` et `oo` que nous ajoutons à l'alphabet `A` comme deux nouveaux caractères. Ainsi, afin de simplifier la problèmatique, on ajoute les méta-élements FAIL et `oo` dans l'ensemble des données brutes que l'on nomme `W`. On complète ainsi les machines de Turing en leur permettant d'avoir, comme possibilité d'entrée, ces 2 éléments supplémentaires. Mais il apparait alors une contrainte : Le méta-élément `oo` transporte une information sur le comportement du programme le produisant. Il signifie que le programme ne s'arrête jamais. Et donc, toute composition série de programmes comportant un tel programme qui ne s'arrête jamais, forme nécessairement un programme qui ne s'arrête jamais. On en conclut que si un programme `F` avec une donnée `x` forme un calcul sans fin, ce qui se note `F(x)=oo`, alors quelque soit un programme `G` nous aurons `(G@F)(x) = oo` et donc `G(F(x)) = oo` et donc `G(oo)=oo`. On en conclu que :
Tout programme appliquée à `oo` doit retourner `oo`.
Par contre le FAIL n'entraine pas de contrainte, il peut être réutilisé comme une donnée ordinaire. C'est le cas lorsqu'il y a une gestion des erreurs qui est programmée. Ainsi, la notion de programme et de machine de Turing évolue quelque peu en s'enrichissant de fonctionnalités supplémentaires, ici, de l'usage de deux nouvelles entrées possibles avec un comportement spécifique pour l'entrée `oo`.
Les élémentariens considèrent que l'ensemble `W` représente l'ensemble de tous les éléments, et qu'il constitue donc dans la nouvelle théorie naissante, la catégorie des éléments. Et ce principe est équivalent à dire que tout élément possède une quantité d'information finie. Vous aurez remarqué qu'il n'existe pour l'instant aucun moyen de désigner `W` comme une donnée brute (et en soi, cela n'est pas étonnant car `W` n'est pas un ensemble mais une catégorie). Nous pourrions compléter le langage, mais ce n'est pas par là qu'il faut commencer. Il faut commencer par pouvoir exprimer sur le ruban des variables élémentaires, et de pouvoir les quantifier sur `W`. Cela se fait à l'aide du symbole `AA` qui, par défaut, quantifie sur `W` la variable qui suit.
Une application brute est une application sur `W`. Le qualificatif brut signifie que l'application s'applique à des données brutes et retourne des données brutes. Et il faut comprendre que les données brutes comprennent le méta-élément FAIL et le méta-élément `oo`.
Une application brute `f` est calculable si et seulement si il existe un programme `F` vérifiant :
`AAxAAy, f(x)"="y <=> F(x)"="y`
Un programme est dit d'arrêt sûr s'il ne produit jamais l'infini de Turing `oo`.
L'application brute `f` est totalement calculable si et seulement s'il existe un programme `F` vérifiant :
`(AAxAAy, f(x)"="y <=> F(x)"="y)" et "(AAx, f(x)"≠"oo)`
Ainsi une application brute totalement calculable est une application brute calculable en un temps fini, c'est à dire calculable par un programme dont l'arrêt est sûr.
Notez que si l'application brute `f` est calculable alors `f(oo)=oo` puisque c'est le cas par définition pour toute machine de Turing.
---- 28 juillet 2018 ----
Afin de pouvoir dénombrer les fonction, on les munie d'un ou de deux ensembles supports ; d'un ensemble de départ et d'un ensemble d'arrivé, qui peut être le même sans altérer nullement la généralité tout au contraire, et qui pose ainsi un cadre, une délimitation, définissant un ensemble de fonctions pouvant être dénombrées le cas échéant. Pour une fonction `f`, son ensemble de départ se note Dép`(f)` et l'ensemble d'arrivé se note Arr`(f)`. Puis la fonction est une relation qui n'est pas définie partout sur son ensemble de départ. Son domaine de définition se note Dom`(f)` et son image se note Im`(f)`. Evidement par définition nous avons :
Dom`(R) sube` Dép`(R)` Im`(R) sube` Arr`(R)`
Contrairement à une application, une fonction peut être définie sur seulement une partie de son ensemble de départ, un sous-ensemble appelé domaine de définition de la fonction et dont la détermination constitue un second calcul à part en soi. C'est pourquoi une fonction brute peut être calculable ou non et indépendament peut posséder un domaine de définition calculable ou non.
--- 2 décembre 2017 ----
et définissant un type qui permettra le typage des arguments par inférence comme on le verra au chapitre n°5. Par définition nous avons :
| Dom`(R) sube` Dép`(R)` |
| Im`(R) sube` Arr`(R)` |
Avec cette nouvelle définition des données brutes, une fonction brute `f` est une fonction de `W->W`. Et la définition des fonctions brutes calculables et totalement calculable devient alors la suivante :
Etant donnée une fonction brute `f` c'est à dire une fonction sur `W` :
Autrerment dit, une fonction brute totalement calculable est une fonction brute calculable en un temps fini excepté pour la donné `oo`, c'est à dire calculable par un programme dont l'arrêt est sûr pour toutes valeurs autre que `oo`.
--- 2 décembre 2017 ----
Contrairement aux mathématiques classiques qui peuvent conçevoir des ensembles d'éléments inexprimables dans des mondes qui n'existent pas, les élémentariens se ramènent à la seule codification réelle et ne conçoivent donc que des ensembles d'éléments exprimables par des données brutes de `W`, et dont nous verrons par la suite qu'ils devront être, de plus, énumérables ou de complément énumérable.
La donnée est une suite finie de caractères sur le ruban de la machine de Turing. 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 envisageable.
Pour une machine de Turing `M`. 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ées. La donnée 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. On commence par définir les entiers en utilisant les chiffres habituels. Ainsi par exemple la successions de caractères 1425 en partant de la case n°0 du ruban correspondra à l'élément entier 1425. Cette convention que nous choisissons librement, nous permet d'écrire n'importe quel entier sur le ruban d'une machine de Turing,
De même, en ajoutant à l'alphabet des opérateurs `alpha, beta, gamma,...` et les parenthèses ouvrantes et fermantes ainsi que la virgule, nous pouvons écrire sur le ruban de la machine de Turing tout terme du langage d'opérateurs engendré par `alpha, beta, gamma,...`, et cela comprend le langage alpha.
----- 16 septembre 2017 -----
Un premier outils de construction d'éléments consiste à rendre égaux des éléments distincts de `W`. Cette relation d'égalité est construite par une théorie `T` qui pour commencer ne comprend qu'une suite finie d'égalités entre éléments de `W` que nous construisons est une relation d'équivalence sur `W` que l'on note avec le signe égal `=`. Les nouveaux éléments construits sont les classes d'équivalence. L'ensemble de ces classes d'équivalence se note par le quotient de l'ensemble mère `W` par la relation d'équivalence `=`.
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.
---- 31 Août 2017 ----
Posons un alphabet quelconque `A` d'au moins deux caractères. Considérons l'ensemble `W` de toutes les données de tailles finies qu'il est possible d'écrire sur le ruban de la machine de Turing utilisant l'alphabet `A`. Ces données peuvent être énumérés. Et donc l'ensemble des données `W` peut être identifié à `NN`. La machine de Turing devient alors un programme transformant les éléments de `NN` en éléments de `NN uu {`FAIL`, oo}`.
Notez que les éléments FAIL et `oo` sont des éléments extraordinaires associés à des comportements spécifiques du programme. Le programme retourne FAIL si et seulement si il se termine sur un état refusant, et il retourne `oo` si et seulement si il ne s'arrête jamais.
Considérons l'ensemble `ccP` de toutes les programmes de tailles finies qu'il est possible de programmer sur une machine de Turing utilisant l'alphabet `A`. Ces programmes peuvent être énumérés. Et on appel `Psi`, un tel énumérateur de programmes, c'est une application de `NN -> ccP`.
--------- il manque un axiome -------
Puis on définie les fonctions calculables entre ensembles dénombrables quelconques. Etant donné deux ensembles dénombrables `A` et `B`, c'est à dire tels qu'il existe une bijection `ttA` de `NN->A` et une bijection `ttB` de `NN->B`. Ces bijections correspondent à l'inverse de la traduction de l'élément en une donnée inscriptible sur le ruban d'une machine de Turing, et aucune restriction sur leur nature n'est posée apriori. Etant donnée une fonction `f` de `A` vers `B`.
La fonction `f` est dite calculable si et seulement si `ttA f ttB^(-1)` est calculable.
Et la fonction `f` est dite totalement calculable si et seulement si `ttA f ttB^(-1)` est totalement calculable.
Notez les deux différentes notations (française et anglaise) de la composition des fonctions : `ttA f ttB^(-1)` `=` `ttB^(-1)@f@ttA`.
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 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.
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 dans le premier compteur, et de même pour la seconde pile mémorisée sous forme d'un entier dans le second compteur.
---- 26 Août 2017 ----
On mets les éléments extraordinaires FAIL et `oo` dans l'ensemble d'arrivé pour décrire les programmes autorisées. Ainsi
Ensemble des fonctions totalement calculables de A vers B Ensemble des fonctions calculables de A vers B Ensemble des applications totalement calculables de A vers B Ensemble des fonctions calculables de A vers B
A->>B Ensemble des surjections totalement calculables de A vers B A->>(B+{oo}) Ensemble des surjections calculables de A vers B
---- 29 Août 2017 ----
Les programmes vont définir les applications calculables
Remarquez la distinction entre programme et application. Chaque application possède plusieurs programmes la calculant. On dira que le programme implémente l'application `f` si et seulement si il la calcule, et pas seulement pour les éléments ordinaires, mais aussi pour le FAIL et l'infini de Turing `oo`. C'est à dire que le programme appliqué à un entier `x` doit se terminer sur un état FAIL si et seulement si `f(x)"="`FAIL. Et il doit ne jamais s'arrêter si et seulement si `f(x)"="oo`. Et il doit s'arrêter sur END avec un ruban contenant l'entier `y` si et seulement si `f(x)"="y`.
Les machines de Turing définissent les applications calculables de `W` vers `Wuu{"FAIL",oo}` où `W` représente l'ensemble de toutes les données de tailles finies possibles que l'on peut écrire sur la bande, et où les éléments FAIL et `oo` sont des éléments extraordinaires associés à un comportement spécifique des programmes implémentant l'application.
Remarquez la distinction entre programme et application. Chaque application possède plusieurs programmes la calculant. On dira que le programme implémente l'application `f` si et seulement si il la calcule, et pas seulement pour les éléments ordinaires, mais aussi pour le FAIL et l'infini de Turing `oo`. C'est à dire que le programme appliqué à un entier `x` doit se terminer sur un état FAIL si et seulement si `f(x)"="`FAIL. Et il doit ne jamais s'arrêter si et seulement si `f(x)"="oo`. Et il doit s'arrêter sur END avec un ruban contenant l'entier `y` si et seulement si `f(x)"="y`.
Une application calculable de `NN` vers `NNuu{"FAIL",oo}` est une fonction calculable de `NN` vers `{NN,oo}` que l'on étend à tous l'ensemble de départ en donnant comme résultat FAIL là où la fonction n'est pas définie. On note `A->B`, l'ensemble des applications de `A` vers `B`. Et on note `A⇢B`, l'ensemble des fonctions de `A` vers `B` éventuellement étendu en application en donnant comme résultat FAIL là où la fonction n'est pas définie. Nous avons donc :
`NN⇢(NNuu{oo}) = N->(Nuu{"FAIL",oo})`
Selon la philosophie élémentarienne, qui rejette l'axiome du choix, il n'y a rien au delà de l'infini, c'est pourquoi `NN` contient tout.
Une application calculable ou une fonction calculable qui ne produit jamais `oo` est dite totalement calculable.
Notez que le symbole, infini de Turing, `oo`, joue un rôle particulier. Ce n'est pas un élément ordinaire. Il signifie que le calcul ne s'arrête jamais.
Notez aussi que le symbole FAIL n'est pas un élément ordinaire. Il joue un rôle particulier. Il signifie que le programme se termine sur un état refusant. Et il constitue la valeur par défaut que retourne une fonction lorsqu'elle n'est pas définie et que l'on étend pour constituer une application.
Notez que c'est la présence de `oo` dans l'ensemble d'arrivé qui précise si l'application calculable ou la fonction calculable peut ne pas être totalement calculable.
Notez que c'est la présence de FAIL dans l'ensemble d'arrivé d'une application qui précise que l'application constitue en faite une fonction vers l'ensemble d'arrivé dans lequel on a enlevé le FAIL.
Remarquez la distinction entre fonction et programme. Chaque fonction possède plusieurs programmes la calculant. On dira que le programme implémente la fonction `f` si et seulement si il la calcule, et pas seulement pour les éléments ordinaires, mais aussi pour le FAIL et l'infini de Turing `oo`. C'est à dire que le programme appliqué à un entier `x` doit se terminer sur un état FAIL si et seulement si `f(x)"="`FAIL. Et il doit ne jamais s'arrêter si et seulement si `f(x)"="oo`. Et il doit s'arrêter sur END avec un ruban contenant l'entier `y` si et seulement si `f(x)"="y`.
Et quelque soit l'alphabet fini posé, il existe une bijection totalement calculable entre `NN` et l'ensemble des programmes noté `Psi(NN)`.
totalement calculable qui associe à chaque entier `n` un programme noté `Psi(n)`.
une application calculable de `W` vers `Wuu{"FAIL",oo}` est une fonction calculable de `W` vers `{W,oo}`. La fonction retourne FAIL lorsqu'elle n'est pas définie. On note `A->B`, l'ensemble des applications de `A` vers `B`. Et on note `A⇢B`, l'ensemble des fonctions de `A` vers `B`. Nous avons donc :
`W⇢Wuu{oo} = W->Wuu{"FAIL",oo}`
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 :
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.
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)` où `x` est un élément, l'autre ensembliste telle que `f(E)` où `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)`
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}=Ø}`.
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.
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 :
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`.
-------------------------------------
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 :
partant de `x` et aller sur `y`
partant de `x` et aller sur `y`
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).
de la relation
relation inverse
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 :
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 :
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.