Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines

DOI10.1016/j.tcs.2004.02.018zbMath1044.03024OpenAlexW2164846953MaRDI QIDQ596050

Jean-Charles Delvenne, Blondel, Vincent D.

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.018

zbMATH Keywords

Dynamical systemsTuring machineTilingQuasi-periodicityUndecidability

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Topological entropy (37B40) Combinatorial aspects of tessellation and tiling problems (05B45) Turing machines and related notions (03D10)

Related Items (6)

Observation of nonlinear systems via finite capacity channels: constructive data rate limits ⋮ A physically universal Turing machine ⋮ Effect of quantified irreducibility on the computability of subshift entropy ⋮ Undecidability of the speed positiveness problem in reversible and complete Turing machines ⋮ Quasiperiodic bobbin lace patterns ⋮ Computability and Beltrami fields in Euclidean space

Cites Work

• An aperiodic set of 13 Wang tiles
• On topological dynamics of Turing machines
• Rice's theorem for the limit sets of cellular automata
• On the presence of periodic configurations in Turing machines and in counter machines.
• Tilings and quasiperiodicity.
• The topological entropy of cellular automata is uncomputable
• The undecidability of the Turing machine immortality problem
• The undecidability of the domino problem
• Strong cocycle triviality for \(Z^{2}\) subshifts
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines