Computing Functions with Dynamical Systems

Question

I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes all initial conditions - The initial tape content, starting state, initial head position) "evolves" to a specific configuration after a finite number of steps and if the function is computable, it halts with the output of the function on the tape. I am trying to draw an analogy of Turing Machines with other "time-evolving" systems and the most intuitive of all is a Dynamical System as a set of differential equations. As an attempt, I formulated a dynamical system which could compute asymptotically the square of a number.

Suppose I want to find the functions $f(x,y,t)$ and $g(x,y,t)$ such that the following dynamical system:

$\frac{dx}{dt}=f(x,y,t)$

$\frac{dy}{dt}=g(x,y,t)$

is such that:

• In the phase plane (with $x$ on X axis and $y$ on Y axis), every point on the X axis is a fixed point.
• Any initial point on the line y=$\alpha$ (with $\alpha\neq0 $) with coordinates $(x(0),\alpha)$ goes towards the fixed point $(x(0)^2,0)$ for $t\rightarrow\infty$

The functions $f$ and $g$ may contain the $\alpha$ term

With such a dynamical system at hand, if we wanted to compute the square of a number $a$, all we have to do is to start off with initial conditions $x(0)=a$ and $y(0)=\alpha$ (Just like we place the initial input on the Turing Machine's tape,set the initial state to the starting state and correctly position the head; In this case we place the input $a$ as the x coordinate of the initial point of the phase trajectory) and "let the Dynamical System evolve" (Just like we let the Turing Machine evolve after placing the inputs), the phase trajectory will converge to $a^2$ for $t\rightarrow\infty$ (Assuming the function to be computable, the turing machine stops in finite time and it prints the output on tape; the given dynamical system doesn't stop in finite time but it also "prints the output" as the x coordinate of the evolved phase trajectory for $t\rightarrow\infty$). In other words if we had a "machine M" following the given dynamical system, we could say that: M computes the "square" function asymptotically. (Just like the way the turing machine computes the "square" function in finite time) The computations in this case happens over reals as opposed to that over members of a countable alphabet.

But I cant really think of such functions $f$ and $g$ for computing the "square" function and I need help finding these. Furthermore if I start taking up more complicated functions to compute, finding the corresponding $f$ and $g$ will not be a trivial task. Can someone guide me on what possible difficulties I may face and how I can overcome them?

If I can formulate computation using Dynamical Systems the way I described above, is there a possibility to prove some theorems in computability (and complexity?) using these formulations?

Thankyou!

Answer 1

Brockett [1] studied a closely related idea, and showed how to construct dynamical systems that solve any linear programming problem in (I believe) the same manner you suggest, as well as dynamical systems to sort a list of numbers and to diagonalize a matrix. You may be able to use this to directly get the dynamics you need to compute the squaring function.

(At some point I saw a cool video of the trajectory of a dynamical system for sorting, but I can't seem to find it...)

I won't venture a guess as to whether such dynamical systems formulations could be used to prove something interesting in computability/complexity, but can offer some further references that may be relevant.

In quantum computing, Nielsen, Dowling, Gu, and Doherty show that QC can be realized as (if I understand correctly) geodesic flow on a certain manifold - a particular example of the kind of dynamical system you're talking about. See [2] and references therein for a discussion of some complexity issues related to this.

Finally, although I don't think it's exactly what you're talking about, it would probably also be worth checking out Bernard Chazelle's work on "influence systems" which are a type of dynamical system that is at least as powerful as Markov chains and Turing machines, but can exhibit all kinds of dynamic behavior (including chaos, etc). See [3] and references therein.

[1] Roger W. Brockett, Dynamical Systems that Sort Lists, Diagonalize Matrices and Solve Linear Programming Problems, Proc. 27th IEEE Conf. Dec. and Control, Austin, TX, pp. 799-803, Dec. 1988.

[2] Mark R. Dowling, Michael A. Nielsen. The geometry of quantum computation, arXiv:quant-ph/0701004, 2007.

[3] B. Chazelle, Natural Algorithms and Influence Systems, Comm. ACM 55 (2012), 101-110.

Answer 2

there may be a ref that relatively directly connects general differential equations with Turing Completeness, but am not sure what one is. wikipedia states in this section Computability theory/continuous:

Computability theory for digital computation is well developed. Computability theory is less well developed for analog computation that occurs in analog computers, analog signal processing, analog electronics, neural networks and continuous-time control theory, modelled by differential equations and continuous dynamical systems (Orponen 1997; Moore 1996).

however another angle, a close nearby area is Reaction Diffusion equations which are a special class of differential equations. these were initially studied by Turing. he proposed they were capable of a kind of computation. this was later borne out and they have somewhat recently been proven to be Turing Complete. see eg

• Computing with a Distributed Reaction-Diffusion Model S. Bandini, G. Mauri, G. Pavesi, C. Simone. Machines, Computations, and Universality Lecture Notes in Computer Science Volume 3354, 2005, pp 93-103

excerpt from abstract:

The Reaction–Diffusion Machine is a computational model we previously introduced inspired by reaction diffusion phenomena. In this work, we prove that a Deterministic Turing Machine can be simulated by a Reaction-Diffusion Machine.

so to sketch this out, one route to your problem is to create the TM that one wants to compute, and then convert it to a RD model as described in the paper. the RD model is then in a special class of differential equations.

Answer 3

here are two other references that show the connection between physics/dynamical systems theory and undecidability (and therefore Turing completeness). therefore being TM complete, all computable functions are representable/reducible to these systems.

the 1st ref uses the physics laws of classical mechanics, which can be described as differential equations (eg Newtons law etc). the descriptions below are from Wikipedia. a description from Ian Stewarts book From here to infinity [the key statement wrt your question is about dynamic system trajectories which are governed by differential equations]:

Recent work of Newton da Costa and F.A. Doria casts doubt upon Penrose's thesis, and explores the limits of computability in chaotic classical dynamical systems. They show that undecidability extends to many basic questions in dynamical systems theory. These include whether the dynamics is chaotic, whether a trajectory starting from a given initial point eventually passes through some specific region of phase space, and whether the equations are integrable—that is, possess an explicit solution defined by formulas built up from classical functions such as polynomials, sines, and exponentials. Indeed virtuallly any 'interesting' question about dynamical systems is—in general—undecidable.

• N. C. A. da Costa and F. A. Dória, Undecidability and incompleteness in classical mechanics, Int. J. Theor. Physics vol. 30, pp. 1041-1073 (1991)

Proves that chaos theory is undecidable and, if axiomatized within set theory, incomplete in the sense of Gödel.

• N. C. A. da Costa and F. A. Dória, An undecidable Hopf bifurcation with an undecidable fixed point, Int. J. Theor. Physics vol. 33, pp. 1885-1903 (1994).

Settles a question raised by V. I. Arnold in the list of problems drawn up at the 1974 American Mathematical Society Symposium on the Hilbert Problems: is the stability problem for stationary points algorithmically decidable? I. Stewart, ``Deciding the undecidable, Nature vol. 352, pp. 664-665 (1991).