Computable symbolic dynamics

Mathematical Logic Quarterly 54 (5):460-469 (2008)

We investigate computable subshifts and the connection with effective symbolic dynamics. It is shown that a decidable Π01 class P is a subshift if and only if there exists a computable function F mapping 2ℕ to 2ℕ such that P is the set of itineraries of elements of 2ℕ. Π01 subshifts are constructed in 2ℕ and in 2ℤ which have no computable elements. We also consider the symbolic dynamics of maps on the unit interval
Keywords symbolic dynamics  Π01 classes  Computability
Categories (categorize this paper)
DOI 10.1002/malq.200710066
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,566
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On the Computability of Fractal Dimensions and Hausdorff Measure.Ker-I. Ko - 1998 - Annals of Pure and Applied Logic 93 (1-3):195-216.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Computable Metrization.Tanja Grubba, Matthias Schröder & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4‐5):381-395.
The Computable Dimension of Trees of Infinite Height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Finite Computable Dimension Does Not Relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
Probabilistic Algorithmic Randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Prime Models of Finite Computable Dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.
Computable Embeddings and Strongly Minimal Theories.J. Chisholm, J. F. Knight & S. Miller - 2007 - Journal of Symbolic Logic 72 (3):1031 - 1040.
Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.


Added to PP index

Total views
26 ( #293,562 of 2,325,877 )

Recent downloads (6 months)
3 ( #527,170 of 2,325,877 )

How can I increase my downloads?


My notes

Sign in to use this feature