A Survey of Continuous-Time Computation Theory
---
paper_title: Some mathematical limitations of the general-purpose analog computer

paper_content:

We prove that the Dirichlet problem on the disc cannot be solved by the general-purpose analog computer, by constructing, on the boundary, a function u"0 that does satisfy an algebraic differential equation, but whose Poisson integral u satisfies no algebraic differential equation on some line segment inside the disc.
---
paper_title: DNA solution of hard computational problems

paper_content:

DNA experiments are proposed to solve the famous "SAT" problem of computer science. This is a special case of a more general method that can solve NP-complete problems. The advantage of these results is the huge parallelism inherent in DNA-based computing. It has the potential to yield vast speedups over conventional electronic-based computers for such search problems.
---
paper_title: Algorithms for quantum computation: discrete logarithms and factoring

paper_content:

A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis. >
---
paper_title: On the computational power of neural nets

paper_content:

This paper deals with finite networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a “sigmoidal” scalar nonlinearity to a linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by rational nets. In particular, one can do this in linear time, and there is a net made up of about 1,000 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Furthermore, we assert a similar theorem about non-deterministic Turing Machines. Consequences for undecidability and complexity issues about nets are discussed too.
---
paper_title: Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems

paper_content:

We explore the simulation and computational capabilities of hybrid and continuous dynamical systems. The continuous dynamical systems considered are ordinary differential equations (ODEs). For hybrid systems we concentrate on models that combine ODEs and discrete dynamics (e.g., finite automata). We review and compare four such models from the literature. Notions of simulation of a discrete dynamical system by a continuous one are developed. We show that hybrid systems whose equations can describe a precise binary timing pulse (exact clock) can simulate arbitrary reversible discrete dynamical systems defined on closed subsets of R n . The simulations require continuous ODEs in IR2n with the exact clock as input. All four hybrid systems models studied here can implement exact clocks. We also prove that any discrete dynamical system in rn can be simulated by continuous ODEs in Rt2n+1. We use this to show that smooth ODEs in RI3 can simulate arbitrary Turing machines, and hence possess the power of universal computation. We use the famous asynchronous arbiter problem to distinguish between hybrid and continuous dynamical systems. We prove that one cannot build an arbiter with devices described by a system of Lipschitz ODEs. On the other hand, all four hybrid systems models considered can implement arbiters even if their ODEs are Lipschitz.
---
paper_title: On some Relations between Dynamical Systems and Transition Systems

paper_content:

In this paper we define a precise notion of abstraction relation between continuous dynamical systems and discrete state-transition systems. Our main result states that every Turing Machine can be realized by a dynamical system with piecewise-constant derivatives in a 3-dimensional space and thus the reachability problem for such systems is undecidable for 3 dimensions. A decision procedure for 2-dimensional systems has been recently reported by Maler and Pnueli. On the other hand we show that some non-deterministic finite automata cannot be realized by any continuous dynamical system with less than 3 dimensions.
---
paper_title: The computability and complexity of optical beam tracing

paper_content:

The ray-tracing problem is considered for optical systems consisting of a set of refractive or reflective surfaces. It is assumed that the position and the tangent of the incident angle of the initial light ray are rational. The computability and complexity of the ray-tracing problems are investigated for various optical models. The results show that, depending on the optical model, ray tracing is sometimes undecidable, sometimes PSPACE-hard, and sometimes in PSPACE. >
---
paper_title: On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines

paper_content:

A model for computation over an arbitrary (ordered) ring R is presented. In this general setting, universal machines, partial recursive functions, and NP-complete problems are obtained. While the theory reflects of classical over Z (e.g. the computable functions are the recursive functions), it also reflects the special mathematical character of the underlying ring R (e.g. complements of Julia sets provide natural examples of recursively enumerable undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis. >
---
paper_title: Analog computation with continuous ODEs

paper_content:

Demonstrates simple, low-dimensional systems of ODEs that can simulate arbitrary finite automata, push-down automata, and Turing machines. We conclude that there are systems of ODEs in R/sup 3/ with continuous vector fields possessing the power of universal computation. Further, such computations can be made robust to small errors in coding of the input or measurement of the output. As such, they represent physically realizable computation. We make precise what we mean by "simulation" of digital machines by continuous dynamical systems. We also discuss elements that a more comprehensive ODE-based model of analog computation should contain. The "axioms" of such a model are based on considerations from physics. >
---
paper_title: The Computational Power of Continuous Time Neural Networks

paper_content:

We investigate the computational power of continuous-time neural networks with Hopfield-type units. We prove that polynomial-size networks with saturated-linear response functions are at least as powerful as polynomially space-bounded Turing machines.
---
paper_title: Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems

paper_content:

The author establishes a number of properties associated with the dynamical system H=(H,(H,N)), where H and N are symmetric n-by-n matrices and (A,B)=AB-BA. The most important of these come from the fact that this equation is equivalent to a certain gradient flow on the space of orthogonal matrices. Particular emphasis is placed on the role of this equation as an analog computer. For example, it is shown how to map the data associated with a linear programming problem into H(0) and N in such a way as to have H=(H(H,N)) evolve to a solution of the linear programming problem. This result can be applied to find systems that solve a variety of generic combinatorial optimization problems, and it also provides an algorithm for diagonalizing symmetric matrices. >
---
paper_title: Computability with low-dimensional dynamical systems

paper_content:

It has been known for a short time that a class of recurrent neural networks has universal computational abilities. These networks can be viewed as iterated piecewise-linear maps in a high-dimensional space. In this paper, we show that similar systems in dimension two are also capable of universal computations. On the contrary, it is necessary to resort to more complex systems (e.g., iterated piecewise-monotone maps) in order to retain this capability in dimension one.
---
paper_title: Complexity theory and genetics

paper_content:

We introduce a population genetics model in which the operators are effectively computable-computable in polynomial time on probabilistic Turing machines. We shall show that in this model a population can encode easily large amount of information from environment into genetic code. Then it can process the information as a parallel computer. More precisely, we show that it can stimulate polynomial space computations in polynomially many steps, even if the recombination rules are very simple. >
---
paper_title: Optical Computing: A Survey for Computer Scientists

paper_content:

Optical Computers provides the first in-depth review of the possibilities and limitations of optical data processing.
---
paper_title: On the computational power of neural nets

paper_content:

This paper deals with finite networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a “sigmoidal” scalar nonlinearity to a linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by rational nets. In particular, one can do this in linear time, and there is a net made up of about 1,000 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Furthermore, we assert a similar theorem about non-deterministic Turing Machines. Consequences for undecidability and complexity issues about nets are discussed too.
---
paper_title: Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems

paper_content:

We explore the simulation and computational capabilities of hybrid and continuous dynamical systems. The continuous dynamical systems considered are ordinary differential equations (ODEs). For hybrid systems we concentrate on models that combine ODEs and discrete dynamics (e.g., finite automata). We review and compare four such models from the literature. Notions of simulation of a discrete dynamical system by a continuous one are developed. We show that hybrid systems whose equations can describe a precise binary timing pulse (exact clock) can simulate arbitrary reversible discrete dynamical systems defined on closed subsets of R n . The simulations require continuous ODEs in IR2n with the exact clock as input. All four hybrid systems models studied here can implement exact clocks. We also prove that any discrete dynamical system in rn can be simulated by continuous ODEs in Rt2n+1. We use this to show that smooth ODEs in RI3 can simulate arbitrary Turing machines, and hence possess the power of universal computation. We use the famous asynchronous arbiter problem to distinguish between hybrid and continuous dynamical systems. We prove that one cannot build an arbiter with devices described by a system of Lipschitz ODEs. On the other hand, all four hybrid systems models considered can implement arbiters even if their ODEs are Lipschitz.
---
paper_title: Analog computation with continuous ODEs

paper_content:

Demonstrates simple, low-dimensional systems of ODEs that can simulate arbitrary finite automata, push-down automata, and Turing machines. We conclude that there are systems of ODEs in R/sup 3/ with continuous vector fields possessing the power of universal computation. Further, such computations can be made robust to small errors in coding of the input or measurement of the output. As such, they represent physically realizable computation. We make precise what we mean by "simulation" of digital machines by continuous dynamical systems. We also discuss elements that a more comprehensive ODE-based model of analog computation should contain. The "axioms" of such a model are based on considerations from physics. >
---
paper_title: Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems

paper_content:

The author establishes a number of properties associated with the dynamical system H=(H,(H,N)), where H and N are symmetric n-by-n matrices and (A,B)=AB-BA. The most important of these come from the fact that this equation is equivalent to a certain gradient flow on the space of orthogonal matrices. Particular emphasis is placed on the role of this equation as an analog computer. For example, it is shown how to map the data associated with a linear programming problem into H(0) and N in such a way as to have H=(H(H,N)) evolve to a solution of the linear programming problem. This result can be applied to find systems that solve a variety of generic combinatorial optimization problems, and it also provides an algorithm for diagonalizing symmetric matrices. >
---
paper_title: Computability with low-dimensional dynamical systems

paper_content:

It has been known for a short time that a class of recurrent neural networks has universal computational abilities. These networks can be viewed as iterated piecewise-linear maps in a high-dimensional space. In this paper, we show that similar systems in dimension two are also capable of universal computations. On the contrary, it is necessary to resort to more complex systems (e.g., iterated piecewise-monotone maps) in order to retain this capability in dimension one.
---
paper_title: Logical reversibility of computation

paper_content:

The usual general-purpose computing automaton (e.g.. a Turing machine) is logically irreversible- its transition function lacks a single-valued inverse. Here it is shown that such machines may he made logically reversible at every step, while retainillg their simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, there by avoiding the irreversible operation of erasure. The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), there by restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.
---
paper_title: Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems

paper_content:

We explore the simulation and computational capabilities of hybrid and continuous dynamical systems. The continuous dynamical systems considered are ordinary differential equations (ODEs). For hybrid systems we concentrate on models that combine ODEs and discrete dynamics (e.g., finite automata). We review and compare four such models from the literature. Notions of simulation of a discrete dynamical system by a continuous one are developed. We show that hybrid systems whose equations can describe a precise binary timing pulse (exact clock) can simulate arbitrary reversible discrete dynamical systems defined on closed subsets of R n . The simulations require continuous ODEs in IR2n with the exact clock as input. All four hybrid systems models studied here can implement exact clocks. We also prove that any discrete dynamical system in rn can be simulated by continuous ODEs in Rt2n+1. We use this to show that smooth ODEs in RI3 can simulate arbitrary Turing machines, and hence possess the power of universal computation. We use the famous asynchronous arbiter problem to distinguish between hybrid and continuous dynamical systems. We prove that one cannot build an arbiter with devices described by a system of Lipschitz ODEs. On the other hand, all four hybrid systems models considered can implement arbiters even if their ODEs are Lipschitz.
---
paper_title: Analog computation with continuous ODEs

paper_content:

Demonstrates simple, low-dimensional systems of ODEs that can simulate arbitrary finite automata, push-down automata, and Turing machines. We conclude that there are systems of ODEs in R/sup 3/ with continuous vector fields possessing the power of universal computation. Further, such computations can be made robust to small errors in coding of the input or measurement of the output. As such, they represent physically realizable computation. We make precise what we mean by "simulation" of digital machines by continuous dynamical systems. We also discuss elements that a more comprehensive ODE-based model of analog computation should contain. The "axioms" of such a model are based on considerations from physics. >
---

Title: A Survey of Continuous-Time Computation Theory
Section 1: Introduction
Description 1: Introduce the renewed interest in analog computation, the advancements prompting this interest, and set the stage for the theoretical discussions to follow.

Section 2: Unconstrained Models
Description 2: Discuss mathematically-based continuous-time computation models that are implementation-wise unconstrained.

Section 3: Constrained Models
Description 3: Detail the models of analog computation that correspond to idealized versions of existing devices, such as mechanical and electronic differential analyzers and neural networks.

Section 4: Computational Complexity
Description 4: Examine the limited existing work on computational complexity in continuous-time systems and suggest possible directions for defining and understanding complexity in these systems.

Section 5: Conclusion and Open Problems
Description 5: Summarize the current state of research in continuous-time computation theory, highlight open problems, and suggest directions for future work.