A-2 Nonlinear computing with switching map systems(基礎物理学研究所研究会「複雑系6」報告,研究会報告)

Abstract

Dynamical systems based computational theory is studied. We demonstrate the ability of simple switching map systems to solve non-trivial computational problems. There exists a switching map system with two types of baker's map to emulate any Turing machines. Here the baker's maps are corresponding to elementary process for computing ('effective procedure') such as left/right shift and read/write symbols in the view of Tuirng machines. Taking other nonlinear mappings as elementary process, the dynamical system can solve various problems in different ways than classical Turing machines. We call this kind of computing 'non-linear computing' and analyze its computational power on a point of view of dynamical systems.