Computability Theory

1 The Computability Concept

1.1 The Informal Concept

1.1.1 Decidable Sets

Computability theory, also known as recursion theory, is the area of mathematics

dealing with the concept of an effective procedure – a procedure that can be carried out

by following specific rules. For example, we might ask whether there is some effec-

tive procedure – some algorithm – that, given a sentence about the integers, will decide

whether that sentence is true or false. In other words, is the set of true sentences about

the integers decidable? (We will see later that the answer is negative.) Or for a simpler

example, the set of prime numbers is certainly a decidable set. That is, there are quite

mechanical procedures, which are taught in the schools, for deciding whether ...