Beyond Infinity

How can you be sure that truly insoluble problems actually exist, and that they're not just waiting for a clever solution to be found? It was the British mathematician and computer pioneer Alan Turing who established that there are some things that computers will never be able to do.

Turing based his discovery on an extraordinary piece of work by the 19th century German mathematician Georg Cantor, who discovered that there are numbers greater than infinity. Cantor's proof can be stated in many different ways, but one simple form is this: imagine that you could write down a table showing the binary form of every integer from zero to infinity. Each number appears as an endless string of ones and zeros. Now, mark a diagonal across the table so that it joins the first bit of the first number, second bit of the second number and so on, all the way to infinity. Next, flip every one of those bits on the diagonal, changing one to zero and zero to one.

The diagonal string of binary bits you now have clearly represents a whole number. And because your original table included every whole number, it has to be one of those. Or does it? It can't be the first number because it differs in the first bit. It can't be the second, because the second bit is different. It can't be the nth, because the nth bits don't match. So you've just created a number that isn't present in the list of all numbers. The only way out of this paradox is to accept that the number of integers is actually greater that infinity.

Cantor established that there was a distinction between infinity which is countable, and so-called transfinite numbers which are even bigger and can't be counted. Transfinite numbers are important in many areas of mathermatics and computer theory. Turing applied them in a particularly ingenious way. He was able to show that the number of possible algorithms, or computer programs, is infinite, but that the number of possible problems is transfinite. Hence, some problems can never be solved by a computer.