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. On the computability ...
Article

On the computability of the topological entropy of subshifts

Jakob Grue Simonsen (1)
(1) Department of Computer Science [Copenhagen]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2006
Last modified on
March 31, 2025
Volume 8
vol. 8
DOI
10.46298/dmtcs.365
License
https://about.hal.science/hal-authorisation-v1
Indicators
1011
Views
1102
Downloads

On the computability of the topological entropy of subshifts

Jakob Grue Simonsen (1)
(1) Department of Computer Science [Copenhagen]
Abstract
We prove that the topological entropy of subshifts having decidable language is uncomputable in the following sense: For no error bound less than 1/4 does there exists a program that, given a decision procedure for the language of a subshift as input, will approximate the entropy of the subshift within the error bound. In addition, we prove that not only is the topological entropy of sofic shifts computable to arbitary precision (a well-known fact), but all standard comparisons of the topological entropy with rational numbers are decidable.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • Computing the Topological Entropy of Shifts

    Electronic Notes in Theoretical Computer Science

    Authors : Christoph Spandl

    Journal reference : Volume 167, 2007, pp. 131-155

    DOI : 10.1016/j.entcs.2006.08.011

  • Computing the topological entropy of shifts

    Mathematical logic quarterly

    Authors : Christoph Spandl

    Journal reference : Volume 53, 2007, pp. 493-510

    DOI : 10.1002/malq.200710014

  • Computability of topological pressure on compact shift spaces beyond finite type*

    Nonlinearity

    Authors : Michael Burr ORCID, Suddhasattwa Das ORCID, Christian Wolf ORCID, Yun Yang ORCID

    Journal reference : Volume 35, 2022, pp. 4250-4282

    DOI : 10.1088/1361-6544/ac7702

  • Beta-Shifts, Their Languages, and Computability

    Theory of Computing Systems

    Authors : Jakob Grue Simonsen ORCID

    Journal reference : Volume 48, 2009, pp. 297-318

    DOI : 10.1007/s00224-009-9245-z

  • On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts

    Theoretical Computer Science

    Authors : Jakob Grue Simonsen ORCID

    Journal reference : Volume 410, 2009, pp. 4878-4891

    DOI : 10.1016/j.tcs.2009.06.037

  • A characterization of the entropies of multidimensional shifts of finite type

    Annals of Mathematics

    Authors : Michael Hochman, Tom Meyerovitch

    Journal reference : Volume 171, 2010, pp. 2011-2038

    DOI : 10.4007/annals.2010.171.2011

  • Observation of nonlinear systems via finite capacity channels: Constructive data rate limits

    Automatica

    Authors : Alexey Matveev ORCID, Alexander Pogromsky ORCID

    Journal reference : Volume 70, 2016, pp. 217-229

    DOI : 10.1016/j.automatica.2016.04.005

  • Densities and Entropies in Cellular Automata

    Lecture notes in computer science

    Authors : Pierre Guillon ORCID, Charalampos Zinoviadis

    Journal reference : Volume , 2012, pp. 253-263

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

  • Computability of entropy and information in classical Hamiltonian systems

    arXiv (Cornell University)

    Authors : Sungyun Kim ORCID

    Journal reference : Volume 373, 2009, pp. 1409-1414

    DOI : 10.1016/j.physleta.2009.02.050

  • 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...