Seminar June 23, 2009, 10.30
Tilings and Computability
Tuesday June 23, 2009, DISCo U14, Seminar Room, 10:30
In the early sixties, Wang has introduced the study of tilings with colored tiles to solve mathematical logical problems. In this model, a tile is a unit size square with colored edges and two tiles can be assembled if their common edge has the same color. To tile consists in assembling tiles from a tile set (a finite set of different tiles) on the grid Z^2. The tiles can be repeated as many times as needed, but cannot be turned. Berger has shown that to know whether a tile set tiles the plane or not is undecidable.
In this talk we show the main results of tilings: simulation of Turing computation, quasiperiodicity function, aperiodicity... Then we show a sample of the last result concerning tiling's computability.