A curated collection of best learning resources on IT topics

All topics -> Computer science -> Theory of computation

Theory of computation studies the fundamental capabilities and limitations of computers. It's concerned with three main questions:

  1. What is computation?
  2. What can and cannot be computed?
  3. How difficult is it to compute something?

These questions are explored in three corresponding branches of the theory of computation: automata theory, computability, and complexity.

Links: Theory of computation (Wikipedia).

Here's 3 amazing resources to learn Theory of computation:

  1. Introduction to the Theory of Computation, 3rd edition (www.amazon.com)
    paid • book • by Michael Sipser • 2012

    This book covers all three major branches of the theory of computation: automata theory and languages, computability, and complexity. You'll learn about seminal results on finite automata and context-free languages, Turing machines and decidability, P and NP and other computational classes. It's rigorous, accessible, and fun – a must read.

  2. The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine (www.theannotatedturing.com)
    paid • book • by Charles Petzold • 2008

    In 1937 Alan Turing published a paper titled "On Computable Numbers" in which he introduced Turing Machines – a computational model that captured the notion of "effective computation". Using this model, Turing showed that there are problems computers cannot solve. In this book Charles Petzold presents the original Turing's paper with his commentary and the mathematical and historical background necessary to understand and fully appreciate Turing's influential work.

  3. Elements of Automata Theory (www.amazon.com)
    paid • book • by Jacques Sakarovitch • 2013

    This book is a treatise on finite automata theory. It's 750-page-long, very mathematical, and yet exceptionally well-written text. You'll learn about fundamental notions like rationality and recognizability as well as advanced results about finite automata over different mathematical structures.