Directional dynamics along arbitrary curves in cellular automata

This paper studies directional dynamics on one-dimensional cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behavior of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2011-07, Vol.412 (30), p.3800-3821
Main Authors: Delacourt, M., Poupet, V., Sablik, M., Theyssier, G.
Format: Article
Language:English
Subjects:
Automation
Cellular
Cellular automata
Directional dynamics
Dynamic tests
Dynamical Systems
Dynamics
Expansion
Formalism
Mathematics
Temporal logic
Topological dynamics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper studies directional dynamics on one-dimensional cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behavior of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial action): qualitative behaviors inherited from topological dynamics (equicontinuity, sensitivity, expansivity) are thus considered along arbitrary curves in space–time. The main contributions of the paper concern equicontinuous dynamics which can be connected to the notion of consequences of a word. We show that there is a cellular automaton with an equicontinuous dynamics along a parabola, but which is sensitive along any linear direction. We also show that real numbers that occur as the slope of a limit linear direction with equicontinuous dynamics in some cellular automaton are exactly the computably enumerable numbers.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2011.02.019