Tilings, algorithms and automata (Laurent Bartholdi, ENS Lyon)

27.02.2020 16:15

Given a certain number of shapes, can you tile the floor of your (infinite) bathroom using only these shapes? The "tiling problem" asks for an algorithm that, given the shapes as input, answers whether such a tiling is possible.

The logician Hao Wang (王浩) considered a particularly simple form of this question, assuming all tiles are square but coloured on their edges, in connection with his study of monadic second-order logic; with his student Berger, he proved that the problem is undecidable — there is no such algorithm.

Since then, the problem has been considered in the more general setting of graphs, and in particular graphs produced using group theory. I will outline as well as possible the border between the decidable and the undecidable, involving some self-similar graphs, and will present a solution for some remarkable objects such as the Cayley graph of the "lamplighter group".


PS. The Colloquium will be followed by an aperitif

Lieu

Room 17

entrée libre