Generalized shifts: Unpredictability and undecidability in dynamical systems. (English) Zbl 0725.58013

This paper discusses a class of dynamical systems called generalized shifts. These are maps from the set of bi-infinite sequences of some alphabet to itself. On each sequence the map will change a finite number of cells and shift the resulting sequence by a certain amount. The way that the sequence is changed and the amount by which it is shifted depends only on a finite set of cells of the initial sequence. Some general results, mainly concerning periodicity and examples are presented.
The author also shows that a generalized shift can be simulated by a Turing machine and hence lists a number of questions which are undecidable. It is also shown that generalized shifts can be embedded in smooth maps in \({\mathbb{R}}^ 2\), or smooth flows in \({\mathbb{R}}^ 3\).
Reviewer: R.Cowen (Gaborone)


37E99 Low-dimensional dynamical systems
37C70 Attractors and repellers of smooth dynamical systems and their topological structure
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI