### From BIMIB

# Seminar June 23, 2009, 10.30

### Tilings and Computability

*Michael Weiss*

*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.