DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2002-08-07 - Colloque/Présentation - communication orale - Anglais - 12 page(s)

Troestler Christophe , "Scalar- v.s. vector-recursion for BSS-recursive functions" in Foundations of Computational Mathematics, Minneapolis, USA, 2002

  • Codes CREF : Logique mathématique (DI1170), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Analyse numérique (S835)
  • Instituts UMONS : Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)
Texte intégral :

Abstract(s) :

(Anglais) As in the classical Turing framework, the set of functions that are computable by BSS-machines can also be described as the closure of a set of basic functions by four rules: composition, juxtaposition, recursion, and minimalization [BSS]. In this talk, we will focus on two types of recursion: scalar-recursion which applies only to functions with one-dimensional range and the unconstrained (vector-) recursion. We will show that, most of the time, scalar-recursion is as powerful as vector-recursion and, when this is not the case, we will explain of what the gap between the two consists. [BSS] Lenore Blum, Mike Shub, Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bulletin of the A.M.S., Vol. 21, N. 1, July 1989, 1--46.