Complete impossibilities

I've discussed problems that can't be solved in less than a given time. But there are also problems that can't be solved at all.

• Diophantine equations. A Diophantine equation is a polynomial equation such as , where the solutions are restricted to being integers. It is impossible to write an algorithm that will tell you, for any Diophantine equation, whether it has a solution. Emperor's New Mind p 129.

• Tiling the plane. Is there an algorithm that will tell you whether, given any set of polygons, it's possible to cover an infinite plane with no gaps and no overlaps? Obviously one can do this for some sets, e.g. that containing just one square. But can it be done in general? Again, it can't. Emperor's New Mind p 132.

• Topological equivalence of manifolds. Informally, a manifold is (in two dimensions) a closed surface. For example: the surface of a sphere; the surface of a cup; the surface of a doughnut. Two manifolds are equivalent if you can deform one into the other without cutting or tearing. Think of each being made of infinitely elastic rubber. Can you write a program that takes two manifolds and tells you whether they're equivalent. For two-dimensional manifolds, yes. For four-dimensional ones and higher, no. For three-dimensional ones, no-one knows whether it's possible or not (as far as I know). It's very odd that one dimension should cause a switch from a soluble to an insoluble problem. Emperor's New Mind p 130.

• The word problem. You have an alphabet of letters. A word is just a sequence of letters. You also have a set of rules by which parts of words can be transformed into other words. Is it possible to write a program which tells you whether, given any words and , you can go from to by using these rules? Once again, no. Again, it can't. Emperor's New Mind p 131.