Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On the Tiling Problem and Reve...

On the Tiling Problem and Reversible Cellular Automata

Ville Lukkarila, On the Tiling Problem and Reversible Cellular Automata. TUCS Technical Reports 788, Turku Centre for Computer Science, 2006.

Abstract:

It is shown that the (infinite) tiling problem is undecidable even if the given tile set is deterministic by two opposite corners, i.e. a tile is uniquely determined by both the colors of the two sides adjacent to some corner and the colors of the sides directly opposite to these sides. The reduction is done from the Turing machine halting problem and uses the 4-way deterministic aperiodic tile set of Kari and Papasoglu.

The tile set construction given here implies also the universality of one-dimensional reversible cellular automata. More specifically, a new proof is given for the result of Dubacq, that any (irreversible) Turing machine can be simulated in real time with a one-dimensional reversible cellular automaton.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tLukkarila06b,
  title = {On the Tiling Problem and Reversible Cellular Automata},
  author = {Lukkarila, Ville},
  number = {788},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {cellular automata, determinism, reversibility, tiling problem, Wang tiles},
  ISBN = {952-12-1787-1},
}

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

Edit publication