We define a new transfinite time model of computation, infinite time cellular automata. The model is shown to be as powerful than infinite time Turing machines, both on finite and infinite inputs; thus inheriting many of its properties. We then show
how to simulate the canonical real computation model, BSS machines, with infinite time cellular automata in exactly omega steps.
A combinatorial substitution is a map over tilings which allows to define sets of tilings with a strong hierarchical structure. In this paper, we show that such sets of tilings are sofic, that is, can be enforced by finitely many local constraints. T
his extends some similar previous results (Mozes90, Goodman-Strauss98) in a much shorter presentation.
This paper is the second part of a series of two papers dealing with bulking: a way to define quasi-order on cellular automata by comparing space-time diagrams up to rescaling. In the present paper, we introduce three notions of simulation between ce
llular automata and study the quasi-order structures induced by these simulation relations on the whole set of cellular automata. Various aspects of these quasi-orders are considered (induced equivalence relations, maximum elements, induced orders, etc) providing several formal tools allowing to classify cellular automata.
Signals are a classical tool used in cellular automata constructions that proved to be useful for language recognition or firing-squad synchronisation. Particles and collisions formalize this idea one step further, describing regular nets of collidin
g signals. In the present paper, we investigate the use of particles and collisions for constructions involving an infinite number of interacting particles. We obtain a high-level construction for a new smallest intrinsically universal cellular automaton with 4 states.
This talk advocates intrinsic universality as a notion to identify simple cellular automata with complex computational behavior. After an historical introduction and proper definitions of intrinsic universality, which is discussed with respect to Tur
ing and circuit universality, we discuss construction methods for small intrinsically universal cellular automata before discussing techniques for proving non universality.
