Elements of Computability, Decidability, and Complexity

These lecture notes are intended to introduce the reader to the basic notions of computability theory, decidability, and complexity. More information on these subjects can be found in classical books. The results reported in these notes are taken from those books and in various parts we closely follow their style of presentation. The reader is encouraged to look at those books for improving his/her knowledge on these topics. Some parts of the chapter on complexity are taken from the lecture notes of a beautiful course given by Prof. Leslie Valiant at Edinburgh University, Scotland, in 1979. It was, indeed, a very stimulating and enjoyable course. For the notions of Predicate Calculus we have used in this book the reader may refer to classical books.