Mission Impossible I: The Uncomputable Jigsaw Floor

You are a floor tile designer: a job that has existed at least since the Roman times so not exactly arcane. You'd have thought there were no real problems in store. Turns out you'd be wrong. There are problems with solutions but that even the Mission Impossible Team couldn't help you with.

You are currently designing tiles with abstract patterns based loosely on the idea of dominos. The tiles will all be square but divided across the diagonals into 4, with possibly different colours in each quarter. The domino part of your design idea is that when the tiles are laid, all 4 sides' colours must match those on adjacent tiles. Each tile also has a particular orientation - one edge of each tile is designated to always go at the top. It's a bit like a jigsaw really - in fact you can buy similar puzzles with lots of identically shaped tiles where you have to match all the pictures.

You are designing a whole series of tile sets based on this idea. Each tile set will have a particular collection of tiles that are then laid in a customer's room following the domino rule. You are happy to get any number of tiles of each kind made, but new tile patterns cannot be added.

Here is the rub though - you need to know that each tile set you come up with will work for any rectangular room, whatever its size without breaking the domino rule of colours matching on all 4 sides. You don't want to advertize designs unless they work anywhere...bad for business to have to say "No you cant use that design for your house!".

No problem though...you just need a program where you feed in the description of a set of tiles you propose and it will tell you if it will always work whatever the room ... and your mate Hannah is a programmer. She will knock up a program ...won't she?

Turn's out she can't...No one can. No one ever will. Innocuous as it seems this problem is one of a class of problems that are Uncomputable. It is impossible for any computer, either now or in the future, to solve the problem. Hannah may be able to write a program that can tell you the answer for some designs, but a program that can tell you the answer for any tile design you come up with will never exist.