The topological entropy of iterated piecewise affine maps is uncomputable

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.351-356
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958966
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:53:51
Dernière modification le : mardi 24 avril 2018 - 13:54:26
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:05:44

Fichier

dm040219.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958966, version 1

Collections

Citation

Pascal Koiran. The topological entropy of iterated piecewise affine maps is uncomputable. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.351-356. 〈hal-00958966〉

Partager

Métriques

Consultations de la notice

177

Téléchargements de fichiers

441