Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Two-by-two Substitution Systems and the Undecidability of the Domino Problem


Speaker: Nicolas Ollinger
Slot: Array, 11:00-11:20, col. 3

Abstract

Thanks to a careful study of elementary properties of two-by-two substitution
systems,
we give a complete self-contained elementary construction of an aperiodic tile
set and sketch
how to use this tile set to elementary prove the undecidability of the classical
Domino Problem.

websites: Arnold Beckmann 2008-05-19