Computability of countable subshifts in one dimension

DOI10.1007/S00224-011-9358-ZzbMATH Open1285.03055OpenAlexW2068322314MaRDI QIDQ693067FDOQ693067

Authors Douglas Cenzer, Ali Dashti, Ferit Toska, Sebastian Wyman 

Publication date 7 December 2012

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-011-9358-z

zbMATH Keywords

symbolic dynamicscomputability\(\Pi^0_1\) classes

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Symbolic dynamics (37B10) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Computability of countable subshifts
• Constructions with countable subshifts of finite type
• Computable symbolic dynamics
• On derivatives and subpattern orders of countable subshifts
• On the computability of the topological entropy of subshifts

Cites work

• scientific article; zbMATH DE number 5117086 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 841094 (Why is no real title available?)
• scientific article; zbMATH DE number 1390012 (Why is no real title available?)
• Computability of countable subshifts
• Computable symbolic dynamics
• Countable thin \(\Pi^0_1\) classes
• Degrees of difficulty of generalized r.e. separating classes
• Logical methods. In honor of Anil Nerode's 60th birthday
• Mass Problems and Randomness
• Medvedev degrees of two-dimensional subshifts of finite type
• Members of countable \(\Pi ^ 0_ 1\) classes
• Non-computable Julia sets
• On the computability of fractal dimensions and Hausdorff measure
• On the computational power of dynamical systems and hybrid systems
• On the dynamics and recursive properties of multidimensional symbolic systems
• On the ranked points of a Π₁⁰ set
• Subsystems of second order arithmetic
• The computational complexity of some Julia sets
• Turing degrees of multidimensional SFTs
• Two notes on subshifts

Cited in

(9)

• Computable symbolic dynamics
• On derivatives and subpattern orders of countable subshifts
• Turing degrees of multidimensional SFTs
• Decidability and universality of quasiminimal subshifts
• Cototal enumeration degrees and their applications to effective mathematics
• Constructions with countable subshifts of finite type
• Computability of countable subshifts
• Two notes on subshifts
• Turing degree spectra of minimal subshifts

This page was built for publication: Computability of countable subshifts in one dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693067)