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 programme sur un ordinateur tel qu'on le conçoit actuellement mais auquel on a enlevé toute limite de temps de calcul et toute limite de quantité de mémoires périphérique initialisée à zéro, mais dont 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 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, ce résultat constitue un nouvel élément. Et cet élément que l'on attribut au calcul sans fin, qui en constitue son résultat d'une certaine façon, s'appel l'infini de Turing `oo`.

2) La machine de Turing

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 avec une position initiale (représentée sur le schéma en jaune). Les caractères font partie d'un alphabet fini d'au moins 2 caractères, comprenant le caractère blanc ¢. Cette bande est parcourue par un curseur, une tête de lecture/écriture (représentée sur le schéma par un triangle).

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.

L'état n°`1` est appelé l'état initial.

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

La donnée initiale d'entrée, `x`, est constituée d'un nombre fini de caractères sur la bande, le caractère blanc ¢ occupant 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 un état acceptant, 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 un état refusant, le résultat est FAIL ce qui se note `M(x)"="`FAIL et on ne retient pas ce qui est écrit sur le ruban.

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 trois cas peuvent se produirent :

`M(x)"="y`
Le calcul se terminer sur un état acceptant, et le résultat est la valeur `y` écrite sur le ruban.
`M(x)"="`FAIL
Le calcul se terminer sur un état refusant et on dira que le résultat est FAIL.
`M(x)"="oo`
Le calcul ne se termine jamais auquel cas on dira que le résultat est `oo`.

On note par `W_(strict)` l'ensemble de toutes les données de tailles finies possibles que l'on peut écrire sur la bande. Les machines de Turing définissent les programmes qui transforment tout élément de `W_(strict)` en élément de `W_(strict)uu{`FAIL`,oo}`. Les éléments de `W_(strict)` sont dit brut et ordinaire. Les éléments FAIL et `oo` sont des éléments extraordinaires associés à des comportements spécifiques du programme. Le programme répond FAIL si et seulement il se termine sur un état refusant. Parcontre 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 parmis d'autres. Le programme répond `oo` si et seulement il ne se termine jamais.

La machine de Turing possède deux limitations qu'il est important de rappeler :

Il existe aussi deux autres notations, le true et le false. On dira que `M(x)"="`true, ou que `M` accepte `x`, si et seulement si le calcul s'arrète en un temps fini sur un état acceptant. Et on dira que `M(x)"="`false, ou que `M` refuse `x`, si et seulement si le calcul s'arrète en un temps fini sur un état refusant. Ainsi le false correspond exactement au FAIL.

`M(x)"="`true
`M` accepte `x`
Le calcul se terminer sur un état acceptant.
`M(x)"="`false
`M` refuse `x`
Le calcul se terminer sur un état refusant.
`M(x)"="`oo
`M` ne détermine pas `x`
Le calcul ne se termine jamais.

3) Formalisation des machines de Turing

Le programme (ou l'automate) comprenant `n` états non terminaux, un état END et un état FAIL se formaliser en une application de :

       `{1,2,3...,n}"×"A   ->   {`END`,`FAIL`,1,2,3...,n}"×"A"×"{"d","g"}`

Cette appliquation prend en entrée un numéro d'état et un caractère, puis retourne en sortie le nouvelle état, le caractère qui doit être réécrit par dessus et le sens du déplacement d'une case qui doit être effectuer.

Dans l'exemple illustré au paragraphe précédent, nous avons :

`A = {"a","b","¢"}`

`(1,"a")|->(1,"b","d")`
`(1,"b")|->(2,"a","g")`
`(1,"¢")|->(2,"a","d")`
`(2,"a")|->(`FAIL`,"a","g")`
`(2,"b")|->(2,"b","g")`
`(2,"¢")|->(`END`,"¢","d")`

Légende :

`{1,2,3...,n}`
Ensemble des états non terminaux.
`{`END`,`FAIL`,1,2,3...,n}`
Ensemble des états.
`A`
Alphabet utilisé comprenant le caractère blanc `"¢"`.
`{"d","g"}`
Ensemble des sens de déplacements possibles de la tête de lecture/écriture.
`1`
État initial.
END
État final acceptant.
FAIL
État final refusant.

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

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

4) Les données brutes strictes

Une donnée brute est 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 ¢. L'ensemble des données brutes se note `W_(strict)`.

Un programme de machine de Turing `M` constitue une application de `W_(strict)` vers `W_(strict)uu{`FAIL`,oo}`. Il est dit d'arrêt sûr s'il ne produit jamais l'infini de Turing `oo`.

Une application brute est une application de `W_(strict)` vers `W_(strict)uu{`FAIL`,oo}`, et elle n'est pas nécessairement calculable. Le qualificatif brut signifie que l'application s'applique à des données brutes et retourne des données brutes ou bien retourne le FAIL ou bien retourne l'infini de Turing `oo`.

On définie les application brutes calculables ainsi que les applications brutes totalement calculables, à partir des programmes de machine de Turing comme suit. Etant donnée une application brute `f` c'est à dire une application de `W_(strict)` vers `W_(strict)uu{`FAIL`,oo}` :

L'application `f` est calculable si et seulement si il existe un programme de machine de Turing `F` vérifiant :

`AAx"∈"W_(strict) AA y"∈"(W_(strict)"∪"{`FAIL`,oo}),  f(x)"="y   <=>   F(x)"="y`

Et l'application `f` est totalement calculable si et seulement si il existe un programme de machine de turing `F` vérifiant :

`AAx"∈"W_(strict) AA y"∈"(W_(strict)"∪"{`FAIL`,oo}),  f(x)"="y   <=>   F(x)"="y`
`AAx"∈"W_(strict) 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.

5) Les données brutes

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

`W    =    W_(strict)uu{`FAIL`,oo}`

Et 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` et une donnée `x` forrme un calcul sans fin `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 de machine de Turing appliquée `oo` doit retourner `oo`.

Par contre le FAIL n'entraine pas de containte, il peut être réutilisé comme une donnée ordinaire.

Avec cette nouvelle définition des données brutes, une application brute `f` est une application sur `W`. Les définitions des applications brutes calculables et totalement calculables deviennent alors les suivantes :

Etant donnée une fonction brute `f` c'est à dire une fonction sur `W` :

L'application `f` est calculable si et seulement si il existe un programme de machine de Turing `F` vérifiant :

`AA(x,y)"∈"W,  f(x)"="y   <=>   F(x)"="y`

Et l'application `f` est totalement calculable si et seulement si il existe un programme de machine de turing `F` vérifiant

`AA(x,y)"∈"W,  f(x)"="y   <=>   F(x)"="y`
`AAx"∈"W,  f(x)"≠"oo`

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.

6) Les fonctions

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 de 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` :

`x in `Dom`(f)`
`<=>`
`(F(x)"≠"`FAIL` "   ou   " F(x)"≠"oo)`
`f(x)"="y`
`<=>`
`F(x)"="y`
`f(x)"="y`
`<=>`
`F(x)"="y`
`f` n'est pas définie en `x`
`<=>`
`(F(x)"=FAIL" "  ou "x"="oo)`

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

7) Le langage de données

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.

6) Le langage de propriété

 

 

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

 

 

-----

 

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

A⇢B
A->(B+{FAIL})
Ensemble des fonctions totalement calculables de A vers B
A⇢(B+{oo})
A->(B+{FAIL, oo})
Ensemble des fonctions calculables de A vers B
A->B
Ensemble des applications totalement calculables de A vers B
A->(B+{oo})

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

 

 

 

 

 

 

 

 

 

 

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.