3. Complexité
Un programme de calcul x d'une semi-fonction récursive f = ϕ(x) étant donné, où ϕ : N → *FR(1) 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
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 → *FR(1) , 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 : ψ ∈ *FR(2) ; 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 […]
… pour nos abonnés, l'article se prolonge sur 13 pages…
