Computation in One-Dimensional Piecewise Maps

摘要

In this paper we show that the one-dimensional Piecewise Affine Maps (PAMs) are equivalent to planar Pseudo-Billiard Systems (PBSs) or so called "strange billiards". The reachability problem for PAMs is still open, however the more general model of rational one-dimensional maps is shown to be universal with undecidable reachability problem.