Premium
Sequential real number computation and recursive relations
Author(s) -
MarcialRomero J. Raymundo,
Moshier M. Andrew
Publication year - 2008
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200710065
Subject(s) - characterization (materials science) , primitive recursive function , expressive power , mathematics , μ operator , computation , natural number , connection (principal bundle) , relation (database) , order (exchange) , power (physics) , discrete mathematics , algebra over a field , recursive functions , computer science , pure mathematics , algorithm , theoretical computer science , materials science , geometry , physics , finance , database , quantum mechanics , economics , nanotechnology
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)