Pascal Koiran - The topological entropy of iterated piecewise affine maps is uncomputable

dmtcs:292 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, Vol. 4 no. 2 - https://doi.org/10.46298/dmtcs.292
The topological entropy of iterated piecewise affine maps is uncomputable

Authors: Pascal Koiran

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.


Volume: Vol. 4 no. 2
Published on: January 1, 2001
Imported on: March 26, 2015
Keywords: topological entropy,piecewise affine functions,saturated linear functions,cellular automata,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 126 times.
This article's PDF has been downloaded 122 times.