|InterJournal Complex Systems, 67
|Manuscript Number: |
Submission Date: 963011
|Universal computation by finite two-dimensional coupled map lattices|
Category: Brief Article
Coupled map lattices (CMLs) are locally-coupled discrete-time, discrete-space, continuous-state dynamical systems. This cellular-automata-like discretization of PDEs was introduced in the early 1980s in studies of spatiotemporal chaos and other phenomena arising in reaction-diffusion processes. Since then CMLs have been applied as models for problems in, e.g. solid-state physics, population biology, neurophysiology, and information processing.
The question of the general computational power of the CML model is rather interesting, both from the point of view of obtaining an understanding of the dynamical possibilities of the model, and with a view towards possible computational applications. Indeed in the concluding phrases of his survey article on CMLs, Kaneko states: "A CML with chaotic behavior must have higher computational ability than a CA, since the former can create information. It will be important to clarify what a CML can do that the conventional computer cannot."
Kanekos aim is actually set too high, as it is rather easy to see that given a finitely described initial state, and with effectively computable response functions, a finite CML can always be simulated on a Turing machine, ie a digital computer. %(One may of course one still ask about the efficiency of CMLs %as parallel computers, but that is another topic.) In this paper we establish, however, that there are no other limitations to the computational power of the model: a universal Turing machine can be simulated on a two-dimensional CML with 74580 scalar lattice sites, and thus CMLs are in principle capable of doing anything that a digital computer can do.
The local response functions of our CML model are simple piecewise-linear, unimodal maps similar to the tent map. The sites in the lattice are interconnected in a symmetric von Neumann pattern (ie, each site is connected to its two vertical and two horizontal neighbors), with homogeneous and symmetric diffusion coefficients. However, in terms of the local response functions our lattice is strongly anisotropic: each site has its own response function. We leave it as an open question whether also completely isotropic lattices can be computationally universal.
|Submit referee report/comment|