Chapter 1. Preface

The present note is based on and made for the Theory of Computing course held at the University of Debrecen.

The the fundamental aim of the course - and therefore of the lecture note - to give an adequate background knowledge for the students of the basics in computability and complexity theory.

The structure of the book is the following:

Chapter 2 describes the necessary concepts and results in formal language theory, related to the general algorithmic problems and definition of the Turing machine.

Chapter 3 contains definitions and properties on the order of growth of functions which are frequently appears in complexity theory.

Chapter 4 discusses the definitions and the related basic properties of Turing machines. The computation of Turing machines, the Church-Turing thesis, the composition of Turing machines and the definition of multi-tape Turing machines and simulation theorems are described here.

In Chapter 5 one can read about the theory of computability, where recursivity, recursively enumerability and their relations are observed. At the end of the chapter some decidability problems are discussed.

Chapter 6 provides definitions and fundamentals on the properties of non-deterministic Turing machines and deals with their Turing equivalence.

In Chapter 7 the time, space and program complexity, the complexity classes defined by them and their relationship are regarded.

Chapter 8 discusses the results related to the class . Among others the witness theorem and -completeness are detailed.