That’s Impossible!

Computers can solve many kinds of computational problems. But there are limits to what computers can do. For some problems, the fastest known programmes would take trillions of years to run on the fastest computer ever built (and there are reasons to believe that no faster programmes exist). But even more surprisingly, there are some computational problems that cannot be solved at all by a computer.

How can we show that a problem is impossible to solve? It is not sufficient to say no known solution exists maybe 10 000 years from now, somebody really, really clever will come up with a solution. Mathematics can help us prove that some problems will never be solved, no matter how clever programmers become. Along the way, this talk will show a bit of elementary transfinite number theory, and see whether army generals can coordinate an attack using carrier pigeons