Skip to content

@boazbk boazbk released this Sep 1, 2020

Fixed annoying conflict that somehow escaped my attention before

Assets 3

@boazbk boazbk released this Aug 31, 2020

Made a set of minor corrections to version 0.9

Assets 3
  • 0.9
  • 9b2070b
  • Compare
    Choose a tag to compare
    Search for a tag
  • 0.9
  • 9b2070b
  • Compare
    Choose a tag to compare
    Search for a tag

@boazbk boazbk released this Aug 26, 2020

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

Assets 3

@boazbk boazbk released this Nov 30, 2019

End of the semester version.

Assets 3

@boazbk boazbk released this Sep 25, 2019

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..

Assets 3

@boazbk boazbk released this Jun 10, 2019

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.

Assets 3

@boazbk boazbk released this Feb 11, 2019

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.

Assets 3
Feb 11, 2019
Feb 11, 2019

@boazbk boazbk released this Jan 21, 2019

This is the version of the book as per December 2018. I am releasing it here before making some changes to the notation.

In this version the computational models are:

  • NAND: Straightline programs with NAND operation (equivalent to Boolean circuits with NAND gates)

  • NAND++: Programs with loops (equivalent to Turing machines, in this version, "vanilla" NAND++ corresponds to oblivious Turing machines)

  • NAND<<: Programs with random access memory, equivalent to RAM machines.

The upcoming versions (0.5.x and onwards) will be less "idiosyncractic" in the sense that Boolean circuits, Turing machines, and RAM machines are introduced before their programming-language analogs. The names of the programming languages will also change to emphasize the relation with the more standard models, and so we will have

  • NAND-CIRC: Straightline programs with NAND operation (equivalent to Boolean circuits with NAND gates)

  • NAND-TM: Programs with loops equivalent to standard single tape Turing machines.

  • NAND-RAM: Programs with random access memory, equivalent to RAM machines.

Assets 3