Logical Approaches to Computational Barriers

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

Speaker:
| Nicolas Ollinger |

Slot: |
Array, 11:00-11:20, col. 3 |

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 |