𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Machines Over the Reals and Non-Uniformity

✍ Scribed by Felipe Cucker

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
908 KB
Volume
43
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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 several resource restrictions. Non‐uniformity appears here in a natural way. However, since this is a technical concept which is not widely known, we summarize in Section 2 some of the intuitive notions, as well as a few basic theorems related to it. In Section 3 we do this for the subject of real machines and then, in Section 4 we present the state of the art of the surveyed topic. We devote Section 1 to introduce the main concepts of complexity theory. Proofs in this article are quite sketchy and are included more to convey intuitive ideas than to completely prove the claimed statements. Bibliographical references to the original literature are supplied for the latter purpose.

πŸ“œ SIMILAR VOLUMES

Analog computers and recursive functions
Analog computers and recursive functions over the reals
✍ Daniel Silva GraΓ§a; JosΓ© FΓ©lix Costa πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 235 KB

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 mod

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.

Some observations and analysis of wind o
Some observations and analysis of wind over non-uniform terrain
✍ Ernest W. Peterson; Leif Kristensen; Chang-Chun Su πŸ“‚ Article πŸ“… 1976 πŸ› John Wiley and Sons 🌐 English βš– 774 KB

## Abstract Continuous measurements of wind were made throughout a layer extending from the surface to a depth of 12m over a distance along the direction of the wind of about 150 metres. It has been found that the variation in the elevation of the underlying terrain has a profound effect, larger th