On the dynamics and recursive properties of multidimensional symbolic systems

DOI10.1007/s00222-008-0161-7zbMath1168.37002OpenAlexW2052399269MaRDI QIDQ1016235

Michael Hochman

Publication date: 5 May 2009

Published in: Inventiones Mathematicae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00222-008-0161-7

zbMATH Keywords

topological dynamicsTuring machinecellular automatonshift of finite type

Mathematics Subject Classification ID

Related Items (60)

Rohlin properties for $\mathbb{Z}^{d}$ actions on the Cantor set ⋮ Entropy dimension of shifts of finite type on free groups ⋮ Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts ⋮ Factor maps and embeddings for random \(\mathbb{Z}^d\) shifts of finite type ⋮ Conservatively Approximable Functions ⋮ Random \(\mathbb{Z}^d\)-shifts of finite type ⋮ Matrix Characterization of Multidimensional Subshifts of Finite Type ⋮ Effective S-adic Symbolic Dynamical Systems ⋮ Computability in Symbolic Dynamics ⋮ Turing degree spectra of minimal subshifts ⋮ Decidability and universality of quasiminimal subshifts ⋮ Simulation of effective subshifts by two-dimensional subshifts of finite type ⋮ Computability of topological entropy: from general systems to transformations on Cantor sets and the interval ⋮ One-dimensional projective subdynamics of uniformly mixing shifts of finite type ⋮ Seas of squares with sizes from a \(\Pi_{1}^{0}\) set ⋮ Countable sofic shifts with a periodic direction ⋮ Mixing properties of tree-shifts ⋮ Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata ⋮ On the Besicovitch-stability of noisy random tilings ⋮ Arithmetical hierarchy of the Besicovitch-stability of noisy tilings ⋮ Growth-type invariants for \(\mathbb Z^{d}\) subshifts of finite type and arithmetical classes of real numbers ⋮ Probability and algorithmics: a focus on some recent developments ⋮ Fixed-point tile sets and their applications ⋮ About the Domino Problem for Subshifts on Groups ⋮ Polyominoes simulating arbitrary-neighborhood zippers and tilings ⋮ Subshifts with sparse traces ⋮ The structure of limit sets for \(\mathbb{Z}^d\) actions ⋮ The Undecidability of the Domino Problem ⋮ Realization of aperiodic subshifts and uniform densities in groups ⋮ Effect of quantified irreducibility on the computability of subshift entropy ⋮ Hardness of conjugacy, embedding and factorization of multidimensional subshifts ⋮ A notion of effectiveness for subshifts on finitely generated groups ⋮ Characterization of sets of limit measures of a cellular automaton iterated on a random configuration ⋮ Zero-temperature phase diagram for double-well type potentials in the summable variation class ⋮ A class of nonsofic multidimensional shift spaces ⋮ On the finite-dimensional marginals of shift-invariant measures ⋮ On the automorphism groups of multidimensional shifts of finite type ⋮ Computability of countable subshifts in one dimension ⋮ Embeddings of dynamical systems into cellular automata – ERRATUM ⋮ Effective Closed Subshifts in 1D Can Be Implemented in 2D ⋮ Multidimensional sofic shifts without separation and their factors ⋮ On the zero-temperature limit of Gibbs states ⋮ Geometric rigidity of \(\times m\) invariant measures ⋮ Unnamed Item ⋮ The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics ⋮ Extender sets and multidimensional subshifts ⋮ The expressiveness of quasiperiodic and minimal shifts of finite type ⋮ Slopes of multidimensional subshifts ⋮ Decidability in Group Shifts and Group Cellular Automata ⋮ Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type ⋮ Ergodic optimization in dynamical systems ⋮ Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy ⋮ A strongly aperiodic shift of finite type on the discrete Heisenberg group using Robinson tilings ⋮ A generalization of the simulation theorem for semidirect products ⋮ Weak colored local rules for planar tilings ⋮ On the Expressive Power of Quasiperiodic SFT. ⋮ Classification of sofic projective subdynamics of multidimensional shifts of finite type ⋮ Lectures on dynamics, fractal geometry, and metric number theory ⋮ Support stability of maximizing measures for shifts of finite type ⋮ Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the entropy of \(\mathbb{Z}^d\) subshifts of finite type
• Computation theoretic aspects of cellular automata
• How sampling reveals a process
• A characterization of the entropies of multidimensional shifts of finite type
• A simple measure-preserving transformation with trivial centralizer
• Rice's theorem for the limit sets of cellular automata
• Dynamical properties of expansive one-sided cellular automata
• Expansive invertible onesided cellular automata
• Theory of cellular automata: a survey
• Tilings, substitution systems and dynamical systems generated by them
• The Arithmetical Hierarchy of Real Numbers
• The entropies of topological Markov shifts and a related class of algebraic integers
• shifts of finite type without equal entropy full shift factors
• The topological entropy of cellular automata is uncomputable
• Nonrecursive tilings of the plane. II
• Non-uniqueness of measures of maximal entropy for subshifts of finite type
• Entropy gaps and locally maximal entropy in $\mathbb{Z}^d$ subshifts
• Textile systems and one-sided resolving automorphisms and endomorphisms of the shift
• Factoring higher-dimensional shifts of finite type onto the full shift
• Endomorphisms and automorphisms of the shift dynamical system
• The undecidability of the domino problem
• Machines, Computations, and Universality

This page was built for publication: On the dynamics and recursive properties of multidimensional symbolic systems