Release for Fall 2023

Frozen version for Fall 2022

Frozen version from Fall 2021. Changes over last release are mostly typos, but also two minor modifications for definitions:

• We measure the size of a circuit or straightline program by the number of gates/lines. For example, the constant zero function on n inputs can be computed by a circuit of at most 10 gates, independently of n. This means that the class SIZE(100) for example contains infinitely many functions, but we typically try to only use SIZE_n(100) or SIZE_{n,m}(100) which are finite classes.

• The output of a Turing machine is the contents of the tape between the "begin tape" and the "empty" symbols. Previously it was until the first head position. The new convention makes composition easier, though notes it means a Turing machine can compute the identity function in constant time.

Fixed annoying conflict that somehow escaped my attention before

Made a set of minor corrections to version 0.9

This is a version of the book as of Fall 2020.
I will not make any major edits during the fall, so as not to disrupt classes that are using this as a textbook

End of the semester version.

September 2019 version. Making this release since I am teaching the course this term and as I encounter comments etc.. will make updates to the book that might change theorem numbering etc..

More edits to emphasize Turing Machine and Boolean Circuits model. Added significant number of new figures and exercises. Text is now more "linear" - removed many footnotes by either incorporating in text or moving to bibliographical notes.

This version is less "idiosyncratic" -

• We now use NAND-CIRC, NAND-TM, and NAND-RAM for the programming-language analogs of Boolean circuits, Turing machines, and RAM machines respectively.

• The standard models are introduced before their programming language analogs and emphasized more.

• Also started adding references and more exercises - will keep working on this.