# Theory of computation books online

Here is a list of online books about Theory of computation in various formats available for free :

Advanced Complexity Theory

by Daniel Spielman, 2001, PDF

Algorithmic Randomness and Complexity

by R. G. Downey, D. R. Hirschfeldt, 2010, 629 pages, 4MB, PDF

Bayesian Computational Methods

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

Cellular Automata

Wikibooks, 2010

Cellular Automata: Simplicity Behind Complexity

edited by Alejandro Salcido, 2011, 566 pages, 31MB, 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

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

From Philosophy to Program Size

by G. J. Chaitin, 2003, 54 pages, PS/PDF

Handbook of Quantum Information

Quantiki, 2013, online html

Introduction to Complexity Theory

by Oded Goldreich, 1999, 375 pages, 2.3MB, 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

Lecture Notes on Algorithm Analysis and Computational Complexity

by Ian Parberry, 119 pages, 1.9MB, PDF

Lecture Notes on Computational Complexity

by Luca Trevisan, 2004, 171 pages, 0.9MB, PDF

Logic for Computer Scientists

by Uli Furbach, 2010

Mathematical Foundations of Automata Theory

by Jean-Eric Pin, 2012, 310 pp, 1.9MB, 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 Computation

by John Watrous, 2006, 139 pages, 660KB, 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