JUCS - Journal of Universal Computer Science 6(9): 881-905, doi: 10.3217/jucs-006-09-0881
Nonlinear Computation with Switching Map Systems
expand article infoYuzuru Sato‡, Takashi Ikegami‡
‡ Institute of Physics, Graduate School of Arts and Sciences, University of Tokyo, Japan

Corresponding author: Yuzuru Sato ( ysato@sacral.c.u-tokyo.ac.jp )

© Yuzuru Sato, Takashi Ikegami.
This article is freely available under the J.UCS Open Content License.
Citation: Sato Y, Ikegami T (2000) Nonlinear Computation with Switching Map Systems. JUCS - Journal of Universal Computer Science 6(9): 881-905. https://doi.org/10.3217/jucs-006-09-0881
Open Access
Abstract
A dynamical systems based model of computation is studied. We demonstrate the computational capability of a class of dynamical systems called switching map systems. There exists a switching map system with two types of baker s map to emulate any Turing machines. The baker s maps are corresponding to the elementary operations of Turing machines such as left/right head-moving and read/write symbols. A connection between the generalized shifts by C. Moore [Moore 91] and the input-output mappings by L. Blum et al. [Blum, Cucker, Shub and Smale 98] is shown with our model. We present four concrete examples of switching map systems corresponding to the Chomsky hierarchy. Taking non-hyperbolic mappings as elementary operations, it is expected that the switching map systems shows a new model of computation with nonlinearity as an oracle.
Keywords
switching map systems, Smale's horseshoe, baker's map, Henon map