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-06-08 - Colloque/Présentation - communication orale - Allemand - 15 page(s)

Troestler Christophe , "Equivalence of scalar- and vector-recursion for BSS machines" in 21st Days of Weak Arithmetics, St. Petersburg, Russie, 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)

Abstract(s) :

(Anglais) In the end of the nineties, L. Blum, M. Shub and S. Smale developed their famous model of machines that are able to perform computations directly on the real numbers. The set of functions that are computable for this model can also be described as the closure of some set of basic functions under four operations (composition, juxtaposition, recursion, minimalization). Recursion can be used with scalar- or (a priori more powerfully) with vector-valued functions. In this talk, we will show that, despite the fact that $\IR$ is not computably isomorphic to $\IR^N$ when $N \ne 1$, the classes generated by scalar- and vector-recursion are generally the same. We will also discuss the non-equality case.