Elements of computability, decidability, and complexity

In this book we introduce some fundamental notions of Computability Theory, Decidability Theory, and Computational Complexity. We first consider the theory of computability based on Turing Machines and we illustrate how from simple devices one can build very powerful computational machines. We then present the theory of the Partial Recursive Functions. It provides an axiomatic characterization of the computable functions without referring to the notions of processor and memory. We also present various stratifications of the class of the Primitive Recursive Functions, which is an important subclass of the Partial Recursive Functions. The part of the book on Decidability Theory is focused on the undecidabilty of the Halting Problem and the Post Correspondence Problem. We also consider various decidable and undecidable problems concerning the context-free languages. Finally, we introduce some elementary notions of Computational Complexity. Our complexity measures refer to the Turing Machine model, but most of the definitions and results can be extended also to other models of computation, such as the von Neumann Machine and the Random Access Machine. We also introduce and illustrate the notions of problem reducibility, NP-completeness, approximation algorithms, interactive proof systems, randomized complexity, and parallel complexity.