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: 93,745

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

Computable symbolic dynamics.Douglas Cenzer, S. Dashti & Jonathan F. King - 2008 - Mathematical Logic Quarterly 54 (5):460-469.
Lp -Computability.Ning Zhong & Bing-Yu Zhang - 1999 - Mathematical Logic Quarterly 45 (4):449-456.
Countable thin Π01 classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 59 (2):79-139.
Minimal extensions of Π01 classes.Douglas Cenzer & Farzan Riazati - 2005 - Mathematical Logic Quarterly 51 (2):206-216.
Initial Segments of the Lattice of $\Pi^0_1$ Classes.Douglas Cenzer & Andre Nies - 2001 - Journal of Symbolic Logic 66 (4):1749-1765.
Initial segments of the lattice of Π10 classes.Douglas Cenzer & Andre Nies - 2001 - Journal of Symbolic Logic 66 (4):1749-1765.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
On the C.E. Degrees Realizable in Classes.Barbara F. Csima, Rod Downey & N. G. Keng Meng - forthcoming - Journal of Symbolic Logic:1-26.
Computable Riesz representation for the dual of C [0; 1].Hong Lu & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4):415-430.
Approaches to Effective Semi‐Continuity of Real Functions.Xizhong Zheng, Vasco Brattka & Klaus Weihrauch - 1999 - Mathematical Logic Quarterly 45 (4):481-496.

Analytics

Added to PP
2013-12-01

Downloads
39 (#115,291)

6 months
6 (#1,472,471)

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