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