Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On Undecidable Dynamical Prope...

On Undecidable Dynamical Properties of Reversible One-Dimensional Cellular Automata

Ville Lukkarila, On Undecidable Dynamical Properties of Reversible One-Dimensional Cellular Automata. TUCS Dissertations 129. Turku Centre for Computer Science, 2010.

Abstract:

Cellular automata are models for massively parallel computation. A cellular automaton consists of cells which are arranged in some kind of regular lattice and a local update rule which updates the state of each cell according to the states of the cell's neighbors on each step of the computation.

This work focuses on reversible one-dimensional cellular automata in which the cells are arranged in a two-way in nite line and the computation is reversible, that is, the previous states of the cells can be derived from the current ones. In this work it is shown that several properties of reversible one-dimensional cellular automata are algorithmically undecidable, that is, there exists no algorithm that would tell whether a given cellular automaton has the property or not.

It is shown that the tiling problem of Wang tiles remains undecidable even in some very restricted special cases. It follows that it is undecidable whether some given states will always appear in computations by the given cellular automaton. It also follows that a weaker form of expansivity, which is a concept of dynamical systems, is an undecidable property for reversible one-dimensional cellular automata.

It is shown that several properties of dynamical systems are undecidable for reversible one-dimensional cellular automata. It shown that sensitivity to initial conditions and topological mixing are undecidable properties. Furthermore, non-sensitive and mixing cellular automata are recursively inseparable. It follows that also chaotic behavior is an undecidable property for reversible one-dimensional cellular automata.

Files:

Full publication in PDF-format

BibTeX entry:

@PHDTHESIS{phdLukkarila10a,
  title = {On Undecidable Dynamical Properties of Reversible One-Dimensional Cellular Automata},
  author = {Lukkarila, Ville},
  number = {129},
  series = {TUCS Dissertations},
  school = {Turku Centre for Computer Science},
  year = {2010},
  ISBN = {978-952-12-2464-5},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication