En 1927, Gabriel Sudan a inventé une fonction récursive à deux variables entières, pour répondre à une question mathématique de David Hilbert.
L'année suivante, Wilhelm Ackermann a publié une fonction similaire mais avec trois variables. Ackermann semble avoir créé cette fonction en 1926.
Par la suite, la « fonction d'Ackermann » a été simplifiée en une fonction à deux variables, que voici :
def A(m,n): assert m==int(m) and n==int(n) and m>=0 and n>=0 if m==0: return n+1 elif n==0: return A(m-1,1) else: return A(m-1,A(m,n-1))
Pour des petites valeurs de m
et
n
, le nombre d'appels récursifs de
A(m,n)
est énorme et le calcul de
A(m,n)
peut prendre un temps rédhibitoire.
Par exemple en calculant
A(4,3)
on a typiquement
RuntimeError: maximum recursion depth exceeded while calling a Python object
C'est en 1970 que John McCarthy a publié sa fonction 91, dont voici la version Python :
def M91(n): assert type(n)==int and n>=0 if n>100: return n-10 else: return M91(M91(n+11))
La représentation graphique de cette suite laisse
conjecturer que pour n ≤ 100
,
M91(n)==91
(d'où le nom de la fonction) :
McCarthy a inventé cette fonction pour lancer
un défi : prouver que la fonction est constante
pour n ≤ 101
. La suite de McCarthy
est A103847.
Douglas Hofstadter,
dans son livre,
a étudié plusieurs fonctions récursives nommées G
,
H
, F
et M
, et
finalement Q
.
def G(n): assert n==int(n) and n>=0 if n==0: return 0 else: return n-G(G(n-1))
Hofstadter trouve un moyen de dessiner la fonction
G
sous la forme d'un arbre : pour toute
valeur de n
, on relie les nœuds
n
et G(n)
par une arête
(on dit que n
est le parent
de G(n)
) :
La fonction G est A005206. Le quotient
de deux termes successifs de la suite tend vers
la solution positive de l'équation x²+x-1=0
(environ 0,618).
def H(n): assert n==int(n) and n>=0 if n==0: return 0 else: return n-H(H(H(n-1)))
L'arbre de H a aussi une allure fractale :
La fonction H est A005374. Le quotient
de deux termes successifs de la suite tend vers
la solution de l'équation x³+x-1=0
(environ 0,682).
F
comme femelle et
M
comme mâle.
Ces deux fonctions font l'objet d'une récurrence croisée.
def F(n): assert n==int(n) and n>=0 if n==0: return 1 else: return n-M(F(n-1))
La fonction F est A005378.
Pour construire son arbre, on a besoin de la fonction
M
ci-dessous :
def M(n): assert n==int(n) and n>=0 if n==0: return 0 else: return n-F(M(n-1))
La fonction M est A005379.
Pour construire son arbre, on a besoin de la fonction
F
ci-dessus :
def Q(n): assert n==int(n) and n>=1 if n<=2: return 1 else: return Q(n-Q(n-1))+Q(n-Q(n-2))
La fonction Q (qui n'est pas définie en 0) est A005185. On ne sait pas à l'heure actuelle si Q est définie pour tous les entiers à partir de 1. Hofstadter la décrit comme chaotique. Voici son arbre :
La fonction notée a
s'appelle
fonction à 10 000 $ de Conway.
def a(n): assert n==int(n) and n>=1 if n<=2: return 1 else: return a(a(n-1))+a(n-a(n-1))
Il s'agit de la suite A004001
sur l'OEIS (encyclopédie de Conway et Sloane).
Conway a présenté cette fonction le 15 juillet 1988
et a promis 10 000 $ au premier qui trouverait une valeur
de a(n)
qui soit proche de n/2
.
Douglas Hofstadter dit avoir inventé cette fonction
des années auparavant. Voici son arbre :
Pour étudier la fonction de Conway-Hofstadter, il est nécessaire de dérécursifier la fonction, qui, sous sa forme récursive, est trop longue à calculer. Par exemple avec ce script :
N = 65 X = list(range(N)) Y = [0,1,1] for n in range(3,N): Y.append(Y[Y[n-1]]+Y[n-Y[n-1]]) plot(X,Y,'b-o')
on obtient ce graphique :
Conway a prouvé que a(n)≥n/2
, d'où
l'idée de représenter la différence :
Z = [Y[k]-X[k]/2 for k in range(len(X))] plot(X,Z,'b-o')
ce qui donne
et on peut dézoomer :