Recursion theory on the reals, the analog counterpart of recursive function theory, is an approach to continuous-time computation inspired by the models of Classical Physics. In recursion theory on the reals, the disc...
详细信息
Recursion theory on the reals, the analog counterpart of recursive function theory, is an approach to continuous-time computation inspired by the models of Classical Physics. In recursion theory on the reals, the discrete operations of standard recursion theory are replaced by operations on continuous functions such as composition and various forms of differential equations like indefinite integrals, linear differential equations and more general Cauchy problems. We define classes of real recursive functions in a manner similar to the standard recursion theory and we study their complexity. We prove both upper and lower bounds for several classes of real recursive functions, which lie inside the elementary functions, and can be characterized in terms of space complexity. In particular, we show that hierarchies of real recursive classes closed under restricted integration operations are related to the exponential space hierarchy. The results in this paper, combined with earlier results, suggest that there is a close connection between analog complexity classes and subrecursive classes, at least in the region between FLINSPACE and the primitive recursive functions. (C) 2003 Elsevier B.V. All rights reserved.
We present the first continuous-time hybrid computing unit in 65nm CMOS, capable of solving nonlinear differential equations up to 4th order, and scalable to higher orders. Arbitrary nonlinear functions used in such e...
详细信息
ISBN:
(纸本)9781467374729
We present the first continuous-time hybrid computing unit in 65nm CMOS, capable of solving nonlinear differential equations up to 4th order, and scalable to higher orders. Arbitrary nonlinear functions used in such equations are implemented by a programmable clockless continuous-time 8b hybrid architecture (ADC+SRAM+DAC) with activity-dependent power dissipation. We also demonstrate the use of the unit in a low-power cyber-physical systems application.
We present a unit that performs continuous-time hybrid approximate computation, in which both analog and digital signals are functions of continuoustime. Our 65 nm CMOS prototype system is capable of solving nonlinea...
详细信息
We present a unit that performs continuous-time hybrid approximate computation, in which both analog and digital signals are functions of continuoustime. Our 65 nm CMOS prototype system is capable of solving nonlinear differential equations up to 4th order, and is scalable to higher orders. Nonlinear functions are generated by a programmable, clockless, continuoustime 8-bit hybrid architecture (ADC + SRAM + DAC). Digitally assisted calibration is used in all analog/mixed-signal blocks. Compared to the prior art, our chip makes possible arbitrary non-linearities and achieves 16x lower power dissipation, thanks to technology scaling and extensive use of class-AB analog blocks. Typically, the unit achieves a computational accuracy of about 0.5% to 5% RMS, solution times from a fraction of 1 mu s to several hundred mu s, and total computational energy from a fraction of 1 nJ to hundreds of nJ, depending on equation details. Very significant advantages are observed in computational speed and energy (over two orders of magnitude and over one order of magnitude, respectively) compared to those obtained with a modern microcontroller for the same RMS error.
We develop a topological theory of continuous-time automata which replaces finiteness assumptions in the classical theory of finite automata by compactness assumptions. The theory is designed to be as mathematically s...
详细信息
ISBN:
(纸本)9783319276830;9783319276823
We develop a topological theory of continuous-time automata which replaces finiteness assumptions in the classical theory of finite automata by compactness assumptions. The theory is designed to be as mathematically simple as possible while still being relevant to the question of physical feasibility. We include a discussion of which behaviors are and are not permitted by the framework, and the physical significance of these questions. To illustrate the mathematical tractability of the theory, we give basic existence results and a Myhill-Nerode theorem. A major attraction of the theory is that it covers finite automata and continuous automata in the same abstract framework.
暂无评论