Sequential Real Number Computation and Recursive Relations

In the first author's thesis [Marcial-Romero, J. R., “Semantics of a sequential language for exact real-number computation”, PhD thesis at the University of Birmingham, 2004)], a sequential language, LRT, for real number computation is investigated. The thesis includes a proof that all polynomials are programmable, but that work comes short of giving a complete characterization of the expressive power of the language even for first-order functions. The technical problem is that LRT is non-deterministic. So a natural characterization of its expressive power should be in terms of relations rather than functions. In [Brattka, V., Recursive characterization of computable real-valued functions and relations, Theoretical Computer Science 162 (1) (1996) 45–77], Brattka investigates a formalization of recursive relations in the style of Kleene's recursive functions on the natural numbers. This paper establishes the expressive power of LRTp, a variant of LRT, in terms of Brattka's recursive relations. Because Brattka already did the work of establishing the precise connection between his recursive relations and Type 2 Theory of Effectivity, we thus obtain a complete characterization of first-order definability in LRTp.