Theory of computing : An open introduction

Abstract

Theory of Computing: An Open Introduction is a book suitable for courses on the theory of computing at both the undergraduate and graduate levels, and for self-study. Topics are introduced in a logical order: we begin with the simple finite automaton and progressively introduce stronger models of computation, up to the Turing machine. We then shift from the models themselves to what the models can compute, which opens up a discussion on computability and decidability. This leads us to a journey through complexity theory. The remainder of the book focuses on a selection of special topics.