In corporate and government bureaucracies, the standard method for making a presentation is to talk about a list of points organized onto slides projected up on the wall. For many years, overhead projectors lit up transparencies, and slide projectors showed high-resolution 35mm slides. Now "slideware" computer programs for presentations are nearly everywhere. Early in the 21st century, several hundred million copies of Microsoft PowerPoint were turning out trillions of slides each year.
Alas, slideware often reduces the analytical quality of presentations. In particular, the popular PowerPoint templates (ready-made designs) usually weaken verbal and spatial reasoning, and almost always corrupt statistical analysis. What is the problem with PowerPoint? And how can we improve our presentations?
Wang tiles (Hao Wang, 1961) are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.
The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern.
In 1966, Wang's student Robert Berger solved the problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem then implies the undecidability of Wang's tiling problem.