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

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

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)

Cites Work

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

Cited In (8)

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

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)