Récursif

"récursif" dans l'encyclopédie

• RÉCURSIVITÉ, logique mathématique

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

  Un ensemble X ⊂ Np est dit récursivement énumérable s'il est la projection d'un ensemble récursif Y de Np+k. Par exemple, l'ensemble :est récursif, car, pour reconnaître (x, y, z, n) ∈ Y, il suffit de calculer xn, yn et zn et de « tester » si xn + yn = zn. Par contre, si :cet ensemble X est récursivement énumérable d'après notre définition, mais on ignore actuellement si X est récursif.

• TURING MACHINE DE

  • Écrit par Bernard PIRE
  • 1 078 mots

  Cette machine peut imprimer ou effacer des symboles, par exemple la partie décimale d'un nombre réel défini par un processus récursif. Turing montre que la plupart des nombres réels ne sont pas calculables au sens où leurs développements décimaux ne peuvent pas être écrits automatiquement par une telle machine. Anticipant de plusieurs décennies la révolution informatique, Turing résout en logicien une des questions centrales des mathématiques.

• RÉCURSIVITÉ, linguistique

  • Écrit par Robert SCTRICK
  • 2 421 mots

  Est dit récursif, dans la linguistique générative, tout élément qui présente la propriété de se reproduire dans l'algorithme d'une structure de phrase à la fois comme constituant et comme constitué, c'est-à-dire à droite et à gauche de la flèche de réécriture. C'est un langage artificiel qui servira ici d'exemple concret : si l'on veut engendrer une suite qui comporte un nombre indéterminé d'occurrences d'un symbole X suivi du même nombre d'occurrences du symbole Y, on aura tout intérêt à considérer qu'il s'agit d'une structure simple et itérée autant de fois qu'on le désire ; pour établir la grammaire de ce langage, on posera en une seule règle que le symbole initial P (phrase) se récrit sous la forme X + P + Y, soit P ⇌ XPY, ce qui donne bien XXPYY, et ainsi de suite.

• FRACTALES

  • Écrit par Bernard PIRE
  • 4 260 mots
  • 2 médias

  Il en découle que toute construction géométrique euclidienne usuelle engendre un objet non fractal ; en fait, une fractale est en général définie par un processus récursif et se prête donc particulièrement bien au dessin assisté par ordinateur. On définit aussi des fractales aléatoires, pour lesquelles le choix de l'opération appliquée à chaque itération suit une loi de probabilité.

• DÉMONSTRATION THÉORIE DE LA

  • Écrit par Jean-Yves GIRARD
  • 33 778 mots
  • 1 média

  Comme un dilatateur est déterminé par sa restriction à la souscatégorie des entiers, il peut être récursif. Le résultat élémentaire sur les dilatateurs est le théorème de forme normale : Théorème. Si l'on a z < F(x), alors on peut écrire z = (z0 ; x0, ..., xn-1 ; x)F, ce qui signifie que : (1) z = F(f ) (z0), si f ∈ I(n, x) est défini par f (0) = x0, .