RÉCURSIVITÉ, logique mathématique

Complexité

Un programme de calcul x d'une semi-fonction récursive f = ϕ(x) étant donné, où ϕ : N → *F_R⁽¹⁾ est l'énumération universelle définie dans le chapitre précédent, on peut effectuer deux types de mesures. La première consiste, par exemple, à mesurer le nombre d'instructions d'un certain type de ce programme x. On définit ainsi une application m : N → N en désignant par m(x) le nombre d'instructions de ce type dans le programme de numéro x pour x ∈ P (et 0 sinon). Il est clair que m est une fonction récursive ; dans ces conditions, il pourrait être intéressant de calculer l'application c : N → N définie par

où y ≡ x signifie ϕ(y) = ϕ(x) ; ainsi, c(x) est le nombre minimal d'instructions du type considéré pour calculer la semi-fonction définie par le programme de numéro x. Malheureusement, on déduit immédiatement de la propriété b du chapitre précédent, sous une hypothèse facile à vérifier pour toutes les pseudo-mesures m, que l'application c n'est pas calculable.

La seconde approche consiste à mesurer, par exemple, le nombre d'instructions, la quantité de mémoire, etc., utilisées par le programme de numéro x lorsqu'on l'applique sur l'argument y, en d'autres termes, faire une mesure sur le calcul lui-même.

On définit ainsi une application ψ : N → *F_R⁽¹⁾ , où ψ(x)(y) est une certaine complexité du calcul du programme de numéro x lorsqu'on l'applique sur l'argument y. On constate que toutes les mesures qu'il est naturel de faire sur les calculs (temps, mémoire, etc.) correspondent à des applications ψ qui possèdent les trois propriétés suivantes : ψ ∈ *F_R⁽²⁾ ; dom ψ = ϕ ; le graphe de ψ est récursif.

Les complexités ψ possédant ces trois propriétés n'interviennent pas seulement en informatique. Reprenant la première application du chapitre précédent, définissons ψ_T1 : N → *F_R⁽¹⁾ de la façon suivante :

On constate que ψ_T1 possède les trois propriétés relatives à l'énumération universelle ϕ_T1 des sous-ensembles récursivement énumérables de N et donc que ψ_T1 va posséder toutes les propriétés qui découlent de ces trois axiomes. On peut démontrer par exemple les deux propositions suivantes que nous énoncerons de façon informelle en utilisant le langage de l'informatique afin de les illustrer simplement.

Proposition. Soit ψ une complexité et t ∈ F_R⁽¹⁾ . Il existe f ∈ F_R⁽¹⁾ tel que, pour tout programme i permettant de calculer f, on a :

sauf pour un nombre fini de x.

En d'autres termes, il existe des fonctions dont tout calcul est aussi compliqué que l'on veut.

Proposition (théorème d'accélération de Blum). Soit g ∈ F_R⁽¹⁾ ; alors, pour toute mesure de complexité ψ, il existe f ∈ F_R⁽¹⁾ tel que :

a) Pour tout programme i permettant de calculer f, on a :

sauf pour un nombre fini d'arguments x.

b) Pour tout programme i permettant de calculer f, il existe un programme j de calcul de f tel que :

sauf pour un nombre fini de x.

En d'autres termes, il existe f ∈ F_R⁽¹⁾ dont tout calcul est aussi compliqué que l'on veut (sauf pour un nombre fini d'arguments) et tel que, pour tout programme i, il en existe un autre j dont le calcul, sauf pour un nombre fini d'arguments, est beaucoup moins compliqué que le calcul par le programme i.

Ce dernier résultat est assez déroutant, dans la mesure où il montre l'existence de fonctions n'ayant pas de meilleur programme de calcul. Mais, bien entendu, toutes les fonctions ne possèdent pas la propriété de la fonction f du théorème et le problème de caractériser les fonctions « non accélérables » (pour différents sens de ce mot) reste ouvert. Certains progrès récents laissent supposer l'existence de solutions accessibles. Il en va de même[...]