Computable symbolic dynamics

, &
Mathematical Logic Quarterly 54 (5):460-469 (2008)
  Copy   BIBTEX

Abstract

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

Categories

Keywords

Reprint years

DOI

10.1002/malq.200710066

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.
Effectively closed sets and enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Review: M. O. Rabin, Computable Algebraic Systems; Michael O. Rabin, Computable Algebra, General Theory and Theory of Computable Fields. [REVIEW]B. H. Mayoh - 1967 - Journal of Symbolic Logic 32 (3):412-413.
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.
Review: Marian Boykan Pour-El, Ian Richards, A Computable Ordinary Differential Equation with Possesses no Computable Solution; Marian Boykan Pour-El, Ian Richards, The Wave Equation with Computable Initial Data Such that its Unique Solution is not Computable. [REVIEW]G. Kreisel - 1982 - Journal of Symbolic Logic 47 (4):900-902.
Probabilistic algorithmic randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
When series of computable functions with varying domains are computable.Iraj Kalantari & Larry Welch - 2013 - Mathematical Logic Quarterly 59 (6):471-493.
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.
Applications of Kolmogorov Complexity to Computable Model Theory.B. Khoussainov, P. Semukhin & F. Stephan - 2007 - Journal of Symbolic Logic 72 (3):1041 - 1054.

Analytics

Added to PP
2013-12-01

Downloads
45 (#345,268)

6 months
6 (#504,917)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

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