Thank you all for your clever questions, for your insightful problem-solving, and for your enjoyable Firestorm presentations! It was a pleasure to teach you all, and I hope you enjoy the rest of your summer.

Slides from the quiz review game

Booklet of puzzles that you all submitted

Present a 5-minute class to your peers!

**Covered in class:** Interactive proofs. **Additional resources **– Sipser 10.4.

**Homework:** Prepare to teach your Firestorm class on Wednesday! Remember, 5 minutes.

**Other resources:**

- ★★★ Interactive zero-knowledge proofs demo involving 3-coloring, that we saw in class
- ★★★ In Code: A Mathematical Journey (book) – an excellent read if you're curious to learn more about prime numbers, modular arithmetic, RSA, and more!
- ☆★★ The Code Book (book) – recommended if you're interested in the history of cryptography
- ☆★★ IP=PSPACE proof

**Covered in class:** Diffie-Hellman key exchange example and the RSA cryptosystem. **Additional resources **– Sipser 10.6.

**Reading:** None today! Optionally, you can try to install PGP and get yourself your very own public/private key. I would be happy to sign your PGP key. Let me know if you encounter any issues.

**Other resources:**

- ★★★ Interactive demo of RSA
- ★★★ A blog post describing Shor’s factoring algorithm
- ☆★★ A long, but thorough, explanation of how quantum computing
*really*works, if you are so inclined.

**Covered in class:** The one-time pad -- the only perfectly-secure cryptography. We also played the card game Kemps in class.

**Reading, due Monday:** read The Limits of Quantum by Scott Aaronson. **Write:** If P is not equal to NP, might it still be possible that certain methods for cryptography -- which rely on factoring being hard -- might be broken?

**Other resources:**

- ☆★★ Supplementary notes about the one-time pad and similar forms of cryptography. See pages 5-8.

**Covered in class:** All about prime numbers.

**Reading, due Thursday:** read Quantum-Mechanical Computers by Seth Lloyd. **Write:** Presumably you had some preconceived notions about quantum computing. Name one thing that you learned about quantum computing that was unexpected or that surprised you.

**Covered in class:** DNA origami and DNA computing. The Knights’ Problem (paper and slides).

**In-class problem-solving:** handout. (solutions)

**Reading, due Wednesday:** read Computing with DNA by Leonard Adleman. Answer these questions (handout).

**Other resources:**

- ☆★★ DNA fractals and Sierpinski triangles!
- ☆★★ DNA origami: (1), (2)
- ☆★★ Adleman’s paper in
*Science*

**Covered in class:** NP-completeness. Cook-Levin theorem and CircuitSAT. NP-completeness reductions: 3-coloring widgets, Super Mario widgets, and Pokemon widgets. **Additional resources:** Sipser 7.4, Sipser 7.5.

**In-class problem-solving:** 3-coloring, Super Mario, and Pokemon.

**Reading, due Tuesday:** read section 2 (“The Basics”) and section 3 (“Soap Bubbles et al.”) of NP-Completeness and Physical Reality by Scott Aaronson. **Write:** What “experiment” does Scott Aaronson perform, and how do you interpret the results?

Optional, but enjoyable, are the first two paragraphs each of section 6 (“Relativity and Analog Computing”), section 8 (“Time Travel Computing”), and/or section 9 (“‘Anthropic Computing’”).

**Other resources:**

- ★★★ Classic Nintendo Games are (Computationally) Hard
- ★★★ Karp’s 21 NP-complete Problems – original paper

**Covered in class:** P, EXP, and NP. Two definitions of NP: as "non-deterministic Turing machines' polynomial time" and as "things you can verify in polynomial time". **Additional resources:** Sipser 7.1, Sipser 7.2, Sipser 9.1.

**In-class problem-solving:** P versus NP problems.

**Reading, due Monday:** The Status of the P Versus NP Problem by Lance Fortnow. **Write:** Why would a solution to the P versus NP problem be important for mathematics?

**Other resources: **

- ☆★★ The Complexity of Songs, a computer science inside-joke paper about computational complexity of various songs
- ☆★★ Interactive depiction of the three-coloring problem

**Covered in class:** Reviewed how to use big-O notation. More on asymptotic analysis and analyzing algorithms. Finished up the problems from yesterday. Introduced P and EXP (and PSPACE and EXPSPACE). **Additional resources:** Sipser 9.1, Sipser 9.2 (but both are highly detailed in a way that is beyond the scope of this course).

**Reading, due Thursday Monday:** The Status of the P Versus NP Problem by Lance Fortnow

**Other resources:**

- ☆★★ RSA Factoring Challenge – numbers that haven't been factored yet!

**Covered in class:** Big-O notation. Sorting functions by how fast they grow. **Additional resources:** Sipser 7.1.

**Reading, due Wednesday:** None today!

**Challenge Problem, due Wednesday:** Week 3 challenge problem – see the relevant section of these problems.

**In-class problem-solving:** handout

**Other resources: **

- ★★★ Asymptotic Notation – read this for a better idea of how to use big-O notation
- ★★★ Sorting Algorithms video – visually and aurally
- ☆★★ Merge Sort video – in dance!

**Covered in class:** Gödel’s incompleteness theorems, and proof. Quines and Gödel numbering.

**Reading, due Tuesday:** Minds, Machines, and Gödel. Be warned: it is somewhat dense and philosophical. Don't fret over every word.

Write: “What argument does the author use that connects Gödel’s theorems with Searle’s ‘Chinese Room’ argument?”

**In-class problem-solving:** handout

**Other resources:**

- ★★★ Quines – in a ton of different programming languages, courtesy of RosettaCode
- ★★★ Gödel’s incompleteness theorem – explained in words of one syllable or fewer
- ☆★★ Quine relay – a quine which passes through so many different languages
- ☆★★ Radiation-hardened quine – delete any character!
- ☆★★ Notes from 24.118
- ☆★★ Pset from 24.118

**Covered in class:** Searle’s “Chinese Room” argument (a.k.a. Day 10’s reading). We debated it.

**Other resources:**

**Covered in class:** Valid vs. sound arguments. Consistency, completeness, and soundness of logical systems. Short history of mathematical logic.

**In-class problem-solving:** Puzzles from *To Mock a Mockingbird* (email me to ask for the handout)

**Homework:** Is the Brain’s Mind a Computer Program? by John Searle. Write: Two things you agree with, and two things you disagree with. Come prepared to debate your opinion on strong AI versus weak AI with your classmates tomorrow.

**Other resources:**

- ★★★ Logicomix (book) – more about the history of mathematical logic
- ★★★ To Mock a Mockingbird (book) – logic puzzles and more
- ★★★ 6.045 notes on mathematical logic
- ☆★★ 24.118 Russell’s Paradox pset

**Covered in class:** Shannon entropy. Huffman encoding. Kolmogorov complexity. **Additional resources:** Sipser 6.4.

**In-class problem-solving:** The Heads and Tails of Huffman (solutions).

**Homework:** The Limits of Reason by Gregory Chaitin. Write: In one or two sentences, describe why Chaitin’s Ω is uncomputable.

**Covered in class:** notes. Check out a demonstration of BB(3) or BB(5) using TMSim.

**In-class problem-solving:** Reductions and the Halting Problem..

**Homework:** TMSim challenge problem due Friday! For Monday, read Who can Name the Bigger Number? and answer the question below.

**Question to answer:**

*In Who Can Name the Bigger Number, Scott Aaronson says: "Noticing this innovation, I declared the girl’s victory without bothering to count the 9’s on the cards."
When I was judging the Bigger Number Contest that we held in class, you might note that I never bothered to count just how many nines had been written, either. Yet somehow I could still declare one person to be unambiguously the victor in each round.
What would you do, if you were judging a Bigger Number Contest? What strategies would you use? When would you have to actually count the nines, and when could you safely ignore them? What are the possible strategies that people could use, and in what order would you rank them?*

**Other resources:**

- ★★★ Graham’s number – one of the largest numbers to have been used in a serious mathematical context. This Wikipedia article is an enjoyable read.
- ★★★ Knuth’s up-arrow notation – useful for defining large numbers. Also an enjoyable Wikipedia article.
- ☆★★ Ackermann numbers – what I confused the Ackermann function for, in class
- ☆★★ Ackermann function – an example of a computable function that grows really quickly, by the power of recursion
- ☆★★ 24.118: An account of a big number contest

**Covered in class:** Sipser 4.2 and 5.1.

**In-class problem-solving:** Decidability, recognizability, and enumeration.

**Homework:** read or skim Sipser 4.2 and Sipser 5.1 – these comprise the material that we covered in class today and yesterday. You should read with the aim of understanding this material better. **Assignment:** As before, write down one thing that you learned from the textbook, either in Sipser 3 or Sipser 4.2 and 5.1 – something new that we didn't cover in class, or something that the textbook explained more clearly.

**Also, finish the TMSim challenge problem! ** (TMSim program) (template)

**Other resources:**

- ☆★★ 24.118 notes on infinity (there is a corresponding pset that you may look at as well)
- ☆★★ 24.118 notes on Turing machines, computability, and Busy Beaver numbers (there is a corresponding pset that you may look at as well)

**Covered in class:** Halting Problem and Sizes of Infinity..

**In-class problem-solving:** Sizes of infinity.

**Homework:** (optional) Read Sipser, chapter 4. No assignment.

**Other resources:**

- ★★★ Scooping the Loop Snooper: proof by poem that the Halting Problem is undecidable

**Covered in class:** notes. **Additional resource:** Sipser 3.

**In-class problem-solving:** Turing-completeness.

**Homework:** read Sipser, chapter 3. (No assignment.)

**This week’s challenge problem:** Turing Machine simulation. (TMSim program) (template)

**Other resources:**

- ★★★ Conway’s Game of Life
- ★★★ Manufactoria – a game involving Turing machines
- ☆★★ Lego Turing machine
- ☆★★ Universal Turing Machine in Minecraft
- ☆☆★ Universal Turing Machine in Conway’s Game of Life

**Covered in class:** Sipser 1.4 (the Pumping Lemma) and Sipser chapter 2 (context-free grammars and pushdown automata).

**In-class problem-solving:** Grammar Rules (solutions) and CFG problems (solutions).

**Homework:** read or skim Sipser 1 and Sipser 2 – these comprise the material that we covered in class today and yesterday. You should read with the aim of understanding this material better. **Assignment:** Write down one thing that you learned from the textbook – something new that we didn't cover in class, or something that the textbook explained more clearly.

**Additional material:** Pumping Lemma examples – some examples of proofs which involve the Pumping Lemma.

**Other resources:**

- ☆★★ More Ties Than We Thought – a CFG describing tie knots.
- ☆★★ Context Free Art – generate art using context-free grammars
- ☆☆★ a context-free grammar for molecules (showed in class), which I am creating a parser for at my work this summer.

**Covered in class:** sections 1.1, 1.2, and 1.3 of Sipser, chapter 1.

**In-class problem-solving:** aw-TOM-uh-tuh (answer key). Problems about regular operations (answer key).

**Homework:** read section 1.1 through 1.3 of Sipser, chapter 1. No reading question; this reading is for you to review what was covered in class and make sure you understand the material. It also covers the concepts in more rigorous detail.

**Covered in class:** Boolean logic; logic gates; Boolean circuits; base 2 / binary; De Morgan’s laws; NAND and functional completeness; adder circuits; CMOS gates

**In-class problem-solving:** Problems and Select Answers.

**Homework:** read and/or skim Sipser, chapter 0, for important mathematical background and terminology. Focus on “0.2 Mathematical Notions and Terminology.”and “0.3 Definitions, Theorems, and Proofs.” Skip anything you already know. Turn in tomorrow: write down, on a piece of paper, one to three new things you learned.

**Other resources:**

- ★★★ Logicly – a logic gate simulator you can download and play around with
- ★★★ KOHCTPYKTOP – a
*difficult*game about (simplified) silicon circuits and logic gates. Be sure to check the tutorial. - ☆★★ Lightbox – a game involving boolean logic
- ☆★★ The Binary Game – practice your base 2
- ☆☆★ An online worksheet with more practice with boolean circuits
- ☆☆★ A binary-number magic trick

**Covered in class:** An introduction to this class, and its themes. A lecture on L-systems and fractals: Examples of fractals. Definition of an L-system. Interactive demonstration of the dragon curve L-system, with origami example and LSysReader program.

**In-class problem-solving:** Fractals and L-systems handout. (I meant to have this printed out before class, but forgot!) Bonus problem: Why does the “B, A, AB, ABA, ...” L-system form the Fibonacci sequence?

**Homework:** Read The Origins of Computing and answer for tomorrow: *Name one thing that surprised you. Name one thing that you would like to learn more about.*

**Other resources:**

- ★★★ Recursive Drawing – draw fractals! Incredibly fun and highly recommended.
- ☆★★ Ada and the First Computer – for if you want to read more about the Difference Engine
- ☆★★ LSysReader – draw more fractals! This time, with L-systems.
- ☆☆★ Science-vs-Magic has a fractal drawing tool.
- ☆☆★ What happens when you Google "recursion"?

Refer to the Course Syllabus.

- (Day 1) Prove that this L-system –
*Start - B. Rules - A goes to AB; B goes to A.*

– generates the Fibonacci sequence. - (Day 2) How many possible 2-input logic gates are there?
- (Day 2) Problem 4 of the “Circuits” day’s problems: create the Three-inverter Logic Gate using only two NOT gates and as many AND/OR gates as you please.
- (Day 3) Are the regular languages closed under intersection? If not, find a counterexample that demonstrates this is not the case: two regular languages, A and B, such that A intersect B is NOT regular.
- (Day 7) How many points (countable or uncountable infinity) are there in a 2-dimensional square, with line segments of length 1 on each side? How many points (countable or uncountable infinity) are there in the xy-plane? Prove your answer by giving a
*mapping*from points to some other set which you know the size of. - (Day 8) Give a reduction from HALT to BLANKHALT by describing code for a Turing machine that would solve HALT using an oracle for BLANKHALT.
- (Day 9) How many possible Turing machines with
*n*states are there? (State any assumptions you make about how Turing machines are specified, along with your answer.) - (Day 10) Show Curry’s Paradox using set theory notation instead of implications.
- (Day 12) Write a quine in your favorite programming language. (Or your least favorite. Or any old programming language, really.) Remember, the English quine is:

*Say the following twice, the second time in quotes. “Say the following twice, the second time in quotes.”* - (Day 20) Investigate: when is
*g*a generator mod*m*? When is it not? What are the rules? You need not discover the rules to receive a bonus point – just explore, and tell me about what you find. - (Day 22) What sort of procedure could we use, as a class, to create a schedule that is guaranteed to be "randomized" in such a way that nobody, not any of you nor I, has control over the final schedule, and everyone is satisfied that this is the case?
- Implement AND, OR, and NOT using the Fredkin gate, proving that the Fredkin gate is universal.