Récursive

"récursive" dans l'encyclopédie

• ITÉRATION, mathématique

  • Écrit par Jean-Paul DELAHAYE, Universalis
  • 4 559 mots

  ) La définition récursive de la même fonction consiste à exprimer l'idée que la somme des éléments de L vaut 0 si L est la liste vide, et vaut le résultat de la somme de L[1] (le premier élément de L) et de la somme des éléments de la liste obtenue en supprimant le premier élément de L. En Maple, cela donne : somme récursive := proc (L) if nops(L)=0 then 0 else L[1] + somme récursive(L[2.

• CHURCH ALONZO (1903-1995)

  • Écrit par Françoise ARMENGAUD
  • 3 380 mots

  La notion de fonction récursive (d'entiers positifs) avait été introduite par Gödel à partir d'une suggestion de Herbrand. S. C. Kleene l'avait analysée en détail ; une fonction est récursive générale si sa valeur pour un argument donné peut être calculée à partir d'un ensemble d'équations au moyen de deux règles seulement : remplacement des variables par des nombres, substitution des identiques.

• KLEENE STEPHEN COLE (1909-1994)

  • Écrit par Pierre GOUJON
  • 2 036 mots

  En 1936, il montre, avec Church, que les notions de fonction lambda-définissable et de fonction récursive générale sont identiques ; ces notions permettent de préciser le concept d'algorithme et débouchent sur la description et l'étude des langages des calculateurs. À partir de 1934, Kleene publie de nombreux ouvrages et articles à caractère pédagogique et théorique.

• RÉCURSIVITÉ, logique mathématique

  • Écrit par Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE
  • 49 023 mots

  Du fait qu'il n'existe pas de suite infinie décroissante d'ordinaux, il est facile de voir que l'on définit bien ainsi une fonction g récursive. Kirby et Paris ont démontré que cette fonction g est équivalente du point de vue de la croissance à la fonction fw, introduite par Ackermann en 1940 comme exemple de fonction récursive qui n'est pas récursive primitive.

• POST EMIL LEON (1897-1954)

  • Écrit par Bernard JAULIN
  • 3 418 mots

  ) le calcul de n'importe quelle fonction récursive. Ce résultat de Post est équivalent à la non-résolubilité du problème des mots, que l'on peut formuler de la façon suivante : soient L(X) et L(Y) deux monoïdes libres ayant un nombre fini de générateurs. Dès que [X] ≥ 3, il n'existe pas d'algorithme permettant de décider si deux morphismes (f, g) de L(X) vers (Y) ont une solution commune (un z ∈ L(X) tel que f(z) = g(z) ; f et g sont donnés par leurs valeurs sur X).