Jupyter notebooks with some NAND code
Switch branches/tags
Nothing to show
Clone or download
Latest commit 1536c30 Nov 8, 2018
Permalink
Failed to load latest commit information.
.gitattributes added presentation Sep 27, 2018
3colgadget.png update presentation Oct 23, 2018
BFassignment.ipynb bf assignment Oct 30, 2018
Cook_Levin.ipynb update lecture 16 Oct 25, 2018
ISETtoMAXCUT.png update presentation Oct 23, 2018
Lec_7_lambda.ipynb added lecture 7 Sep 24, 2018
Lecture03_Defining_Computation.ipynb fixed notebook Sep 11, 2018
Lecture04_sugar.ipynb update lecture 4 Sep 13, 2018
Lecture_16_Cook_Levin.ipynb update lecture 16 Oct 25, 2018
NAND overview.ipynb added notebooks Nov 6, 2017
NAND programming language.ipynb edited notebooks Jun 19, 2018
NAND_gate.png update presentation Oct 23, 2018
NANDpp_configurations.ipynb update configurations Oct 11, 2018
NANDpp_language.ipynb edited notebooks Jun 19, 2018
NANDpp_overview.ipynb added notebooks Nov 6, 2017
NANDshift_language.ipynb nandshift Sep 22, 2018
NANDutils.ipynb update Oct 29, 2018
README.md update readme Jun 3, 2018
Reductions.ipynb added notebooks Nov 6, 2017
abstractions_talk1.pptx added lecture 7 Sep 24, 2018
ahlfors.png updated lecture 3 Sep 11, 2018
blog.ipynb added notebooks Nov 6, 2017
clique.png update presentation Oct 23, 2018
compendium.png update lecture 16 Oct 25, 2018
environment-old.yml added notebooks Nov 6, 2017
environment.yml added notebooks Nov 6, 2017
githubbutton.png updated binder links on readme May 21, 2018
halting1.pptx added presentation Sep 27, 2018
karastubavsgschool.png update presentation Oct 23, 2018
karp_abstract.png update presentation Oct 23, 2018
karp_problems.png update presentation Oct 23, 2018
karpthm1.png update presentation Oct 23, 2018
lambda.ipynb edited notebooks Jun 19, 2018
lec_01_introduction.ipynb lec 1 karastubaa May 8, 2018
lec_15_reductions.ipynb update presentation Oct 23, 2018
lec_17_PvsNP.pptx update Oct 29, 2018
maxcut.png update presentation Oct 23, 2018
moorelaw.jpeg update Oct 29, 2018
npcompletexkcd.png update lecture 16 Oct 25, 2018
npreductions.png update lecture 16 Oct 25, 2018
nvsnsquared.png update presentation Oct 23, 2018
offlinebpp.pptx powerpoint Nov 8, 2018
satinstances.png update presentation Oct 23, 2018
satsolvers.png update presentation Oct 23, 2018
size_vs_func2.pptx update lecture 4 Sep 13, 2018
transistor-NAND-Gate.png update presentation Oct 23, 2018

README.md

The NAND programming languages

This is a collection of Jupyter Notebooks for the NAND family of programming languages that accompany the upcoming book Introduction to Theoretical Computer Science.

You can launch all the notebooks live using either Binder or Azure notebooks, see below for links to Google collaborative notebooks versions as well.

However, if you want to play with them more extensively you'd probably want to download them to your own machine. You can do so by (1) clone/download (using the this button button on the top right corner) all of the files to a local folder, (2) install anaconda, and then install Jupyter Lab by opening up a command prompt (or maybe "anaconda prompt", in windows) and type conda install -c conda-forge jupyterlab. You then change directory to the folder containing these notebooks and type jupyter lab. For visualizing circuits you will need to also install graphviz, which I believe can be done by typing conda install -c anaconda graphviz

The main notebooks contained in this repository are:

  1. The NAND Programming Language ( live version on binder version on google collab ): Definition of the NAND programming language, relation to Boolean circuits, syntactic sugar, computing every function, and representing it as list of triples

  2. Blog post about the course (live version version on google collab ) : High level overview of the main results in the course.

  3. NAND++ programming language ( live version version on google collab ): Overview of the NAND++ programming lanaguage.

  4. The Cook Levin Theorem (live version version on google collab ): Overview of the Cook Levin Theorem.

  5. Lambda calculus ( live version version on google collab ): Some notes on the lambda calculus and the Y combinator.

Note: As of Summer 2018 I am changing a bit the syntax of the languages, and hence some notebooks use the older syntax foo := bar NAND blah and some use the newer syntax foo = NAND(bar,blah)