RÉCURSIVITÉ, logique mathématique

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(r_i, r_j) : porter dans le registre r_i le nombre contenu dans le registre r_j et passer à l'instruction suivante ;

T(q_i, q_j) (r) est l'instruction de transfert : Dans un programme, c'est-à-dire une suite finie d'instructions q₁, q₂, ..., q_i, ..., q_j, ..., q_n ; lorsqu'on rencontre l'instruction T(q_i, q_j)(r) on effectue l'instruction de nom q_i si <r> = 0, sinon on effectue l'instruction de nom q_j.

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[...]