(This article represents a brief divergence from our usual focus on distributed systems and algorithms. Normal service will be resumed shortly.)

One of the courses I do some teaching for is the dryly named ‘Theory of Computation’. Although such a course name is unlikely to pique a lot of interest, in actual fact it is probably the most fundamental and important course that you could take about computer science. Computation theory allows us to ask, and answer, questions about the limits of computers and the programs they execute. Is every problem solvable by a computer program? What do we even mean by a ‘problem’?

It turns out that there are profound and beautiful truths to be discovered when considering these questions. In a short series of articles, I’m going to give a brief introduction to the theory of computability, aimed at those who have never studied Turing machines, Cantor diagonalisation or Godel incompleteness. An appreciation for some of these ideas and results should give a perspective on what computers are, and are not, capable of.

This first article presents a bit of background material on the nature of infinity, which is right at the heart of computation theory. In the next article I’ll tie this in with the idea of computability and show how these ideas elegantly allow us to establish limits on what we can do with computers – even in theory, let alone practice.

Continue reading →