Nonlinear Computation with Switching Map Systems

Yuzuru Sato (Institute of Physics, Graduate School of Arts and Sciences, University of Tokyo, Japan)

Takashi Ikegami (Institute of Physics, Graduate School of Arts and Sciences, University of Tokyo, Japan)

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: Henon map, Smale's horseshoe, baker's map, switching map systems

Categories: F.1