Foundations of Computer Science
Thursday, January 24, 15:30 - 17:00
Undecidability of the Tiling Problem
A classical result by R.Berger (1964) states that it is undecidable
if a given set of tiles admits a valid tiling of the plane.
We give a new, simple proof of this result. Then we show how
our proof can be modified to demonstrate the undecidability
of the tiling problem on the hyperbolic plane, thus answering
an open problem asked by R.M.Robinson in 1971.