Sequential real number computation and recursive relations
✍ Scribed by J. Raymundo Marcial-Romero; M. Andrew Moshier
- Publisher
- John Wiley and Sons
- Year
- 2008
- Tongue
- English
- Weight
- 195 KB
- Volume
- 54
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
In the first author's thesis [10], a sequential language, LRT, for real number computation is investigated. That 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 in terms of functions. In [2], Brattka examines a formalization of recursive relations in the style of Kleene's recursive functions on the natural numbers. This paper is an expanded version of [13] which establishes the expressive power of LRT~p~ , 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 LRT~p~ . (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)