Computational Models and Computability

Computability is the study of the limits of computing: what can be computed and, more interesting, what cannot be computed.

Note that we are not interested in showing that there are problems we don't know how to solve today but maybe we'll solve tomorrow, rather we are interested in showing that there are problems that can be shown (proved) to have no possible algorithmic solution!

We can't agree on what can or cannot be computed unless we agree on a reasonable model of a computer. We need a formal model of a computer that (a) allows each algorithm to be described in a finite number of steps and (b) each step can be carried out mechanically.

The most basic computer is a mathematical concept called a Turing machine. Counter programs are a very different, yet equally powerful, computational model. The Church-Turing thesis states that all known models of computation are equivalent.

Using these formal models of computation we can show that there are certain problems that are undecidable, which means they cannot be solved by any computer or computational model.