Computability Theory

       According to Herbert B. Enderton about his Computability theory, 
it  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 effective procedure—
some algorithm—that, given a sentence about the positive integers, will decide
whether that sentence is true or false. In other words, is the set of true sentences
about the positive integers decidable? Or for a much 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 of any given positive
integer whether or not it is a prime number.
More generally, consider a set S, which can be either a set of natural numbers
(the natural numbers are 0, 1, 2, . . .), or a set of strings of letters from a finite
alphabet. (These two situations are entirely interchangeable. A set of natural
numbers is very much like a set of base-10 numerals, which are strings of digits.
And in the other direction, a string of letters can be coded by a natural number
in a variety of ways. The best way is, where the alphabet has k symbols, to
utilize k-adic notation, which is like base-k numerals except that the k digits
represent 1, 2, . . . , k, without a 0 digit.) We say that S is a decidable set if
there exists an effective procedure that, given any natural number (in the first
case) or string of letters (in the second case) will eventually end by supplying
the answer: “Yes” if the given object is a member of S and “No” if it is not a member of S.