Distortion in One-Head Machines and Cellular Automata - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

Distortion in One-Head Machines and Cellular Automata

(1) , (2)
1
2
Pierre Guillon
Ville Salo
  • Function : Author
  • PersonId : 998313

Abstract

We give two families of examples of automorphisms of subshifts that are range-distorted, that is, the radius of their iterations grows sublinearly. One of these families comes from one-head machines, and allows us to build such automorphisms for the full shift, and to obtain undecidability results. We also give some conditions on the functions that can occur as such growths.
Fichier principal
Vignette du fichier
447449_1_En_10_Chapter.pdf (307.73 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01656350 , version 1 (05-12-2017)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Pierre Guillon, Ville Salo. Distortion in One-Head Machines and Cellular Automata. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.120-138, ⟨10.1007/978-3-319-58631-1_10⟩. ⟨hal-01656350⟩
143 View
91 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More