Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The topological entr ...
Article

The topological entropy of iterated piecewise affine maps is uncomputable

Pascal Koiran ORCID (1)
(1) Laboratoire de l'Informatique du Parallélisme
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2001
Last modified on
March 31, 2025
Volume 4
vol. 4:2
DOI
10.46298/dmtcs.292
License
https://about.hal.science/hal-authorisation-v1
Indicators
740
Views
670
Downloads

The topological entropy of iterated piecewise affine maps is uncomputable

Pascal Koiran ORCID (1)
(1) Laboratoire de l'Informatique du Parallélisme
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • topological entropy
  • piecewise affine functions
  • saturated linear functions
  • cellular automata
Cited by

Source: OpenCitations

  • Reachability in Injective Piecewise Affine Maps

    2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

    Authors : Faraz Ghahremani, Edon Kelmendi ORCID, Joël Ouaknine ORCID

    Journal reference : Volume , 2023, pp.

    DOI : 10.1109/lics56636.2023.10175723

  • Modular Computation of Restoration Entropy for Networks of Systems: A Dissipativity Approach

    IEEE Control Systems Letters

    Authors : Mahendra Singh Tomar ORCID, Majid Zamani ORCID

    Journal reference : Volume 6, 2022, pp. 3289-3294

    DOI : 10.1109/lcsys.2022.3184824

  • Shifts with decidable language and non-computable entropy

    Discrete Mathematics & Theoretical Computer Science

    Authors : Peter Hertling ORCID, Christoph Spandl

    Journal reference : Volume Vol. 10 no. 3, 2008, pp.

    DOI : 10.46298/dmtcs.425

  • Reachability Problems for PAMs

    Lecture notes in computer science

    Authors : Oleksiy Kurganskyy ORCID, Igor Potapov ORCID

    Journal reference : Volume , 2016, pp. 356-368

    DOI : 10.1007/978-3-662-49192-8_29

  • On Immortal Configurations in Turing Machines

    Authors : Emmanuel Jeandel ORCID

    Journal reference : Volume , 2012, pp. 334-343

    DOI : 10.1007/978-3-642-30870-3_34

  • Effect of quantified irreducibility on the computability of subshift entropy

    Discrete and Continuous Dynamical Systems

    Authors : Silvère Gangloff, Benjamin Hellouin de Menibus ORCID

    Journal reference : Volume 39, 2019, pp. 1975-2000

    DOI : 10.3934/dcds.2019083
Preview
Loading PDF preview...