Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

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

Edit abstract data

Speaker: Nicolas Ollinger
Slot: Fri, 11:00-11:20, Room 24 (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 Valid HTML 4.01! Valid CSS!