The Domino Problem

[Tev]

...Can someone explain it to be? As far as I can tell its something to do with trying to fit tiles to a plane with no spaces.

[Ben]

I found on Mathworld that the domino problem is the same as Wang's Conjecture, which is stated as:

Wang's conjecture states that if a set of tiles can tile the plane, then they can always be arranged to do so periodically (Wang 1961). The conjecture was refuted when Berger (1966) showed that an aperiodic set of tiles existed. Berger used 20426 tiles, but the number has subsequently been greatly reduced. In fact, Culik (1996) has reduced the number of tiles to 13.

There is a small section on tiling here: mathworld.wolfram.com/Tiling.html

I think what it means is that given any set of shapes, you may be able to fill a given space or plane, but you cannot always get them to tessellate. The examples are things like Kepler's Monsters and the Penrose Tiles.

[Chris]

You actually went to the EXACT SAME WEB-PAGES as me. That's kinda creepy, though I guess mathworld is generally quite useful.

[Ben]

heh, well you know me. It's my first port of call, followed briefly by Wikipedia then a search on Google.

[Tom]

natalie knows all about the donimo problem!