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.
1. 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 reg […]
… pour nos abonnés, l'article se prolonge sur 13 pages…
