Fonction mécaniquement calculable.

La notion de fonction récursive a été introduite par K. Gödel et J. Herbrand en 1936 à la suite d’études entreprises sur les fondements des mathématiques, plus précisément à propos du problème de la décision. Depuis, cette théorie a été largement développée et apporte un support théorique à différents problèmes de l’informatique.

Définitions des fonctions récursives

Il existe de nombreuses définitions des fonctions récursives adaptées chacune au type de problème que l’on a en vue. Si on désigne par ℕ l’ensemble des entiers naturels et si u ∉ ℕ, ℕ* représentera l’ensemble ℕ ∪ {u}. *F^(p) est l’ensemble des applications de ℕ^(p) dans ℕ*. Si f ∈ *F^(p), on dit que f est une semi-application de ℕ^(p) dans ℕ, dont le domaine est {x/x ∈ ℕ^(p), f (x) ≠ u}. Enfin

Définition arithmétique

On considère les opérations suivantes pour tout n, tout p ∈ ℕ. La superposition

ou

avec pour tout x ∈ ℕⁿ

La récurrence R_n : *F⁽ⁿ⁺²⁾ x *F⁽ⁿ⁾ → *F⁽ⁿ⁺¹⁾
avec
R_n (g, h) = f
ou pour tout x ∈ ℕⁿ, y ∈ ℕ

Enfin, la minisation M_n : *F⁽ⁿ⁺¹⁾ → *F⁽ⁿ⁾ où M_n (g) = f ou pour tout x ∈ ℕⁿ, y ∈ ℕ

Soit alors suc : ℕ → ℕ, la fonction successeur, suc (x) = x + 1, la i-ème projection et Z^(p), p ∈ ℕ, la fonction nulle Z^(p) : ℕ^p → ℕ, Z^(p) (x) = 0, pour tout x ∈ N^p. Dans ces conditions, on peut définir *F_R comme le plus petit sous-ensemble de *F qui contient la fonction successeur, les projections p ∈ ℕ, les fonctions zéro Z^(p), p ∈ ℕ, et qui est stable pour les opérations de substitution, de récurrence et de minisation.

Définition par programme : *F_p

Cette définition est inspirée par le mécanisme des ordinateurs. On suppose que l’on dispose d’une infinité dénombrable de boîtes ou de registres de mémoire dans chacun desquels il est possible d’enregistrer un nombre. Si r est le numéro d’une de ces boîtes, on désigne par < r > le nombre qu’elle contient ; r et < r > appartiennent à ℕ. Pour modifier les nombres contenus dans ces boîtes, on dispose d’instructions à l’aide desquelles on écrit des programmes, c’est-à-dire des suites finies d’instructions. Les instructions que l’on utilise sont les suivantes :
A (r) : augmenter de 1 le nombre contenu dans le registre de numéro r et aller ensuite à l’instruction suivante ;
D (r) : diminuer de 1 le nombre contenu dans le registre de numéro r si < r > > 0 et aller à l’instruction suivante, sinon arrêter le calcul ;
E (r₁, r₂) : porter < r₂ > dans le registre de numéro r₁ ;
T (q_i, q_j) (r) est l’instruction de test : dans un programme, c’est-à-dire une suite finie d’instructions qui chacune porte un nom, q_k, cette instruction a pour effet, suivant que < r > = 0 ou non, d’effectuer après cette instruction l’instruction de nom q_i, ou, respectivement, celle de nom q_j.
Dans ces conditions, f ∈ *F^(p) est calculable par programme s’il existe un programme écrit avec les quatre instructions A (r), D (r), E (r₁, r₂) et T (q_i, q_j) (r), tel que si x₁, ..., x_p sont les nombres placés dans les registres 1 à p, avant calcul, les autres registres étant vides, alors si f (x₁, ..., x_p) ≠ u, ce programme s’arrêtera avec, dans le registre 1, le nombre f (x₁, ..., x_p) et sinon le programme ne s’arrêtera pas.

On désigne par l’ensemble des fonctions calculables par programme. Le programme suivant, dont on explicite à côté l’« organigramme », permet de calculer l’addition de deux nombres dans la mesure où, si x et y sont les nombres placés dans les registres 1 et 2 avant calcul, les autres registres étant vides, ce programme s’arrêtera avec x + y dans le registre 1.

Comme cela est mentionné dans la définition de , un programme peut ne pas s’arrêter lorsqu’on l’applique sur certains arguments. Ainsi par exemple le programme composé de la seule instruction
q₁ : T (q₁, q₁,)   (0)
est un programme qui ne s’arrête jamais.

Définition par formules de type Σ⁺ :

Soit désignant l’ensemble des parties de ℕ^p. On définit un sous-ensemble de d’une façon analogue à celle que l’on a utilisée pour définir *F_R. Plus précisément, est le plus petit sous-ensemble de qui contient les sous-ensembles finis de ℕ, le graphe de l’addition, de la multiplication et qui est stable par réunion, intersection, quantification existentielle, quantification universelle bornée et changements de variables.

Ces diverses opérations, réunion, changement de variables, etc., sont définies dans un ensemble . Pour que A ⊂ ℕ^p appartienne à il est nécessaire et suffisant que A soit la valeur (dans la structure < ℕ, 0, s, S, P, = >, où 0 désigne le nombre zéro, s la fonction successeur, S le graphe de l’addition, P celui de la multiplication et enfin = le graphe de l’égalité) d’une formule du 1^er ordre du langage de cette structure où n’apparaît ni quantification universelle, ni négation, ni implication. L’ensemble Σ⁺ de ces formules est donc l’ensemble des formules qui sont construites à partir des formules atomiques positives par un nombre fini de conjonctions, disjonctions, quantifications existentielles et universelles bornées et quantifications existentielles. On dit alors que si, et seulement si, le graphe de f appartient à .

On peut alors énoncer