Discrete Mathematics & Theoretical Computer Science (Dec 2001)

The topological entropy of iterated piecewise affine maps is uncomputable

  • Pascal Koiran

Journal volume & issue
Vol. 4, no. 2

Abstract

Read online

We show that it is impossible to compute (or even to approximate) the topological entropy of a continuous piecewise affine function in dimension four. The same result holds for saturated linear functions in unbounded dimension. We ask whether the topological entropy of a piecewise affine function is always a computable real number, and conversely whether every non-negative computable real number can be obtained as the topological entropy of a piecewise affine function. It seems that these two questions are also open for cellular automata.