From the beginning of the twentieth century questions concerning the decidability of logical and mathematical theories have held a special interest for logicians, mathematicians, and philosophers. A number of important concepts and far-reaching results in this field have come from Alonzo Church (1903–1995), author of a definitive text on logic and noted writer on the history of logic.

The notion of decidability is not one which a beginner in mathematics could explicitly formulate, but both this and related notions, such as that of effective calculability, have a place in the description of the most elementary mathematical concepts. Often our understanding of a particular numerical predicate is inextricably tied to our ability to determine whether or not an arbitrary number satisfies that predicate, and in many cases terms expressing the result of a calculation or computation can be fully grasped only by one who has the ability to carry out...