September 21, 2017, Thursday

From BIMIB

Jump to: navigation, search

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.