Current Trends in Theory and Practice of Computer Science  
Track filter:   
Invited Talk
Foundations of Computer Science

Thursday, January 24, 15:30 - 17:00

Jarkko Kari

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.

pdf iconPresentation (473 kB)
SOFSEM 2008, January 19-25, High Tatras, Slovakia