X Advertisement for Corq Mobile Event Engagement Application

Corq for Android

View

Learning

Event Time and Date

Wednesday, April 5 2017, 5:45 PM to 6:35 PM

A Wang tileset is a finite set of tiles with colored edges.  Two tiles can be placed next to each other if they have matching colors on the edge that they share.  Now suppose you have an unlimited number of copies of each tile from the tileset.  Is there a way to cover the entire plane by placing tiles legally?  If so, we say that tileset can tile the plane.

Which tilesets can tile the plane, and which cannot?  There are examples of both types, but in the 1960s Berger proved that an algorithm to decide this question for an arbitrary tileset does not exist!  In other words, the tiling problem is undecidable.

All proofs of this undecidability rely on a trick of Wang, which I will present.  I will discuss the difficulties in going from Wang's trick to the full undecidability result, and mention the main features of a recent proof of the full result due to Durand, Romashchenko and Shen.

Monteith 321