𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Analog computers and recursive functions over the reals

✍ Scribed by Daniel Silva Graça; José Félix Costa

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
235 KB
Volume
19
Category
Article
ISSN
0885-064X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we show that Shannon's general purpose analog computer (GPAC) is equivalent to a particular class of recursive functions over the reals with the flavour of Kleene's classical recursive function theory.

We first consider the GPAC and several of its extensions to show that all these models have drawbacks and we introduce an alternative continuous-time model of computation that solves these problems. We also show that this new model preserves all the significant relations involving the previous models (namely, the equivalence with the differentially algebraic functions).

We then continue with the topic of recursive functions over the reals, and we show full connections between functions generated by the model introduced so far and a particular class of recursive functions over the reals.

📜 SIMILAR VOLUMES

Sequential real number computation and r
Sequential real number computation and recursive relations
✍ J. Raymundo Marcial-Romero; M. Andrew Moshier 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

## 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 fo

Machines Over the Reals and Non-Uniformi
Machines Over the Reals and Non-Uniformity
✍ Felipe Cucker 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 908 KB

## Abstract We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet ‐ say {0,1} ‐ which can be decided by real machines working under sev

On sparseness and Turing reducibility ov
On sparseness and Turing reducibility over the reals
✍ Felipe Cucker 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 517 KB

We prove some results about existence of NP-complete and NP-hard (for Turing reductions) sparse sets on different settings over the real numbers.