"Theory of Computing: An Open Introduction" by Taylor J. Smith, Assistant Professor of Computer Science, StFXThis book is 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.
