ABSTRACT

We now have some good models of computability, and they all turn out to be equivalent. These models enable us to talk about computability with some confidence that what we are saying can be rigorously justified. Many natural examples of everyday sets, functions and relations can be easily fitted into these models. But not all such examples — as we come to suspect in what follows. Before this chapter is finished we will have found that mathematics, at least, is riddled with easily described, but incomputable, objects.