Accueilretour

Les fonctions non calculables.

Sémantique

Logique

Infini

Mesure

Probas

Nombres

Physique

Peut-on calculer toutes les valeurs d'une fonction à partir du moment où celle ci est bien définie ? Cette question appelle une formulation plus précise, qui conduit à distinguer les notions suivantes :

  • fonction totale (bien définie pour toutes les valeurs de ses variables) -- c'est ce que les mathématiciens appellent une application ;
  • fonction récursive : programmable à l'aide de boucles for ou while ;
  • fonction récursive primitive : programmable à l'aide de boucles for exclusivement.
Jusqu'à la fin du XIXième siècle, on faisait coïncider la notion de fonction calculable avec l'une et l'autre de ces deux dernières définitions, que l'on ne savait pas distinguer l'une de l'autre.

La fonction d'Ackermann est définie sur N×N par

A ( x,y )  =
⎧
⎨
⎩
y+1  si x=0
A ( x-1,1 )
 si y=0
A ( x-1,A ( x,y-1 ) )
 sinon

Elle constitue un contre-exemple. Elle est totale : puisque la définition de A(x,y) ne fait appel qu'à des valeurs de A en (x' ,y') <lex (x,y) (antérieures pour l'ordre lexicographique), on finit toujours par se ramener à (0,0) . Elle est évidemment récursive.

Pour essayer de démontrer qu'elle est récursive primitive on peut essayer de déterminer des relations explicites selon les valeurs de x. On obtient (par récurrences sur y) :
x 0 1 2 3 4
A(x,y) y+1 y+2 2y+3 2y+3-3 y+322...2-3

... la notation exponentielle ne suffit plus pour représenter les valeurs supérieures.

Les calculs explicites ne sont pas plus accessibles :
  y = 0 1 2 3 4 5 6
x = 0 1 2 3 5 13 65333 ?
1 2 3 5 13 65533 ? ?
2 3 4 7 29 A(4,2) ? :
3 4 5 9 61 ? : :
4 5 6 11 125 ? ? ?
: : : : : : : :

On arrive à A(4,2). Par définition A(4,2) = A(3,A(4,1) ) = A( 3,65533) =265536-3. C'est un nombre de 19729 chiffres décimaux ; il faut 7 pages à Maple pour l'afficher. On peut encore évaluer A(5,0) = A(4,1) = 65533 mais A(5,1) = A(4,A(5,0) ) = A(4,65533) est de loin inaccessible, nous n'arrivons déjà pas à A(4,3) = A(3,A(4,2)))... Quant à la septième colonne, il est tout simplement impossible d'en calculer une seule valeur.

Le point de vue moderne consiste à faire coïncider la notion de fonction calculable avec celle de fonction récursive primitive. On prouve (Dötzel 1991) que la fonction d'Ackermann croît plus vite que toute fonction exponentielle, que toute exponentielle d'exponentielle ou toute exp ∘ ... ∘ exp(x) ... Or toute fonction récursive primitive est dominée par une fonction de type exponentielle itérée.

La fonction d'Ackermann a donc été donc le premier exemple de fonction récursive mais non récursive primitive. D'autres plus élaborés et moins artificiels ont été identifiés par la suite.

On s'est ainsi aperçu avec les progrès de la théorie du calcul qu'il ne suffisait pas qu'une fonction soit bien définie du point de vue mathématique (totale) pour que le calcul pratique d'une de ses valeurs quelconques soit réalisable.