Decidability of the graph of a map in the model of Blum, Shub and Smale.
Corine Ceola · 1996
It is shown that in the theory of computation over a ring proposed by Blum, Shub and Smale in [Bl-Sh-S1], the computability of a map is equivalent to the decidability of its graph if the ring is an algebraically closed field, while over IR, there exist non computable functions whose graphs nevertheless are decidable. 1 Introduction In classical theory of computation, defined for instance using Turing machines [L-P5], the computability of a function (or a map) f is equivalent to the decidability of its graph G f . This is quite obvious. Indeed, it is clear that G f is decidable if f is computable. Conversely, to compute f at a given y, one enumerates the integers t in increasing order, using a decision procedure for G f to check whether (y; t) belongs to G f until the value t = f(y) for which it answers yes is reached. In [Bl-Sh-S1], L. Blum, M. Shub and S. Smale have developped a general theory of computation (the BSS-model) in which the smallest codable information elements belong ...