Computation in One-Dimensional Piecewise Maps and Planar Pseudo-Billiard Systems

摘要

The computation in low-dimensional system is related to many long standing open problems. In this paper we show the universality of a one-dimensional iterative map defined by elementary functions. The computation in iterative maps have a number of connections with other unconventional models of computations. In particular, one-dimensional iterative maps can be simulated by a planar pseudo-billiard system. As a consequence of our main result we show that a planar pseudo-billiard system is not only can demonstrate a chaotic behaviour, but also has ability of universal computation.