Computability in Symbolic Dynamics

DOI10.1007/978-3-319-40189-8_13MaRDI QIDQ3188248zbMATH OpenOpenAlexFDO

Authors Emmanuel Jeandel

Publication date 17 August 2016

Published in Pursuit of the Universal (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01445688/file/syndyn.pdf

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Symbolic dynamics (37B10)

Cites work

• An Introduction to Symbolic Dynamics and Coding
• An order on sets of tilings corresponding to an order on languages
• Characterizations of periods of multi-dimensional shifts
• Computable symbolic dynamics
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Degrees of models
• Effective closed subshifts in 1D can be implemented in 2D
• Effective symbolic dynamics
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• Generalized one-sided shifts and maps of the interval
• scientific article; zbMATH DE number 193180 (Why is no real title available?)
• scientific article; zbMATH DE number 1303200 (Why is no real title available?)
• scientific article; zbMATH DE number 2158945 (Why is no real title available?)
• Mass problems associated with effectively closed sets
• Medvedev degrees of two-dimensional subshifts of finite type
• Nonrecursive tilings of the plane. II
• On the dynamics and recursive properties of multidimensional symbolic systems
• On topological dynamics of Turing machines
• Reducibility and Completeness for Sets of Integers
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• Subgroups of finitely presented groups
• The undecidability of the domino problem
• Turing degree spectra of minimal subshifts
• Turing degrees of multidimensional SFTs
• Two notes on subshifts
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(10)

• Symbolic dynamics and characterization of complexity
• The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics
• Computability and human symbolic output
• Symbolic Dynamics, Flower Automata and Infinite Traces
• scientific article; zbMATH DE number 5117086 (Why is no real title available?)
• Symbolic dynamics and finite automata
• Dynamical aspects of \(\sigma\)-machines
• Substitution-dynamics and invariant measures for infinite alphabet-path space
• Dynamics and abstract computability: computing invariant measures
• On a Rice theorem for dynamical properties of SFTs on groups

This page was built for publication: Computability in Symbolic Dynamics

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