Books on Theory of Computation

Algorithmic Randomness and Complexity
by R. G. Downey, D. R. Hirschfeldt, 2010, 629 pages, 4MB, PDF

Around Kolmogorov Complexity: Basic Notions and Results
by Alexander Shen, 2015, 51 pp, 300KB, PDF

Automata and Rational Expressions
by Jacques Sakarovitch, 2015, 49 pp, 430KB, PDF

Bayesian Computational Methods
by Christian P. Robert, 2010, 59 pp, 3.7MB, PDF

Brief Primer on the Fundaments of Quantum Computing
by Richard L Amoroso, 2018, 140 pp, 6.3MB, PDF

Cellular Automata
Wikibooks, 2010

Cellular Automata And Complexity: Collected Papers
by Stephen Wolfram, 1994

Cellular Automata: Simplicity Behind Complexity
edited by Alejandro Salcido, 2011, 566 pages, 31MB, PDF

Combinatorial Optimization: Exact and Approximate Algorithms
by Luca Trevisan, 2011, 139 pages, 830KB, PDF

Communication Complexity
by Domotor Palvolgyi, 2005, 39 pages, 380KB, PDF

Complexity Theory
by Johan Hastad, 2008, 130 pages, 0.7MB, PDF

Computability and Complexity
Wikibooks, 2010

Computability and Complexity from a Programming Perspective
by Neil D. Jones, 1997, 485 pages, 1.7MB, PDF

Computability and Randomness
by Andre Nies, 2008, 447 pages, 2.6MB, PDF

Computability Theory
by Wilfried Sieg, 2006, 125 pp, 1.9MB, PDF

Computability, Unsolvability, Randomness
by Stephen G. Simpson, 2009, 151 pp, 910KB, PDF

Computational Complexity: A Modern Approach
by Sanjeev Arora, Boaz Barak, 2008, 489 pages, 4.4MB, PDF

Computational Modeling and Complexity Science
by Allen Downey, 2008, 97 pages, 1.4MB, PDF

Evolution of Parallel Cellular Machines: The Cellular Programming Approach
by Moshe Sipper, 1997, 213 pp, 1.8MB, PDF

Exploring Discrete Dynamics
by Andrew Wuensche, 2011, 536 pp, 21MB, PDF

From Complexity to Creativity
by Ben Goertzel, 1996

From Philosophy to Program Size
by G. J. Chaitin, 2003, 54 pages, PS/PDF

The Functional Analysis of Quantum Information Theory
by Ved Prakash Gupta, Prabha Mandayam, V. S. Sunder, 2014, 123 pp, 930KB, PDF

Handbook of Quantum Information
Quantiki, 2013, online html

Introduction to Complexity Theory
by Oded Goldreich, 1999, 375 pages, 2.3MB, PDF

Introduction to Computability Theory
by Dag Normann, 2010, 95 pp, 430KB, PDF

Introduction to Computational Complexity
by Martin Tompa, 1991, 85 pages, 1MB, PDF

Introduction to Quantum Algorithms for Physics and Chemistry
by Man-Hong Yung, et al. 2012, 44 pp, 2MB, PDF

Introduction to Quantum Cellular Automata
by B. Aoun, M. Tarifi, 2004, 46 pages, 330KB, PDF

An Introduction to Quantum Computing using Cavity QED concepts
by Zachary Burell, 2012, 53 pp, 260KB, PDF

An Introduction to the Theory of Computation
by Eitan Gurari, 1989, 314 pages, 3.2MB, ZIP/HTML

Introduction to Theory of Computation
by Anil Maheshwari, Michiel Smid, 2012, 246 pp, 1.2MB, PDF

Lecture Notes on Computational Complexity
by Luca Trevisan, 2004, 171 pages, 0.9MB, PDF

Logic and Automata: History and Perspectives
by Jorg Flum (ed), 2007, 737 pp, 5.4MB, PDF

Logic for Computer Scientists
by Uli Furbach, 2010

Mathematical Foundations of Automata Theory
by Jean-Eric Pin, 2012, 310 pp, 1.9MB, PDF

Models of Computation: Exploring the Power of Computing
by John E. Savage, 1998, 698 pp, 4.3MB, PDF

Notes on Automata, Logics, Games and Algebra
by K Narayan Kumar, 2007, PDF

P, NP, and NP-Completeness: The Basics of Complexity Theory
by Oded Goldreich, 2010, 190pp, 1.9MB, PS

Physics, Topology, Logic and Computation: A Rosetta Stone
by John C. Baez, Mike Stay, 2009, 73 pages, 780KB, PDF

Quantum Computing: Progress and Prospects
by Emily Grumbling, Mark Horowitz, 2018, 206 pp, 8.9MB, PDF

Quantum Computing Since Democritus
by Scott Aaronson, 2006, 398 pp, online html

Quantum Hamiltonian Complexity
by S. Gharibian, Y. Huang, Z. Landau, S. W. Shin, 2014, 58 pp, 1.3MB, PDF

Quantum Information and Computation
by John Preskill, 1998, 481 pp, 2.7MB, PDF

Quantum Information: primitive notions and quantum correlations
by Valerio Scarani, 2009, 74 pp, 840KB, PDF

Quantum Walks: A Comprehensive Review
by Salvador E. Venegas-Andraca, 2012, 88 pp, 1.5MB, PDF

Recursion Theory
by Frank Stephan, 2009, 125 pp, 610KB, PDF

Rule-based Computation and Deduction
by Helene Kirchner, Pierre-Etienne Moreau, 2001, 100 pp, 870KB, PDF

Superconducting Qubits and Circuits
by Steven M. Girvin, 2011, 132 pp, 2.9MB, PDF

Think Complexity: Complexity Science and Computational Modeling
by Allen B. Downey, 2012, 146 pp, 1.2MB, PDF

Tree Automata Techniques and Applications
by H. Comon, M. Dauchet, R. Gilleron, 2008, 262 pages, 2MB, PDF