Récursivement

"récursivement" 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.

• ROBINSON JULIA (1919-1985)

  • Écrit par Gabriel SABBAGH
  • 5 566 mots

  Matijasevič établit que le dixième problème de Hilbert est indécidable en montrant un résultat spectaculaire conjecturé par Julia Robinson : un ensemble A d'entiers est récursivement énumérable si et seulement si il existe un polynôme P (x0, x1, ..., xn) tel que : a ∈ A↔ P(a, x1, ..., xn) a une racine. En collaboration avec Matijasevič (« Reduction of an arbitrary diophantine equation to one in 13 unknowns », Acta Arithmetica, 1975, est peut-être le résultat le plus spectaculaire), elle s'attacha à établir des raffinements quantitatifs tels que : Il existe un polynôme à n + 3 variables (à coefficients entiers) U(x0, .

• ADJECTIF

  • Écrit par Robert SCTRICK
  • 2 765 mots

  Si, en contrepartie, on adopte une perspective structurale, on définira l'adjectif comme l'élément linguistique dont la distribution, dans l'énoncé non marqué, varie avec les systèmes considérés, mais est tributaire de l'élément vecteur du syntagme nominal, soit qu'on l'intercale récursivement entre le nom et le déterminant, soit qu'il suive le nom.

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD et Philippe FLAJOLET
  • 36 592 mots
  • 3 médias

  On obtient la suite y correspondant au tri de x par la fusion (ou interclassement) des suites u et v, l'algorithme de fusion étant défini récursivement par :Une programmation classique fondée sur ces équations montre que la fusion de u et v s'effectue en O(|u| + |v|) opérations élémentaires. Le tri de n éléments est aussi ramené à deux tris de n/2 éléments suivi d'une fusion de complexité O(n).

• PREUVE, épistémologie

  • Écrit par Fernando GIL
  • 18 357 mots
  • 1 média

  La même convention régit récursivement les propositions complexes formées par l'intermédiaire des connecteurs logico-linguistiques et on dira : (T) X n'est pas vraie si et seulement si p n'est pas vraie ; une proposition obtenue par l'insertion de ou entre p1 et p2 est vraie si et seulement si p1 ou p2 est vraie, etc. On aura alors expliqué intralinguistiquement comment il faut comprendre la correspondance : dire qu'une proposition est vraie équivaut logiquement à affirmer simplement cette proposition.