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

Add categories

Keywords

Reprint years

DOI

10.1002/malq.200710066

Links

PhilArchive



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

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. Ali Dashti & Jonathan L. F. King - 2008 - Mathematical Logic Quarterly 54 (5):460-469.
On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.
A Banach–Mazur computable but not Markov computable function on the computable real numbers.Peter Hertling - 2005 - Annals of Pure and Applied Logic 132 (2-3):227-246.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
Effectively closed sets and enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
H‐monotonically computable real numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
Finite computable dimension does not relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
Turing computable embeddings.F. Knight Julia, Miller Sara & M. Vanden Boom - 2007 - Journal of Symbolic Logic 72 (3):901-918.
Computable Embeddings and Strongly Minimal Theories.J. Chisholm, J. F. Knight & S. Miller - 2007 - Journal of Symbolic Logic 72 (3):1031 - 1040.
The computable dimension of trees of infinite height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
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.
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.
Rabin M. O.. Computable algebraic systems. Summaries of talks presented at the Summer Institute for Symbolic Logic, Cornell University, 1957, 2nd edn., Communications Research Division, Institute for Defense Analyses, Princeton, N.J., 1960, pp. 134–138.Rabin Michael O.. Computable algebra, general theory and theory of computable fields. Transactions of the American Mathematical Society, vol. 95 , pp. 341–360. [REVIEW]B. H. Mayoh - 1967 - Journal of Symbolic Logic 32 (3):412-413.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.

Analytics

Added to PP
2017-02-17

Downloads
0

6 months
0

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references