Computability of countable subshifts in one dimension

DOI10.1007/s00224-011-9358-zzbMath1285.03055OpenAlexW2068322314MaRDI QIDQ693067

Sebastian Wyman, Ali Dashti, Douglas Cenzer, Ferit Toska

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

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

Related Items

Cototal enumeration degrees and their applications to effective mathematics, Turing degree spectra of minimal subshifts, Decidability and universality of quasiminimal subshifts, Turing degrees of multidimensional SFTs

Cites Work

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