RÉCURSIVITÉ, logique mathématique

Carte mentale

Élargissez votre recherche dans Universalis

Complexité

Un programme de calcul x d'une semi-fonction récursive f = ϕ(x) étant donné, où ϕ : → *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 en désignant par m(x) le nombre d'instructions de ce type dans le programme de numéro x pour ∈ 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 définie par

 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 ψ : → *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 première application du chapitre précédent, définissons ψT1 : → *FR(1) 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 pr [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 14 pages

Écrit par :

Classification

Autres références

«  RÉCURSIVITÉ, logique mathématique  » est également traité dans :

CHURCH ALONZO (1903-1995)

  • Écrit par 
  • Françoise ARMENGAUD
  •  • 611 mots

Mathématicien et logicien, philosophe et historien de la logique, Alonzo Church est né le 14 juin 1903 à Washington et mort le 11 août 1995 à Hudson (Ohio). Professeur de mathématiques à l'université de Princeton, directeur du Journal of Symbolic Logic , il est selon Kneale « le plus fidèle des disciples de Frege ». Réputé « platonisant », il défend une conception délibérément réaliste de la propo […] Lire la suite

DÉMONSTRATION THÉORIE DE LA

  • Écrit par 
  • Jean-Yves GIRARD
  •  • 6 260 mots
  •  • 1 média

Dans le chapitre « La logique Π12 »  : […] L'extension des résultats obtenus par Takeuti, Pohlers, Buchholz... pour le schéma de compréhension Π 1 1 à des systèmes plus forts nécessite de remplacer la ω-logique par des logiques correspondant à de plus grandes complexités logiques, Π 2 1 et plus généralement Π 1 n . Le problème de la B -règle, posé par Mostowski est le suivant : Caractériser les énoncés qui sont vrais dans tout modèle da […] Lire la suite

KLEENE STEPHEN COLE (1909-1994)

  • Écrit par 
  • Pierre GOUJON
  •  • 370 mots

Mathématicien américain né à Hartford (Connecticut). Diplômé de l'Amherst College, Stephen C. Kleene entre, en 1930, à l'université de Princeton. Il est docteur de la même université en 1934. Dès cette époque, il partage son temps entre l'enseignement (université du Wisconsin) et la recherche. Il est successivement membre du Conseil national de la recherche scientifique (1957), puis président de l […] Lire la suite

POST EMIL LEON (1897-1954)

  • Écrit par 
  • Bernard JAULIN
  •  • 622 mots

Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l'université Columbia de New York en 1920. Il était membre de l'American Mathematical Society depuis 1918 et de l'Association for Symbolic Logic dès sa fondation en 1935. Sa thèse de doctorat, publiée en 1921, porte sur le calcul propositionnel de A. N. Whitehead et B. Ru […] Lire la suite

Voir aussi

Pour citer l’article

Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE, « RÉCURSIVITÉ, logique mathématique », Encyclopædia Universalis [en ligne], consulté le 16 juin 2021. URL : https://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/