Geodesic
On the computability of the topological entropy of subshifts
Discrete mathematics & theoretical computer science, Tome 8 (2006).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2006_8_a6,
     author = {Simonsen, Jakob Grue},
     title = {On the computability of the topological entropy of subshifts},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {8},
     year = {2006},
     doi = {10.46298/dmtcs.365},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.365/}
}
TY  - JOUR
AU  - Simonsen, Jakob Grue
TI  - On the computability of the topological entropy of subshifts
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.365/
DO  - 10.46298/dmtcs.365
LA  - en
ID  - DMTCS_2006_8_a6
ER  - 
%0 Journal Article
%A Simonsen, Jakob Grue
%T On the computability of the topological entropy of subshifts
%J Discrete mathematics & theoretical computer science
%D 2006
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.365/
%R 10.46298/dmtcs.365
%G en
%F DMTCS_2006_8_a6
Simonsen, Jakob Grue. On the computability of the topological entropy of subshifts. Discrete mathematics & theoretical computer science, Tome 8 (2006). doi : 10.46298/dmtcs.365. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.365/

Cité par Sources :