RÉCURSIVITÉ, logique mathématique

Carte mentale

Élargissez votre recherche dans Universalis

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(qiqj)(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 q1 : T(q1q1)(1) ; en d'autres termes, ce programme calcule la semi-fonction u(p) de Np dans N dont le domaine est vide.

On peut maintenant poser la définition suivante, calculatoire ou informatique, des semi-fonctions récursives.

Définition. Une fonction ∈ *F(p) est dite calculable par programme, et on note ∈ *FP(p) s'il existe un programme écrit à l'aide des quatre instructions ci-dessus et de l'instruction « arrêt » tel que, si x1, x2, ..., xp sont les nombres placés avant le début du calcul dans les registres 1 à p, les autres contenant 0, alors, si (x1, ..., xp) ≠ u, le programme s'arrêtera avec (x1, ..., xp) dans le registre 1 et, sinon (si (x1, ..., xp) = u), il ne s'arrêtera pas.

Désignons par *FP l'ensemble réunion des *FP(p) pour ∈ N. On constate immédiatement un certain nombre de propriétés de clôture de cet ensemble ; par exemple la somme, le produit... de deux fonctions calculables par programme l'est encore. En fait, *FP est clos pour des procédés arithmétiques de définition très vastes, notamment la substitution, la récurrence et la minisation. Indiquons ces opérations qui nous conduiront à la définition arithmétique des fonctions récursives introduite simultanément par K. Gödel et J. Herbrand en 1931.

a) La substitution Sn m est une application :

définie par :
où, pour tout ∈ Nn,

b) La récurrence Rn est une application :

définie par :
où, pour tout ∈ Nn, ∈ N,

c) La minisation Mn est une application :

soit ↦ f, où, pour tout ∈ Nn :

Il est facile de voir que *FP est clos pour ces différentes opérations. Par exemple, si ∈ *FP(n+1) , montrons que f = Mn(g) appartient à *FP(n) . Il suffit de construire, à partir d'un programme de calcul de g, un programme de calcul de f. On vérifiera facilement que l'organigramme suivant, dans lequel le programme de calcul de g apparaît sous la forme abrégée d'une instruction de sous-programme, est celui d'un programme de calcul de f.

On démontre ainsi que *FP contient l'ensemble *FR des semi-fonctions récursives que l'on va maintenant définir.

Définition arithmétique

Définition. L'ensemble *FR des semi-fonctions récursives est le plus petit ensemble de semi-fonctions contenant la fonction successeur, suc : → N, définie, pour tout x, par suc x = x + 1, les fonctions proje [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 14 pages

Écrit par :

Classification

Autres références

«  RÉCURSIVITÉ, logique mathématique  » est également traité dans :

CHURCH ALONZO (1903-1995)

  • Écrit par 
  • Françoise ARMENGAUD
  •  • 611 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 « le plus fidèle des disciples de Frege ». Réputé « platonisant », il défend une conception délibérément réaliste de la propo […] Lire la suite

DÉMONSTRATION THÉORIE DE LA

  • Écrit par 
  • Jean-Yves GIRARD
  •  • 6 261 mots
  •  • 1 média

Dans le chapitre « La logique Π12 »  : […] L'extension des résultats obtenus par Takeuti, Pohlers, Buchholz... pour le schéma de compréhension Π 1 1 à des systèmes plus forts nécessite de remplacer la ω-logique par des logiques correspondant à de plus grandes complexités logiques, Π 2 1 et plus généralement Π 1 n . Le problème de la B -règle, posé par Mostowski est le suivant : Caractériser les énoncés qui sont vrais dans tout modèle da […] Lire la suite

KLEENE STEPHEN COLE (1909-1994)

  • Écrit par 
  • Pierre GOUJON
  •  • 370 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. Il est successivement membre du Conseil national de la recherche scientifique (1957), puis président de l […] Lire la suite

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 en 1935. Sa thèse de doctorat, publiée en 1921, porte sur le calcul propositionnel de A. N. Whitehead et B. Ru […] Lire la suite

Voir aussi

Pour citer l’article

Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE, « RÉCURSIVITÉ, logique mathématique », Encyclopædia Universalis [en ligne], consulté le 09 janvier 2022. URL : https://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/