RÉCURSIVITÉ, logique mathématique
Les (semi-) fonctions récursives ont été introduites pour donner un équivalent mathématique à la notion métamathématique intuitive de (semi-) fonction effectivement ou mécaniquement calculable (cf. logique mathématique, chap. 4). Par souci de simplicité, nous considérons ici le cas des fonctions des entiers dans les entiers, bien que l'on puisse définir la notion de récursivité pour des fonctions des réels dans les réels, ou pour des fonctionnelles de type supérieur.
Dans la suite, N désigne l'ensemble des entiers naturels et on note F(p) l'ensemble des applications de Np dans N. Soit u ∉ N ; on désigne par N* l'ensemble N ∪ {u} et par *F(p) l'ensemble des applications de Np dans N*. Si f ∈ *F(p), on appelle domaine de f l'ensemble :
L'ensemble des fonctions récursives à p arguments est un sous-ensemble dénombrable de *F(p) qui peut être défini de nombreuses façons différentes. Nous présenterons successivement un point de vue inspiré par l' informatique, une définition arithmétique et enfin une caractérisation de nature logique. Nous indiquerons ensuite quelques propriétés des éléments universels et de la complexité, notions qui s'introduisent de manière naturelle lorsqu'on adopte l'un ou l'autre de ces points de vue.
Définitions des fonctions récursives
Définition informatique
Nous donnerons cette définition de façon informelle, bien qu'elle puisse être présentée de façon rigoureuse dans le cadre de la théorie des automates.
On dispose de « boîtes » (ou registres de mémoire) dans lesquelles on peut enregistrer des nombres entiers naturels. Si n est le numéro d'une boîte, on désigne par <n> le nombre qu'elle contient. On dispose également d'« instructions » à l'aide desquelles on établit des programmes, c'est-à-dire des suites finies d'instructions permettant de modifier les nombres contenus dans ces boîtes. Nous utiliserons des instructions d'un des quatre types suivants :
A(r) : augmenter de 1 le nombre contenu dans la boîte numérotée r et passer à l'instruction suivante du programme ;
D(r) : diminuer de 1 le nombre contenu dans la boîte numérotée r si <r> > 0, sinon ne rien faire, et passer à l'instruction suivante du programme ;
E(ri, rj) : porter dans le registre ri le nombre contenu dans le registre rj et passer à l'instruction suivante ;
T(qi, qj) (r) est l'instruction de transfert : Dans un programme, c'est-à-dire une suite finie d'instructions q1, q2, ..., qi, ..., qj, ..., qn ; lorsqu'on rencontre l'instruction T(qi, qj)(r) on effectue l'instruction de nom qi si <r> = 0, sinon on effectue l'instruction de nom qj.
Donnons un exemple de programme écrit avec le langage précédent :
Le lecteur vérifiera facilement que si x et y sont les nombres placés dans les registres 1 et 2 avant le début du calcul, les autres registres contenant 0, le programme s'arrêtera avec le nombre x + y dans le registre 1. Ainsi, ce programme permet d'effectuer l'addition de deux nombres ; on le désigne par l'abréviation [1, 2] +→ [1] que l'on peut utiliser comme une nouvelle instruction (ou instruction de sous-programme) pour écrire de nouveaux programmes. On peut ainsi enrichir successivement le langage miniature dont nous sommes partis, mais il faut remarquer que les quatre types d'instructions élémentaires que nous avons introduits sont suffisants pour décrire n'importe quel calcul !
Notons qu'un programme peut ne pas s'arrêter pour certaines valeurs des arguments ; par exemple, le programme suivant, composé d'une seule instruction[...]
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Kenneth Mc ALOON : maître de recherche au C.N.R.S.
- Bernard JAULIN : membre de l'Académie des sciences
- Jean-Pierre RESSAYRE : chargé de recherche au C.N.R.S.
Classification
Autres références
-
CHURCH ALONZO (1903-1995)
- Écrit par Françoise ARMENGAUD
- 616 mots
Mathématicien et logicien, philosophe et historien de la logique, Alonzo Church est né le 14 juin 1903 à Washington et mort le 11 août 1995 à Hudson (Ohio). Professeur de mathématiques à l'université de Princeton, directeur du Journal of Symbolic Logic, il est selon Kneale «...
-
DÉMONSTRATION THÉORIE DE LA
- Écrit par Jean-Yves GIRARD
- 6 140 mots
- 1 média
...fini, détermine uniquement (par unicité du prolongement par limites directes) la famille (Pα). Il devient alors possible de parler de B-démonstration récursive, autrement dit nous avons un concept syntaxique. (Mais l'ensemble des indices de B-démonstrations est Π12 .) Et Girard a pu établir en... -
KLEENE STEPHEN COLE (1909-1994)
- Écrit par Pierre GOUJON
- 371 mots
Mathématicien américain né à Hartford (Connecticut). Diplômé de l'Amherst College, Stephen C. Kleene entre, en 1930, à l'université de Princeton. Il est docteur de la même université en 1934. Dès cette époque, il partage son temps entre l'enseignement (université du Wisconsin) et la recherche....
-
POST EMIL LEON (1897-1954)
- Écrit par Bernard JAULIN
- 622 mots
Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l'université Columbia de New York en 1920. Il était membre de l'American Mathematical Society depuis 1918 et de l'Association for Symbolic Logic dès sa fondation...
