Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Chapter 1. The Computability Concept > 1.1 The Informal Concept - Pg. 1

1 The Computability Concept 1.1 1.1.1 The Informal Concept 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 or not any given integer is a prime number. (For a very large number, the procedure taught in the schools might take a long time.) If we want, we can write a computer program to execute the procedure. Simpler still, the set of even integers is decidable. We can write a computer program that, given an integer, will very quickly decide whether or not it is even. Our goal is to study what decision problems can be solved (in principle)